LP with only equality constraints
Answered
How do I optimize it efficiently? Gurobi treats it as a standard LP (runs barrier/simplex).
Update: I'm not sure about my expectation anymore.
The problem is min c'x s.t. Ax=b.
The KKT system is under-constrained and of the form:
[0 A'] [ x ] = [-c]
[A 0 ] [lam] [ b]
Since it's rank deficient, I'm not sure how to solve it efficiently. I assume that gurobi's presolve would have done it if possible.
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
Gurobi can deal with any kind of rank deficiency. Any sophisticated Simplex/Barrier solvers (not only Gurobi) are usually the best choice for the model you posted. There are exceptions for very specific problems where one can exploit some specific property.
How do I optimize it efficiently?
What does make you thing that your LP is solved inefficiently? Is the solution process too slow?
0 -
-
I naively thought that it's just a matter of solving a linear system of equalities, which usually takes under a second rather than a minute (using packages such mldivide, pardiso, umfpack).
However, if the matrix is singular (under constrained), then getting rid of the null space may not be trivial. It's a question that I've considered before.
In this case, I forgot about my ub and lb, which makes it an LP in a standard form...
0
Post is closed for comments.
Comments
3 comments