# Basis and non-basis matrix
**URL:** https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219
**Category:** Optimization (Mathematical)
**Tags:** jump
**Created:** [February 14, 2024, 6:02pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219 "2024-02-14T18:02:23Z")
**Posts on this page:** 15
**Page:** 1
### Author:  [@mohammad\_amini](https://discourse.julialang.org/u/mohammad_amini)
#### Post date: [February 14, 2024, 6:02pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/1 "2024-02-14T18:02:23Z")
I am seeking methods to identify the basis and non-basis matrices in HiGHS, or determine the status of variables and columns within the basis and non-basis. Additionally, I am curious about accessing the final simplex tableau of a model that I have read through an MPS file.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [February 14, 2024, 6:49pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/2 "2024-02-14T18:49:22Z")
Hi @mohammad_amini, welcome to the forum.
This is something that we’re currently missing documentation for in JuMP (it’s a fairly rare request). I’ve posted an issue to improve: [Suggestions for documentation improvements · Issue #2348 · jump-dev/JuMP.jl · GitHub](https://github.com/jump-dev/JuMP.jl/issues/2348#issuecomment-1944401242)
For now, you can do something like:
```julia
julia> using JuMP, HiGHS
julia> model = direct_model(HiGHS.Optimizer())
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: DIRECT
Solver name: HiGHS
julia> @variable(model, 0 <= x[1:2] <= 1)
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
2-element Vector{VariableRef}:
x[1]
x[2]
julia> @constraint(model, c, sum(x) == 1)
c : x[1] + x[2] = 1
julia> @objective(model, Max, sum(x))
x[1] + x[2]
julia> optimize!(model)
Presolving model
0 rows, 0 cols, 0 nonzeros
0 rows, 0 cols, 0 nonzeros
Presolve : Reductions: rows 0(-1); columns 0(-2); elements 0(-2) - Reduced to empty
Solving the original LP from the solution after postsolve
Model status : Optimal
Objective value : 1.0000000000e+00
HiGHS run time : 0.00
julia> v_stat = Dict(
xi => MOI.get(model, MOI.VariableBasisStatus(), xi)
for xi in all_variables(model)
)
Dict{VariableRef, MathOptInterface.BasisStatusCode} with 2 entries:
x[2] => BASIC
x[1] => NONBASIC_AT_LOWER
julia> c_stat = Dict(
ci => MOI.get(model, MOI.ConstraintBasisStatus(), ci)
for ci in all_constraints(model; include_variable_in_set_constraints = false)
)
Dict{ConstraintRef{Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.EqualTo{Float64}}, ScalarShape}, MathOptInterface.BasisStatusCode} with 1 entry:
c : x[1] + x[2] = 1 => NONBASIC
julia> v_stat[x[1]]
NONBASIC_AT_LOWER::BasisStatusCode = 2
julia> v_stat[x[2]]
BASIC::BasisStatusCode = 0
julia> c_stat[c]
NONBASIC::BasisStatusCode = 1
julia> basic_vars = [xi for (xi, stat) in v_stat if stat == MOI.BASIC]
1-element Vector{VariableRef}:
x[2]
```
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [February 15, 2024, 1:34am UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/3 "2024-02-15T01:34:56Z")
I started to add a tutorial for this: [[docs] add tutorial on querying the basis status by odow · Pull Request #3675 · jump-dev/JuMP.jl · GitHub](https://github.com/jump-dev/JuMP.jl/pull/3675). Not really sure what topics to cover/what would be useful, etc, so feedback appreciated.
---
### Author:  [@mohammad\_amini](https://discourse.julialang.org/u/mohammad_amini)
#### Post date: [February 15, 2024, 6:53pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/4 "2024-02-15T18:53:08Z")
Thank you so much.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [February 15, 2024, 7:17pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/5 "2024-02-15T19:17:09Z")
No problem. What, exactly, do you want to accomplish with the basis? What documentation would be useful?
---
### Author:  [@mohammad\_amini](https://discourse.julialang.org/u/mohammad_amini)
#### Post date: [February 16, 2024, 10:08pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/6 "2024-02-16T22:08:06Z")
The issue I’m encountering pertains to identifying basis and non-basis variables, along with their corresponding matrices, within the final tableau. The challenge arises specifically in the context of degenerate problems. Essentially, it seems this function only account for non-zero variables whose values do not match their lower and upper bounds, But I need to find some variables that their value is zero, or match with their lower or upper bound but we have them in the basis matrix.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [February 16, 2024, 11:40pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/7 "2024-02-16T23:40:50Z")
> Essentially, it seems this function
Which function?
A degenerate variable that has value `0` and is in the basis will still have a `MOI.BASIC` status code.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [February 16, 2024, 11:56pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/8 "2024-02-16T23:56:10Z")
As one example:
```Julia
julia> using JuMP, HiGHS
julia> function is_degenerate(x)
if get_attribute(x, MOI.VariableBasisStatus()) == MOI.BASIC
v = value(x)
return (has_lower_bound(x) && ≈(v, lower_bound(x))) ||
(has_upper_bound(x) && ≈(v, upper_bound(x)))
end
return false
end
is_degenerate (generic function with 1 method)
julia> A, b, c = [1 1; 0 1], [1, 1], [1, 1]
([1 1; 0 1], [1, 1], [1, 1])
julia> model = Model(HiGHS.Optimizer);
julia> set_silent(model)
julia> @variable(model, x[1:2] >= 0)
2-element Vector{VariableRef}:
x[1]
x[2]
julia> @objective(model, Min, c' * x)
x[1] + x[2]
julia> @constraint(model, A * x == b)
[x[1] + x[2] - 1, x[2] - 1] ∈ MathOptInterface.Zeros(2)
julia> optimize!(model)
julia> degenerate_variables = filter(is_degenerate, all_variables(model))
1-element Vector{VariableRef}:
x[1]
```
Edit: I added a section to the docs: [[docs] add tutorial on querying the basis status by odow · Pull Request #3675 · jump-dev/JuMP.jl · GitHub](https://github.com/jump-dev/JuMP.jl/pull/3675/files)
---
### Author:  [@mohammad\_amini](https://discourse.julialang.org/u/mohammad_amini)
#### Post date: [February 19, 2024, 10:46pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/9 "2024-02-19T22:46:27Z")
With this code also I can not find degenerate basic variables for the below model (obviously this model is degenerate in 0,1):
NAME example
ROWS
N OBJ
L R114
L R115
L R116
COLUMNS
MARKER ‘MARKER’ ‘INTORG’
C157 OBJ 3
C157 R114 1
C157 R115 -2
C157 R116 -1
C158 OBJ 2
C158 R114 -2
C158 R115 1
C158 R116 -1
MARKER ‘MARKER’ ‘INTEND’
RHS
RHS1 OBJ 0
RHS1 R114 1
RHS1 R115 1
RHS1 R116 -1
BOUNDS
ENDATA
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [February 19, 2024, 11:44pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/10 "2024-02-19T23:44:40Z")
To clarify, this is your problem?
```julia
julia> using JuMP, HiGHS
julia> A, b, c = [1 -2; -2 1; -1 -1], [1, 1, -1], [3, 2]
([1 -2; -2 1; -1 -1], [1, 1, -1], [3, 2])
julia> model = Model(HiGHS.Optimizer)
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: HiGHS
julia> @variable(model, x[1:2] >= 0, Int)
2-element Vector{VariableRef}:
x[1]
x[2]
julia> cons = @constraint(model, A * x .<= b)
3-element Vector{ConstraintRef{Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}, ScalarShape}}:
x[1] - 2 x[2] ≤ 1
-2 x[1] + x[2] ≤ 1
-x[1] - x[2] ≤ -1
julia> optimize!(model)
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
3 rows, 2 cols, 6 nonzeros
3 rows, 2 cols, 6 nonzeros
Objective function is integral with scale 1
Solving MIP model with:
3 rows
2 cols (0 binary, 2 integer, 0 implied int., 0 continuous)
6 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
Solving report
Status Optimal
Primal bound 0
Dual bound 0
Gap 0% (tolerance: 0.01%)
Solution status feasible
0 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 1 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
julia> get_attribute.(x, MOI.VariableBasisStatus())
2-element Vector{MathOptInterface.BasisStatusCode}:
NONBASIC_AT_LOWER::BasisStatusCode = 2
NONBASIC_AT_LOWER::BasisStatusCode = 2
julia> get_attribute.(cons, MOI.ConstraintBasisStatus())
3-element Vector{MathOptInterface.BasisStatusCode}:
BASIC::BasisStatusCode = 0
BASIC::BasisStatusCode = 0
BASIC::BasisStatusCode = 0
```
I assume the problem is because of the `Int` variables. I don’t know what basis HiGHS returns if it solves an integer problem.
If you drop the integrality, you get:
```Julia
julia> get_attribute.(x, MOI.VariableBasisStatus())
2-element Vector{MathOptInterface.BasisStatusCode}:
NONBASIC_AT_LOWER::BasisStatusCode = 2
BASIC::BasisStatusCode = 0
julia> get_attribute.(cons, MOI.ConstraintBasisStatus())
3-element Vector{MathOptInterface.BasisStatusCode}:
BASIC::BasisStatusCode = 0
BASIC::BasisStatusCode = 0
NONBASIC::BasisStatusCode = 1
```
---
### Author:  [@mohammad\_amini](https://discourse.julialang.org/u/mohammad_amini)
#### Post date: [February 20, 2024, 6:49pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/11 "2024-02-20T18:49:23Z")
> [@odow](#):
>
> `get_attribute.(cons, MOI.ConstraintBasisStatus())`
Thank you. The output is different. After running your code and dropping integrality, output of get\_attribute.(x, MOI.VariableBasisStatus()) is:
NONBASIC\_AT\_LOWER::BasisStatusCode = 2
NONBASIC\_AT\_LOWER::BasisStatusCode = 2
And output for get\_attribute.(cons, MOI.ConstraintBasisStatus()) is:
3-element Vector{MathOptInterface.BasisStatusCode}:
BASIC::BasisStatusCode = 0
BASIC::BasisStatusCode = 0
BASIC::BasisStatusCode = 0
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [February 20, 2024, 8:39pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/12 "2024-02-20T20:39:55Z")
What is the output of `versioninfo()` and `import Pkg; Pkg.status()`?
Do you have the most recent version of HiGHS? Could you post the log of the solver?
---
### Author:  [@mohammad\_amini](https://discourse.julialang.org/u/mohammad_amini)
#### Post date: [February 26, 2024, 5:16pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/13 "2024-02-26T17:16:44Z")
I think I resolved it. It was because of the HiGHS version. Is there any function to find slacks on the basis?
---
### Author:  [@mohammad\_amini](https://discourse.julialang.org/u/mohammad_amini)
#### Post date: [February 26, 2024, 5:18pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/14 "2024-02-26T17:18:10Z")
Julia version is 1.9.4
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [February 26, 2024, 7:35pm UTC](https://discourse.julialang.org/t/basis-and-non-basis-matrix/110219/15 "2024-02-26T19:35:46Z")
There is no explicit function for the slacks.
See this tutorial for some examples: [Sensitivity analysis of a linear program · JuMP](https://jump.dev/JuMP.jl/stable/tutorials/linear/lp_sensitivity/)