search

JuliaOpt / MathProgBase.jl

DEPRECATED: Solver-independent functions (i.e. linprog and mixintprog) and low-level interface for Mathematical Programming
Other
80 stars 38 forks source link

getbasis specification in MIP case #212

Open matbesancon opened 6 years ago

matbesancon commented 6 years ago

From the documentation of the SolverInterface.getbasis function, I'm not sure if it is supposed to return the basis of the augmented constraint matrix (with cuts and bounds) at current node or of the initial linear formulation constraint matrix.

odow commented 6 years ago

It is somewhat ill-defined in MPB.

It would be really helpful if you could read http://www.juliaopt.org/MathOptInterface.jl/latest/apireference.html#Basis-Status-1 and http://www.juliaopt.org/MathOptInterface.jl/latest/apireference.html#MathOptInterface.VariableBasisStatus and suggest edits if necessary in order to help clarify things.

matbesancon commented 6 years ago

I'll check that after this weekend

mtanneau commented 5 years ago

TL;DR: the notion of "basis" is not well-defined for integer solutions, and is not implemented by any major solver.

The notion of basis for a MIP solution is not clearly defined, and thus this is not implemented by any of the major solvers (there is no basis information for a MIP solution in CPLEX/Gurobi/XPress...). [what follows is for the case of Mixed-Integer Linear Programs]

Let's assume you have an integer solution to a MILP. To get basis information, that integer point has to be an extreme vertex of some (LP) polyhedron. First, it may be that no basic solution of the LP relaxation is integer, therefore it makes no sense to seek basis information with respect to the initial formulation. Second, the integer solution may have obtained heuristically, in which case there is definitely no basic information available.

Consequently, the only scenario where "basis information" for a MIP solution may be available, is when a node relaxation yields an integer solution. In this case, you would need access to LP-level information at that node, which would most likely require a solver-specific callback. Even then, the basis may (and most likely will) include cuts/bounds that were not part of the original formulation, and thus not in the scope of the MPB/MOI layer.

matbesancon commented 5 years ago

Thank you both for the answers and details I hadn't thought of the heuristic-found solution.

matbesancon commented 5 years ago

@odow, I don't know if the issue should be closed given that it aims at being fixed in MOI and not MPB. Maybe a wont-fix tag? For the documentation, one thing I didn't find clear on http://www.juliaopt.org/MathOptInterface.jl/latest/apireference.html#Basis-Status-1 is the last status. SuperBasic corresponds to degeneracy?

odow commented 5 years ago

A degenerate variable is one in the basis with variable value of 0. Superbasic variables are exactly what is written: [edit: not] in the basis but not at a bound. See also: https://groups.google.com/forum/#!topic/ampl/vZEHzbyyhVE

Feel free to open an issue at MOI to discuss further. We definitely need help improving the docs :)

matbesancon commented 5 years ago

Oh ok I see this applies only to non-linear problems. I guess this could be good to add it (I was thinking of (MI)LPs and when that's the case, people might forget MOI is meant to be more general

odow commented 5 years ago

Open an issue. I'm not sure how much anyone has actually thought about this part of the API or implemented things.