Linear-Program-Solvers

Introduction

• This repository contains implementations of following linear program (LP) solver algorithms in Python and NumPy:
  1. Simplex algorithm
  2. Primal-Dual Infeasible Interior Point method
  3. Brute force algorithm (exhaustive search over all possible bases)
• The solvers are tested on concrete max-flow (network flow) problems (see Results section below)
• Refer to in-code documentation and comments for description of how the code is working

Repository structure

• Directory solvers/ contains the implementation of the mentioned solvers
  1. Implementation of SimplexSolver class can be found in solvers/simplex_solver.py
  2. Implementation of InteriorPointSolver class can be found in solvers/interior_point_solver.py
  3. Implementation of BruteSolver class can be found in solvers/brute_solver.py
• utils.py contains definition of the following useful helper functions:
  1. network_flow_to_std_LP() that converts a given max-flow problem instance to its corresponding LP
  2. primal_to_dual() that converts a given primal LP in standard form to its corresponding dual in standard form
• main.py contains example driver code that solves two max-flow problem instances using the solvers

Results

We test SimplexSolver and InteriorPointSolver on two separate max-flow instances.

• Network for first max-flow instance is given below (green circle marks a min-cut of the network)

  SimplexSolver gives the following flow assignment for this instance:

The total flow leaving source (vertex-0) in the above flow assignment (16 + 10 = 26) is equal to the sum of the capacities of edges going out of the cut shown above in green (12 + 14 = 26). Hence, this flow assignment is optimal (cf. max-flow min-cut theorem)

• Network for second max-flow instance is given below (green circle marks a min-cut of the network)

  InteriorPointSolver gives the following flow assignment for this instance:

The total flow leaving source (vertex-0) in the above flow assignment (11 + 8 + 10 = 29) is equal to the sum of the capacities of edges going out of the cut shown above in green (11 + 3 + 5 + 10 = 29). Hence, this flow assignment is optimal (cf. max-flow min-cut theorem)

References

1. Introduction to Linear Optimization by Dimitris Bertsimas, John Tsitsiklis
2. Interior-Point Methods by Stephen Wright