search

jump-dev / Xpress.jl

A Julia interface to the FICO Xpress Optimization suite
https://www.fico.com/en/products/fico-xpress-optimization
65 stars 30 forks source link

Possible bug in lazy constraints #191

Closed odow closed 8 months ago

odow commented 1 year ago

Reported on https://discourse.julialang.org/t/issue-with-lazy-constraints-on-xpress/95463

using JuMP
using Xpress
model = Model(()->Xpress.Optimizer(THREADS = 2))
@variable(model, x >= 0, Int)
@variable(model, y >= 0, Int)
@variable(model, FO >= 0)
@constraint(model, FO == x + y )
@constraint(model, x + y <= 220 )
@objective(model, Max, FO)
function lazy_flow_constraints(cb_data)
    x_val = callback_value(cb_data,x)
    y_val = callback_value(cb_data,y)
    if x_val + y_val > 10
        con = @build_constraint( x + y <= 10 )
        MOI.submit(model, MOI.LazyConstraint(cb_data), con)
    end
end
MOI.set(model, MOI.LazyConstraintCallback(), lazy_flow_constraints)
set_optimizer_attributes(model, “HEURSTRATEGY” => 0)
optimize!(model)

yields

ulia> optimize!(model)
FICO Xpress v8.8.0, Hyper, solve started 10:28:18, Mar 3, 2023
Heap usage: 84KB (peak 84KB, 834KB system)
Maximizing MILP
Original problem has:
2 rows 3 cols 5 elements 2 globals
Presolved problem has:
0 rows 0 cols 0 elements 0 globals
LP relaxation tightened
Presolve finished in 0 seconds
Heap usage: 86KB (peak 105KB, 836KB system)
Will try to keep branch and bound tree memory usage below 21.7GB
Starting concurrent solve with dual

Concurrent-Solve, 0s
Dual
objective dual inf
D 220.00000 .0000000
------- optimal --------
Concurrent statistics:
Dual: 0 simplex iterations, 0.00s
Optimal solution found

Its Obj Value S Ninf Nneg Sum Dual Inf Time
0 220.000000 D 0 0 .000000 0
Dual solved problem
0 simplex iterations in 0s

Final objective : 2.200000000000000e+02
Max primal violation (abs/rel) : 0.0 / 0.0
Max dual violation (abs/rel) : 0.0 / 0.0
Max complementarity viol. (abs/rel) : 0.0 / 0.0
All values within tolerances

Starting root cutting & heuristics

Its Type BestSoln BestBound Sols Add Del Gap GInf Time
ERROR: XpressError(32): Subroutine not completed successfully, possibly due to invalid argument. Unable to call Xpress.storecuts:

405 Error: Invalid column number passed to XPRSstorecuts.
Column number 0 is invalid.

Stacktrace:
[1] macro expansion
@ ~/.julia/packages/Xpress/I3tPu/src/utils.jl:137 [inlined]
[2] storecuts(prob::Xpress.XpressProblem, ncuts::Int32, nodupl::Int32, mtype::Vector{Int32}, qrtype::Vector{Int8}, drhs::Vector{Float64}, mstart::Vector{Int32}, mindex::Vector{Ptr{Nothing}}, mcols::Vector{Int32}, dmatval::Vector{Float64})
@ Xpress ~/.julia/packages/Xpress/I3tPu/src/api.jl:2638
[3] submit(model::Xpress.Optimizer, cb::MathOptInterface.LazyConstraint{CallbackData}, f::MathOptInterface.ScalarAffineFunction{Float64}, s::MathOptInterface.LessThan{Float64})
@ Xpress ~/.julia/packages/Xpress/I3tPu/src/MOI/MOI_callbacks.jl:191
[4] submit
@ ~/.julia/packages/MathOptInterface/GIbN0/src/Bridges/bridge_optimizer.jl:1918 [inlined]
[5] submit(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.Bridges.LazyBridgeOptimizer{Xpress.Optimizer}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}, ::MathOptInterface.LazyConstraint{CallbackData}, ::MathOptInterface.ScalarAffineFunction{Float64}, ::MathOptInterface.LessThan{Float64})
@ MathOptInterface.Utilities ~/.julia/packages/MathOptInterface/GIbN0/src/Utilities/cachingoptimizer.jl:1268
[6] submit(model::Model, cb::MathOptInterface.LazyConstraint{CallbackData}, con::ScalarConstraint{AffExpr, MathOptInterface.LessThan{Float64}})
@ JuMP ~/.julia/packages/JuMP/yYfHy/src/callbacks.jl:71
[7] lazy_flow_constraints(cb_data::CallbackData)
@ Main ./REPL[13]:7
[8] (::Xpress.var"#51#52"{Xpress.Optimizer})(cb_data::CallbackData)
@ Xpress ~/.julia/packages/Xpress/I3tPu/src/MOI/MOI_callbacks.jl:100
[9] (::Xpress.var"#49#50"{Xpress.Optimizer, Xpress.var"#51#52"{Xpress.Optimizer}})(cb_data::CallbackData)
@ Xpress ~/.julia/packages/Xpress/I3tPu/src/MOI/MOI_callbacks.jl:27
[10] setcboptnode_wrapper(ptr_model::Ptr{Nothing}, my_object::Ptr{Nothing}, feas::Ptr{Int32})
@ Xpress ~/.julia/packages/Xpress/I3tPu/src/xprs_callbacks.jl:26
[11] XPRSmipoptimize(prob::Xpress.XpressProblem, _sflags::String)
@ Xpress.Lib ~/.julia/packages/Xpress/I3tPu/src/lib.jl:322
[12] macro expansion
@ ~/.julia/packages/Xpress/I3tPu/src/utils.jl:133 [inlined]
[13] mipoptimize
@ ~/.julia/packages/Xpress/I3tPu/src/api.jl:1019 [inlined]
[14] optimize!(model::Xpress.Optimizer)
@ Xpress ~/.julia/packages/Xpress/I3tPu/src/MOI/MOI_wrapper.jl:2622
[15] optimize!
@ ~/.julia/packages/MathOptInterface/GIbN0/src/Bridges/bridge_optimizer.jl:376 [inlined]
[16] optimize!(m::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.Bridges.LazyBridgeOptimizer{Xpress.Optimizer}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}})
@ MathOptInterface.Utilities ~/.julia/packages/MathOptInterface/GIbN0/src/Utilities/cachingoptimizer.jl:325
[17] optimize!(m::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.Bridges.LazyBridgeOptimizer{Xpress.Optimizer}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}})
@ MathOptInterface.Utilities ~/.julia/packages/MathOptInterface/GIbN0/src/Utilities/cachingoptimizer.jl:313
[18] optimize!(model::Model; ignore_optimize_hook::Bool, _differentiation_backend::MathOptInterface.Nonlinear.SparseReverseMode, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
@ JuMP ~/.julia/packages/JuMP/yYfHy/src/optimizer_interface.jl:480
[19] optimize!(model::Model)
@ JuMP ~/.julia/packages/JuMP/yYfHy/src/optimizer_interface.jl:450
[20] top-level scope
@ REPL[16]:1
joaquimg commented 1 year ago

Thanks! Will take a look, we started rewriting those this very week. PR should be online late next week. We will test on this example as well.

rafabench commented 1 year ago

Thanks for reporting! In fact, the presolve from Xpress removed the column 0 from the original problem and couldn't add the specified cut. One way to work around this problem is to disable the presolve, but this is not really necessary. It is possible to map solutions and cutting planes beetween the original and presolved problem, you just need to set the control MIPDUALREDUCTIONS to 0. https://www.fico.com/fico-xpress-optimization/docs/latest/solver/optimizer/HTML/MIPDUALREDUCTIONS.html

using JuMP
using Xpress

model = Model(()->Xpress.Optimizer())
@variable(model, x >= 0, Int)
@variable(model, y >= 0, Int)
@variable(model, FO >= 0)
@constraint(model, FO == x + y )
@constraint(model, x + y <= 220 )
@objective(model, Max, FO)
function lazy_flow_constraints(cb_data)
    x_val = callback_value(cb_data,x)
    y_val = callback_value(cb_data,y)
    if x_val + y_val > 10
        con = @build_constraint( x + y <= 10 )
        MOI.submit(model, MOI.LazyConstraint(cb_data), con)
    end
end
MOI.set(model, MOI.LazyConstraintCallback(), lazy_flow_constraints)
set_optimizer_attributes(model, "MIPDUALREDUCTIONS" => 0)
optimize!(model)

@info(" Execution is " * string(termination_status(model)))

println("x=",JuMP.value(x))
println("y=",JuMP.value(y))

And gives the desired result:

┌ Warning: Callbacks in XPRESS might not work correctly with HEURSTRATEGY != 0
└ @ Xpress C:\Users\rafabench\.julia\dev\Xpress\src\MOI\MOI_wrapper.jl:2660
FICO Xpress v8.14.2, Hyper, solve started 18:38:54, Mar 5, 2023
Heap usage: 124KB (peak 124KB, 595KB system)
Maximizing MILP  using up to 4 threads and up to 15GB memory, with these control settings:
OUTPUTLOG = 1
MPSNAMELENGTH = 64
CALLBACKFROMMASTERTHREAD = 1
MIPDUALREDUCTIONS = 0
Original problem has:
         2 rows            3 cols            5 elements         2 globals
Presolved problem has:
         0 rows            2 cols            0 elements         2 globals
         1 delrows
LP relaxation tightened
Presolve finished in 0 seconds
Heap usage: 129KB (peak 145KB, 595KB system)

Coefficient range                    original                 solved
  Coefficients   [min,max] : [ 1.00e+00,  1.00e+00] / [      0.0,       0.0]
  RHS and bounds [min,max] : [ 2.20e+02,  2.20e+02] / [ 2.20e+02,  2.20e+02]
  Objective      [min,max] : [ 1.00e+00,  1.00e+00] / [ 1.00e+00,  1.00e+00]
Autoscaling applied standard scaling

Will try to keep branch and bound tree memory usage below 7.1GB
 *** Solution found:      .000000   Time:   0    Heuristic: T ***
Starting concurrent solve with dual (1 thread)

 Concurrent-Solve,   0s
            Dual
    objective   dual inf
 D  440.00000   .0000000
------- optimal --------
Concurrent statistics:
      Dual: 0 simplex iterations, 0.00s
Optimal solution found

   Its         Obj Value      S   Ninf  Nneg   Sum Dual Inf  Time
     0        440.000000      D      0     0        .000000     0
Dual solved problem
  0 simplex iterations in 0.01 seconds at time 0

Final objective                       : 4.400000000000000e+02
  Max primal violation      (abs/rel) :       0.0 /       0.0
  Max dual violation        (abs/rel) :       0.0 /       0.0
  Max complementarity viol. (abs/rel) :       0.0 /       0.0

Starting root cutting & heuristics

 Its Type    BestSoln    BestBound   Sols    Add    Del     Gap     GInf   Time
Heuristic search 'R' started
Heuristic search 'R' stopped
*           10.000000    10.000000      2                 -0.00%       0      0
 *** Search completed ***
Uncrunching matrix
Final MIP objective                   : 1.000000000000000e+01
Final MIP bound                       : 1.000000000000000e+01
  Solution time / primaldual integral :         0s/ 99.454320%
  Number of solutions found / nodes   :         2 /         1
  Max primal violation      (abs/rel) :       0.0 /       0.0
  Max integer violation     (abs    ) :       0.0
[ Info:  Execution is OPTIMAL
x=10.0
y=-0.0
daponsr commented 1 year ago

Hi!

I happen to also be trying to implement a "lazy constraint" approach to solve a model with Xpress. I am not having the same issue, mine is related that the first callback all succeeds to submit the lazy constraint, but after a certain number of calls (depending on the problem instance that I am solving), it kind of "freezes" and eventually the time limit pops. Could it have any relations?

Best

odow commented 8 months ago

See also https://discourse.julialang.org/t/lazy-constraints-issues-with-presolve/110449.

We should probably just set MIPDUALREDUCTIONS by default if you have a callback.