what's the meaning of "(super-basic)" in VBasis?
Answered
Hi, everyone, I'm reading the referance mannual, in Attributes Chapter, I'm confused to VBasis status。
Giving an example,
min CX
s.t. a<= X <= b
X >= 0
1. what's the meaning of -1 (non-basic at lower bound), -2 (non-basic at upper bound)?The non-basic variable at lowe bound means X_i(non-basic) = a_i , the non-basic at upper boundX_i(non-basic) = b_i ?
2. what 's the meaning of -3 (super-basic)?
Thanks,
Best regards.
-
Official comment
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 why not try our AI Gurobot?. -
Hi!
The Simplex algorithm handles Linear Programming problems by partitioning the variables into basic and non-basic variables. Non-basic variables are always set to either of their bounds, while basic variables are determined by solving a linear system of equations with the basis matrix.
You may find this video lecture by Bob Bixby very interesting: Robert Bixby: Solving Linear Programs: The Dual Simplex Algorithm (1/3): Some Basic Theory
When solving an LP with the Interior Point or Barrier method, you don't end up at a vertex or basic solution and there might be super-basic variables. These are non-basic variables that are not on their bounds. Gurobi uses the so-called crossover algorithm to determine a proper basic solution that has no more super-basic variables. It's called crossover because we are crossing over from the central point of the optimal hyperplane to one of the vertices of this hyperplane. This is comparable to how the Simplex method works and can sometimes be quite expensive or time-consuming.
Cheers,
Matthias0 -
Thank you. It's so kind of you. I read the lecture that give me the answer of super-basic.
Best regards.
0
Post is closed for comments.
Comments
3 comments