vbasis in Gurobi(Py) for LP has too few basic variables?
Answered
Hi all,
I am using Gurobi to solve a LP and I need access to the basis of the simplex algorithm for some downstream computation. I have specified my model in standard form (i.e. only lower bounds at 0 for all variables, and only equality constraints). After model.optimize(), I therefore call model.vbasis. In VBasis, a 0 indicates a basic variable as described here. Unfortunately, the number of basic variables as indicated by vBasis is sometimes fewer than I would expect (the number of linearly independent equality constraints).
Why is this and how can I get the "full" basis?
My best guess is that this is due to degeneracy, but I don't really understand why.
I am happy to share an instance and a notebook with code for reproduction.
Many thanks
Max
-
Hi Max,
You also need to check for CBasis to get the full basis information.
Cheers,
Matthias1 -
Hi Matthias,
thank you for your reply. Could you please expand on how I should use CBasis to find out which of my variables are in the basis? (I am using the variable basis to form the basis matrix B composed of columns of A which are in the basis). For the particular instance, I referred to above, I find that for 18 linearly independent constraints in A, vBasis returns 17 of 28 variables to be basic, and cBasis returns 1 out of 18 constraints to be basic. Since all my constraints are specified as equality constraints by me, the slacks are naturally zero for all.
Is it the case that Gurobi adds another "Gurobi slack variable" to each constraints (regardless of whether the constraint was specified as equality or inequality by the user) and the information in cBasis means one of the "Gurobi slack variables" should be in the basis?
0 -
Hi Max,
A full basis description always contains \(m+n\) elements. VBasis shows the basis status of variables, while CBasis shows the basis status of constraints.
Consider this example:
Minimize
Subject To
c0: x + y + z = 1
c1: x + y = 1
Bounds
EndThe resulting optimal basis looks as follows:
Vbasis: [0, -1, -1] CBasis: [-1, 0] Solution: [1.0, 0.0, 0.0]
So, \(x\) is basic together with the constraint \(c_0\). The basis matrix is always constructed from columns of \(A\) corresponding to the basic variables and columns of \(I \in \mathbb{R}^{m,m}\) corresponding to the basic constraints - these are the slack variables.
I hope this helps.
Cheers,
Matthias2 -
That's very helpful. Thank you!
0 -
Hi Matthias,
Since there's no slack variable in an equality constraint, how to understand that an equality constraint is basic?
In your example, can we say the basic variables are x and z since columns of A corresponding to them are linearly independent?
Thanks
Andy
1 -
Hi Andy,
an equality constraint has kind of a slack variable with an upper and lower bound of 0.
When the equality constraint is basic, then this variable is part of the basis.
Best regards,
Thomas1 -
Hi Thomas,
Thanks for your explanation! I want to ask another question.
For an LP problem in its standard form, can we get a basis containing only its variables with gurobi or other tools?
Best wishes,
Andy
1 -
Hi Andy,
first of all, if you look into literature, you might find different standard forms for LPs. So you should tell us which standard form you are talking about.
Anyway, for every form, you might run into the problem that you might have redundant constraints. If you have got redundant constraints, you cannot build a basis of only the variables. So I would say in general the answer is "no". (Eliminating all redundant constraints typically is too expensive, if I remember correctly.)
Best regards,
Thomas0
Please sign in to leave a comment.
Comments
8 comments