# How to obtain a Basic solution?

**URL:** <https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784>\
**Category:** Optimization (Mathematical)\
**Tags:** question, jump\
**Created:** [January 30, 2017, 1:19pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784 "2017-01-30T13:19:57Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [January 30, 2017, 1:19pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784/1 "2017-01-30T13:19:57Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![joehuchette](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/joehuchette/32/32_2.png) [@joehuchette](https://discourse.julialang.org/u/joehuchette)\
**Post date:** [January 30, 2017, 2:44pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784/2 "2017-01-30T14:44:56Z")

</div>

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`](http://mathprogbasejl.readthedocs.io/en/latest/lpqcqp.html#getbasis) to inspect the basis information, if the solver supports this.

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [January 30, 2017, 4:22pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784/3 "2017-01-30T16:22:20Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![chkwon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chkwon/32/3632_2.png) [@chkwon](https://discourse.julialang.org/u/chkwon)\
**Post date:** [January 30, 2017, 5:23pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784/4 "2017-01-30T17:23:48Z")

</div>

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

```julia
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:

```julia
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.

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [January 30, 2017, 7:34pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784/5 "2017-01-30T19:34:17Z")

</div>

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`?

---

<div class="post-metadata">

**Author:** ![chkwon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chkwon/32/3632_2.png) [@chkwon](https://discourse.julialang.org/u/chkwon)\
**Post date:** [January 30, 2017, 7:38pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784/6 "2017-01-30T19:38:47Z")

</div>

@e3c6: Already @joehuchette gave the link 🙂

[http://mathprogbasejl.readthedocs.io/en/latest/lpqcqp.html#getbasis](http://mathprogbasejl.readthedocs.io/en/latest/lpqcqp.html#getbasis)

This doc explains what `cbasis` and `rbasis` are.

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [January 30, 2017, 7:41pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784/7 "2017-01-30T19:41:33Z")

</div>

Oh I had missed that. Thanks.

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [February 2, 2017, 6:03pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784/8 "2017-02-02T18:03:31Z")

</div>

@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)?

---

<div class="post-metadata">

**Author:** ![e3c6](https://avatars.discourse-cdn.com/v4/letter/e/e79b87/32.png) [@e3c6](https://discourse.julialang.org/u/e3c6)\
**Post date:** [February 2, 2017, 6:14pm UTC](https://discourse.julialang.org/t/how-to-obtain-a-basic-solution/1784/9 "2017-02-02T18:14:16Z")

</div>

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.