To solve a linear program (LP) using the simplex method one first needs to bring the LP to standard form. This requires replacing every equality constraint with two inequalities and replacing every free variable with two non-negative variables. I have always felt like this approach can obscure the true structure of the problem and is not the most efficient as it increases the dimensions of the problem. Hence the question: do state-of-the-art solvers convert LPs to standard form before solving, or do they apply more clever strategies to deal with equality constraints and free variables?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
No, state of the art LP solvers do not do that. They do bring the problem into a computational form that suits the algorithm used. Note that in the case of simplex algorithms, modern solvers use the revised simplex method with lower and upper bounds that does not require standard form. You can get an idea of the computation forms used from "Computational Techniques of the Simplex Method" by István Maros.
The exact form depends on implementational details and might be different from one major solver to the other while not leading to significant performance differences. But specifically the splitting up of equalities and free variables is inefficient and most likely not done by anyone.
answered Mar 4, 2021 at 15:10
-
-
2$\begingroup$ Another reference might be "The Dual Simplex Method, Techniques for a fast and stable implementation" by Achim Koberstein. I think the main idea is to add an artificial variable to every constraint and give them upper, lower or upper and lower bounds. Then every constraint can be an equality constraint with right-hand side 0. $\endgroup$– T_OMar 4, 2021 at 22:54
-
1$\begingroup$ Another relevant reference regarding implementation of the simplex is "Linear Programming Computation" by Ping-Qi Pan. $\endgroup$ Mar 5, 2021 at 8:39
$\begingroup$
$\endgroup$
1
Based on their manual, as I understood, Gurobi does not reformat the equality constraint because the equality expression can immediately be added to the list of constraints. They use more clever ways to handle these situations but as a black-box commercial solver, they don't share these approaches with the public and you would never know those techniques.
Please check the Gurobi reference manual page 234 where the equality and inequality operators are being explained.
Although increasing the number of constraints and variables may affect the complexity of the model but I don't agree with your statement when you said:
I have always felt like this approach can obscure the true structure of the problem
answered Mar 4, 2021 at 14:27
-
$\begingroup$ The statement about the structure seems somehow valid for MIP. I think for LP, the structure is not as important as for MIP if you don't want to do decomposition. $\endgroup$– T_OMar 4, 2021 at 22:58