Skip to main content

vbasis in Gurobi(Py) for LP has too few basic variables?

Answered

Comments

8 comments

  • Matthias Miltenberger
    Gurobi Staff Gurobi Staff

    Hi Max,

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

    Cheers,
    Matthias

    1
  • Max Paulus
    Gurobi-versary
    First Comment
    First Question

    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
  • Matthias Miltenberger
    Gurobi Staff 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:

    Minimize
    Subject To
    c0: x + y + z = 1
    c1: x + y = 1
    Bounds
    End

    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

    2
  • Max Paulus
    Gurobi-versary
    First Comment
    First Question

    That's very helpful. Thank you!

    0
  • Anqi Lu
    First Comment

    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
  • Thomas Opfer
    Gurobi-versary
    Thought Leader

    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

    1
  • Anqi Lu
    First Comment

    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
  • Thomas Opfer
    Gurobi-versary
    Thought Leader

    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

    0

Please sign in to leave a comment.