I have coded recently the simplex algorithm. It is an algorithm that solves the optimizations of a problem of linear programming. It gives a function to minimize and constrains the variables with an inequality form.
It can be proven that the simplex algorithm solves this problem in Non-Polynomial time.
The simplex algorithm iterates over feasible solutions and minimizes the value of the function
The image below shows an example of the code that solves a linear programming problem
As it shows, it creates a table with the variables used by the algorithm.
Sometimes can not find a feasible solution, we can reinterpret the problem of finding a feasible solution with a linear programming one. It executes the simplex algorithm two times, the first to find a feasible solution and the second to optimize.
It can be proven that the optimization of the first problem is equivalent that there exists an optimum solution.
It can be defined the dual problem of ours. It has special properties, whether our problem is not feasible then the dual is not too.
We can use the dual version of the simplex algorithm to find feasible solutions to our problem. It will be used to add new restrictions to the problem
This is an important part of the problem, we can use an optimized problem to accelerate the optimization of a new version of ours.
- Add restriction
- New Costs
- New independent variables
- New variable
Integer Linear Programming
We can use the simplex algorithm in order to get an optimized solution to a solution that is integer-only or integer-mixed. We can use two algorithms that I have implemented: Hyper-planes cutting and Ramiction and Bounding.