Gurobi LP solver's cut-off behavior---an example

Specific Domains Optimization (Mathematical)
,
1

I find an interesting example about Gurobi’s LP solver.
There are 2 linear constraints in my LP, named fixed and cut.

The outcomes for the following 2 schemes are different:

  1. Add Both constraints, and solve only once
  2. Add fixed, solve; Then add cut, solve again

In the 1st scheme, the solution y = -1.192e-6.
In the 2nd scheme, the solution upon the first solve is y = -2.384e-6. Theoretically, upon adding the cut, the updated solution y should be the same as the 1st scheme (because the final model are identical). But the cut cannot cut off the first solution y = -2.384e-6.

Here is the runnable code to produce the above results

import JuMP, Gurobi
function optimise(model)
    JuMP.optimize!(model)
    JuMP.assert_is_solved_and_feasible(model; allow_local = false, dual = true)
end
c = -4.76837158203125e-6
model = JuMP.Model(Gurobi.Optimizer) 
JuMP.@variable(model, y)
JuMP.@objective(model, Min, 2 * y)
JuMP.@constraint(model, fixed, -9.5367431640625e-6 * y <= 2.2737367544323206e-11)
optimise(model);
yt = JuMP.value(y)
JuMP.@constraint(model, cut, c * y <= 5.6843418860808015e-12)
optimise(model);
yt = JuMP.value(y)

Then I proceed to explore the can-cut-off behavior.
I modify the RHS constant of cut, and find the 2 values, with one can cut off while the other cannot.

b = -1.1e-9 # cannot cut off
b = -2.9e-9 # can cut off
JuMP.@constraint(model, cut, c * y <= b)
optimise(model);
yt = JuMP.value(y)

I guessed Gurobi decide whether the current trial point y = -2.384e-6 is cut off according to the violation of the new cut. But with this line of reasoning, the critical violation is a value which is not very rational (It’s somewhere between 1.1e-9 and 2.9e-9).

I don’t quite understand this.

2

Have you tried setting a tolerance? Setting tolerances in JuMP - is there an Optimizer-independent way? - #2 by odow

1 Like
4

The updated description should be more clearer.
I guess it’s not a straightforward tolerance problem.
I’m sleeping now. I’ll check the other issues tomorrow :slightly_smiling_face:.

5

Read Tolerances and numerical issues · JuMP

6

I read them. Although it is ideal to have the recommended setting, in real cases numerical problematic cuts are generated via algorithms, e.g. my case.

And to update, I didn’t quite understand how Gurobi judges (the last line below)

import JuMP, Gurobi
function optimise(model)
    JuMP.optimize!(model)
    JuMP.assert_is_solved_and_feasible(model; allow_local = false, dual = true)
end
function test_can_cut_off(b)
    model = JuMP.Model(Gurobi.Optimizer)
    JuMP.set_silent(model) 
    JuMP.@variable(model, y)
    JuMP.@objective(model, Min, 2 * y)
    JuMP.@constraint(model, fixed, -9.5367431640625e-6 * y <= 2.2737367544323206e-11)
    optimise(model);
    yt = JuMP.value(y)
    JuMP.@constraint(model, cut, c * y <= b)
    optimise(model);
    println("y was $yt, y is $(JuMP.value(y)). Vio = $(c * yt - b)")
end
c = -4.76837158203125e-6
base = -1.95e-9
d = 1e-11

b = base + d/5 # can cut off
test_can_cut_off(b) # y was -2.384185791015625e-6, y is 0.0004085252096. Vio = 1.9593686837721615e-9
b = base + d # cannot cut off
test_can_cut_off(b) # y was -2.384185791015625e-6, y is -2.384185791015625e-6. Vio = 1.9513686837721615e-9
# Remark: if Gurobi adopts a Vio parameter, it should be some number between 1.951e-9 and 1.959e-9, which is not very rational
7

Gurobi’s default feasibility tolerance is 1e-6: Parameter Reference - Gurobi Optimizer Reference Manual

You cannot rely on specific behavior below this limit. It may find a solution that has a violation of 1e-10 or it may find a solution that has a tolerance of 1e-6. Gurobi doesn’t care, so long as the violation is less than the tolerance.

1 Like
8

Therefore I set a tolerance myself, in my real-world application.
e.g. this example.