• Gurobi Staff

Hi Max,

You also need to check for CBasis to get the full basis information.

Cheers,
Matthias

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?

• Gurobi Staff

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:

MinimizeSubject To c0: x + y + z = 1 c1: x + y = 1BoundsEnd

The 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,
Matthias

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

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,
Thomas

Hi Thomas,

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

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,
Thomas