How to obtain a Basic solution?

question
jump
#1

Is there a way to guarantee that the solution returned by JuMP to a linear program is a basic solution?

I know this is probably a responsability of the solver. Is there an option I can pass from JuMP to any solver that guarantees that the solution is basic?

#2

This would be a solver-level setting, though I believe (most of) the LP solvers available from julia will either use the simplex method or apply crossover after an interior point algorithm to give you an optimal basic solution. You can try calling the MathProgBase function getbasis to inspect the basis information, if the solver supports this.

#3

Do you happen to know if Gurobi (with default settings) will return a basic solution?

#4

I was also curious about this and ran the following code:

using JuMP, Gurobi
m = Model(solver=GurobiSolver())
@variable(m, x[1:4]>=0)
@objective(m, Min, x[1] + x[2])
@constraint(m, const1, x[1] + 2x[2] + x[3] == 4)
@constraint(m, const2, x[2] + x[4] == 1)
solve(m)
@show getvalue(x)

cbasis, rbasis = MathProgBase.getbasis(internalmodel(m))

@show cbasis
@show rbasis

The results are:

getvalue(x) = [0.0,0.0,4.0,1.0]
4-element Array{Float64,1}:
 0.0
 0.0
 4.0
 1.0

cbasis = Symbol[:NonbasicAtLower,:NonbasicAtLower,:Basic,:Basic]
4-element Array{Symbol,1}:
 :NonbasicAtLower
 :NonbasicAtLower
 :Basic          
 :Basic          

rbasis = Symbol[:NonbasicAtLower,:NonbasicAtLower]
2-element Array{Symbol,1}:
 :NonbasicAtLower
 :NonbasicAtLower

From cbasis, I can tell x[3] and x[4] are basic variables.

#5

Thanks. I was trying to find getbasis in MathProgBase docs but I could not find it. This code sample helps me a lot. Do you know what are cbasis and rbasis?

#6

@cossio: Already @joehuchette gave the link :slight_smile:

http://mathprogbasejl.readthedocs.io/en/latest/lpqcqp.html#getbasis

This doc explains what cbasis and rbasis are.

#7

Oh I had missed that. Thanks.

#8

@chkwon, @joehuchette As a follow up question, how can I determine if a solution is degenerate (a basic variable is zero)?

Just looking at cbasis, rbasis and comparing the variable values to zero gets messy. The problem is that in a complex model, that I formulated through JuMP, I lost track of how the indices in cbasis, rbasis match to which variables / constrains in the model. Additionally, I do not know which variables have lower, and upper bounds, which are unbounded, and which are only restricted to be non-negative.

Is there a simpler way? Maybe MathProgBase exposes an isdegenerate API (I did not find any)?

#9

Well I found a way. Use getsolution, getvarLB and getvarUB from MathProgBase to lower bounds and variable values in whatever order they got defined internally by Julia. Then for the variables where cbasis is :Basic, check whether the variable value equals the lower bound or the upper bound. If it does the solution is degenerate.