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.
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
For now, you can do something like:
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]
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. Not really sure what topics to cover/what would be useful, etc, so feedback appreciated.
Thank you so much.
1 Like
No problem. What, exactly, do you want to accomplish with the basis? What documentation would be useful?
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.
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.
As one example:
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
1 Like
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
To clarify, this is your problem?
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> 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
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
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?
I think I resolved it. It was because of the HiGHS version. Is there any function to find slacks on the basis?
Julia version is 1.9.4
There is no explicit function for the slacks.
See this tutorial for some examples: Sensitivity analysis of a linear program · JuMP