Retrieve the simplex tableau from Gurobi.jl using JuMP

Specific Domains Optimization (Mathematical)
,
1

Hello everyone!

I’m trying to retrieve the optimal simplex tableau after solving a linear program using Gurobi. Thanks to Oscar’s help, I learned how to use the GRBBinvRowi function to access individual rows of the inverse basis matrix. Here’s the helper function I’m using:

using JuMP
import Gurobi

"""
    my_GRBBinvRowi(model::Gurobi.Optimizer, i::Int)

Computes a single row of the simplex tableau (row `i` of B⁻¹A).

`i` is the zero-based index of an affine constraint.

See Gurobi documentation:
https://docs.gurobi.com/projects/optimizer/en/current/reference/c/simplex.html#c.GRBBinvRowi
"""
function my_GRBBinvRowi(model::Gurobi.Optimizer, i::Int)
    grb = model
    pNumVars, pNumConstrs = Ref{Cint}(0), Ref{Cint}(0)
    @assert Gurobi.GRBgetintattr(grb, "NumConstrs", pNumConstrs) == 0
    @assert Gurobi.GRBgetintattr(grb, "NumVars", pNumVars) == 0
    len = pNumVars[] + pNumConstrs[]
    ind, val = zeros(Cint, len), zeros(Cdouble, len)
    x = Gurobi.GRBsvec(len, pointer(ind), pointer(val))
    @assert Gurobi.GRBBinvRowi(grb, i, Ref(x)) == 0
    return ind, val
end

I tested the function with this small example:

c = [1, 2]
A = [-1 1; 1 1; 2 -1]
b = [2, 5, 4]

model = direct_model(Gurobi.Optimizer())
@variable(model, x[1:2] >= 0)
@objective(model, Max, c' * x)
@constraint(model, A * x .<= b)
optimize!(model)

grb = backend(model)
ind, val = my_GRBBinvRowi(grb, 0)

The output was:

(Int32[2, 3, 4, 0, 0], [1.5, -0.5, 1.0, -0.5, 1.0])

Now I’m confused by two things:

  1. The index vector contains two zeros (i.e., index 0 appears twice) with different values. What do these duplicate entries mean?
  2. According to Gurobi’s documentation, the result vector may include entries for slack variables, with slack variable for row i having index cols + i. But:
  • How do artificial variables fit in here?
  • What do the two values at index 0 correspond to? Why does this happen? The index 0 should corresponds to the first variable, x[1].

Any insight into interpreting the result of GRBBinvRowi correctly, especially regarding artificial variables and duplicate indices, would be greatly appreciated!

Thanks in advance!

2

I guess I should have tested before sending to you! Here you go. The vector is sparse, so the missing values are 0.0.

julia> using JuMP

julia> import Gurobi

julia> function my_GRBBinvRowi(model::Gurobi.Optimizer, i::Int)
           pNumVars, pNumConstrs = Ref{Cint}(0), Ref{Cint}(0)
           @assert Gurobi.GRBgetintattr(model, "NumConstrs", pNumConstrs) == 0
           @assert Gurobi.GRBgetintattr(model, "NumVars", pNumVars) == 0
           len = pNumVars[] + pNumConstrs[]
           ind, val = zeros(Cint, len), zeros(Cdouble, len)
           x = Gurobi.GRBsvec(0, pointer(ind), pointer(val))
           pX = Ref(x)
           @assert Gurobi.GRBBinvRowi(model, i, pX) == 0
           modified_x = pX[]
           return ind[1:modified_x.len], val[1:modified_x.len]
       end
my_GRBBinvRowi (generic function with 1 method)

julia> begin
           c = [1, 2]
           A = [-1 1; 1 1; 2 -1]
           b = [2, 5, 4]
           model = direct_model(Gurobi.Optimizer())
           set_silent(model)
           @variable(model, x[1:2] >= 0)
           @objective(model, Max, c' * x)
           @constraint(model, A * x .<= b)
           optimize!(model)
           grb = backend(model)
           ind, val = my_GRBBinvRowi(grb, 0)
       end
Set parameter LicenseID to value 890341
(Int32[2, 3, 4], [1.5, -0.5, 1.0])

I did some similar stuff in SDDP.jl which might help: