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.
-
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
Please sign in to leave a comment.
Comments
2 comments