Skip to content

Python implementations of Simplex Method, Branch and Bound, Gomory's Cutting Plane Method, Iterative: Steepest Gradient Descent, Newton's Method

Notifications You must be signed in to change notification settings

Megha-Bose/Optimization-Methods

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

11 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Optimization Methods

Python implementations of Simplex Method, Branch and Bound, Ellipsoid Method and Gomory's Cutting Plane Method.

Simplex Algorithm

Simplex algorithm is implemented in simplex.py to solve given optimization problem. Two phase method is used for initialization of simplex algorithm.

Input Format

Each input file for this section has the following structure:

See sample_input_simplex.txt for reference.

Output Format

  • If the optimal solution exists, then the optimal value if given as output along with the vector of optimal values of the variables.
  • If there is unbounded solution, outputs ”Unbounded”.
  • If infeasible, outputs ”Infeasible”.

See sample_output_simplex.txt for reference.

Branch and Bound

Problem taken: Given a set of villages and distance between every pair of villages, find a tour (a cycle that visits all the nodes) of minimum cost. The cut set formulation of travelling salesman problem is used here.

Branch and bound algorithm is used to find a tour with minimum cost. To solve LP relaxation problem, the Simplex Algorithm routing developed above is used.

Input Format

Each input file for this section has the following structure:

See sample_input_bb.txt for reference.

Output Format

  • If a tour exists:
    • (a) Outputs the cost of the minimum distance tour.
    • (b) Outputs a Boolean vector of dimension |E|, where i th value denotes whether i th edge is included in the tour or not.
    • (c) Outputs the number of nodes explored (or output the number of LP relaxations solved).
  • If there does not exist any tour, then outputs ”Infeasible Problem”, the number of nodes explored.

See sample_output_bb.txt for reference.

Cutting Plane Method

Gomory’s cutting plane method is implemented to solve given integer programming problem. To solve LP relaxation problem, the Simplex Algorithm routing developed above is used.

Input format

Each input file for this section has the following structure:

See sample_input_cutting_plane.txt for reference.

Output format

  • If solution exists,
    • (a) Outputs the optimal value (up to 6 decimals).
    • (b) Outputs an N - dimensional integer vector, denoting optimal solution.
    • (c) Outputs the number of cutting planes generated (or the number of LP relaxations solved).
  • In case of unbounded solution, outputs ”Unbounded” and the number of cutting planes generated (or the number of LP relaxations solved).
  • In case of no solution outputs ”Infeasible Solution” and the number of cutting planes generated (or the number of LP relaxations solved).

See sample_output_cutting_plane.txt for reference.

About

Python implementations of Simplex Method, Branch and Bound, Gomory's Cutting Plane Method, Iterative: Steepest Gradient Descent, Newton's Method

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages