Analyzing the conditioning of a MIP
回答済み
Hello everyone,
I have several different MIP formulations for the same problem, which I am currently benchmarking against each other. One thing I would like to look at is the conditioning of the resulting matrices. I already had a request like this a while back in the old Google Groups forum and thus know that the 'Kappa statistics' as offered by CPLEX (basically, a rough histogram of the Kappa values of the LP relaxations seen at the Branch & Cut nodes) is not available in Gurobi.
However, there is the Kappa attribute, which according to the documentation is only available for LPs. I wonder if I am able to use that to access the Kappa of the original MIP, and the presolved MIP. I was thinking about:
* First, use Model.relax() to transform my MIP into an LP with the same matrix
* Then, query Kappa
* Then, on the original non-relaxed model, call .presolve()
* Relax the model again, query Kappa again
Now my questions:
* Do I need to call .solve() on the relaxed models before I'm able to retrieve a Kappa value? The documentation says "Only available for basic solutions." - that seems to me that Gurobi needs to have computed a solution to get me a Kappa value. What if the solution computed by .solve() is not a basic solution? I know that there is always an optimal basic (feasible) solution, however a solution being optimal does not mean that it is basic. Does Gurobi always compute a basic optimal solution? Plain Simplex should do that, however I don't know if Gurobi does "just simplex"…
* Obviously, that's inefficient, because my subsequent solving of the MIP does optimize the root relaxation again. Is there a more efficient way of getting to those Kappa values?
-
正式なコメント
-
Gurobi Staff
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?. -
-
-
The condition number "kappa" is a property of a square matrix. So, there is not a single "kappa" for your model, but any subset of the columns of cardinality equal to the number of rows yields one such square matrix and thus one particular "kappa". One choice of a subset of columns is an optimal basis for the LP. This is the "kappa" that Gurobi returns. You need to first call solve() in order to find an optimal basis, and then you can query its condition number. Both primal and dual simplex provide a basic solution to your model. The barrier algorithm only provides a basic solution if you use crossover to find it. Using crossover is the default setting.
Your approach does something that is somewhat reasonable, but it doesn't provide the full picture. It is just sampling the set of basic solutions of the LP. Namely, it just tests for one particular basis matrix. Hence, if this has a large kappa value, then it is likely that you will have trouble with solving your model as a MIP. But on the other hand, if this kappa value is small, it does not say anything about the numerical properties of the MIP. It could be that there are other basis matrices with a very large kappa that the MIP solve would have to work with.
0 -
投稿コメントは受け付けていません。
コメント
2件のコメント