jump-dev / Cbc.jl

A Julia interface to the Coin-OR Branch and Cut solver (CBC)
https://projects.coin-or.org/Cbc
Other
81 stars 35 forks source link

Providing custom start value causes double free #187

Open lassepe opened 2 years ago

lassepe commented 2 years ago

When I provide a custom start value for some of my variables via JuMP, then the solver crashes with segfault and/or double free errors. I can only reproduce for indicator constraints as reported below:

using Cbc: Cbc
using JuMP: JuMP, @constraint, @objective, @variable

model = JuMP.Model(Cbc.Optimizer)
@variable(model, x[1:2], Bin, start = false)
@variable(model, y[1:2], Bin, start = false)

@constraint(model, x[1] => {y[1] == true})
@constraint(model, x[1] => {y[2] == false})
@constraint(model, x[2] => {y[1] == false})
@constraint(model, x[2] => {y[2] == true})

@objective(model, Max, sum(x))
JuMP.optimize!(model)
odow commented 2 years ago

This syntax is not valid JuMP:

julia> model = Model()
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: NO_OPTIMIZER
Solver name: No optimizer attached.

julia> @variable(model, x[1:10], Bin, false)
ERROR: At REPL[14]:1: `@variable(model, x[1:10], Bin, false)`: Unrecognized positional arguments: (false,). (You may have passed it as a positional argument, or as a keyword value to `variable_type`.)

If you're trying to create a JuMP extension, you need to implement `build_variable`. Read the docstring for more details.
Stacktrace:
  [1] error(::String, ::String)
    @ Base ./error.jl:42
  [2] _macro_error(macroname::Symbol, args::Tuple{Symbol, Expr, Symbol, Bool}, source::LineNumberNode, str::String)
    @ JuMP ~/.julia/dev/JuMP/src/macros.jl:1657
  [3] (::JuMP.var"#_error#105"{LineNumberNode})(str::String)
    @ JuMP ~/.julia/dev/JuMP/src/macros.jl:1968
  [4] build_variable(_error::JuMP.var"#_error#105"{LineNumberNode}, info::VariableInfo{Float64, Float64, Float64, Float64}, args::Bool; kwargs::Base.Iterators.Pairs{Union{}, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ JuMP ~/.julia/dev/JuMP/src/macros.jl:1556
  [5] build_variable(_error::Function, info::VariableInfo{Float64, Float64, Float64, Float64}, args::Bool)
    @ JuMP ~/.julia/dev/JuMP/src/macros.jl:1555
  [6] (::var"#3#4")(260::Int64)
    @ Main ~/.julia/dev/JuMP/src/Containers/macro.jl:309
  [7] (::JuMP.Containers.var"#37#38"{var"#3#4"})(I::Tuple{Int64})
    @ JuMP.Containers ~/.julia/dev/JuMP/src/Containers/container.jl:72
  [8] iterate
    @ ./generator.jl:47 [inlined]
  [9] collect(itr::Base.Generator{JuMP.Containers.VectorizedProductIterator{Tuple{Base.OneTo{Int64}}}, JuMP.Containers.var"#37#38"{var"#3#4"}})
    @ Base ./array.jl:678
 [10] map(f::Function, A::JuMP.Containers.VectorizedProductIterator{Tuple{Base.OneTo{Int64}}})
    @ Base ./abstractarray.jl:2323
 [11] container
    @ ~/.julia/dev/JuMP/src/Containers/container.jl:72 [inlined]
 [12] container(f::Function, indices::JuMP.Containers.VectorizedProductIterator{Tuple{Base.OneTo{Int64}}})
    @ JuMP.Containers ~/.julia/dev/JuMP/src/Containers/container.jl:66
 [13] macro expansion
    @ ~/.julia/dev/JuMP/src/macros.jl:142 [inlined]
 [14] top-level scope
    @ REPL[14]:1

Please provide a reproducible example.

lassepe commented 2 years ago

Hi @odow,

Sorry, I was moving a bit too quickly last night when I filed the issue. I've edited the description to include an MWE that reliable reproduces the issue reported above

odow commented 2 years ago

Still not reproducible unfortunately:

julia> using Cbc: Cbc

julia> using JuMP: JuMP, @constraint, @objective, @variable

julia> model = JuMP.Model(Cbc.Optimizer)
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: COIN Branch-and-Cut (Cbc)

julia> @variable(model, x[1:2], Bin, start = false)
2-element Vector{JuMP.VariableRef}:
 x[1]
 x[2]

julia> @variable(model, y[1:2], Bin, start = false)
2-element Vector{JuMP.VariableRef}:
 y[1]
 y[2]

julia> @constraint(model, x[1] => {y[1] == true})
x[1] => {y[1] = 1.0}

julia> @constraint(model, x[1] => {y[2] == false})
x[1] => {y[2] = 0.0}

julia> @constraint(model, x[2] => {y[1] == false})
x[2] => {y[1] = 0.0}

julia> @constraint(model, x[2] => {y[2] == true})
x[2] => {y[2] = 1.0}

julia> @objective(model, Max, sum(x))
x[1] + x[2]

julia> JuMP.optimize!(model)
Welcome to the CBC MILP Solver 
Version: 2.10.5 
Build Date: Dec  4 2021 

command line - Cbc_C_Interface -solve -quit (default strategy 1)
Continuous objective value is 2 - 0.00 seconds
Cgl0004I processed model has 2 rows, 6 columns (2 integer (2 of which binary)) and 4 elements
Cbc0045I MIPStart provided solution with cost 0
Cbc0012I Integer solution of 0 found by Reduced search after 0 iterations and 0 nodes (0.00 seconds)
Cbc0036I Heuristics switched off as 4 branching objects are of wrong type
Cbc0013I At root node, 0 cuts changed objective from -2 to -2 in 1 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 1 (Gomory) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, 0 best solution, best possible -2 (0.00 seconds)
Cbc0016I Integer solution of -1 found by strong branching after 0 iterations and 1 nodes (0.00 seconds)
Cbc0001I Search completed - best objective -1, took 0 iterations and 2 nodes (0.00 seconds)
Cbc0032I Strong branching done 6 times (1 iterations), fathomed 1 nodes and fixed 0 variables
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from -2 to -2
Probing was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
2 bounds tightened after postprocessing

Result - Optimal solution found

Objective value:                1.00000000
Enumerated nodes:               2
Total iterations:               0
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.01

Total time (CPU seconds):       0.00   (Wallclock seconds):       0.01

What versions are you running? What is versioninfo()? What is the full error message?

However, you're better off formulating this as a MILP directly:

model = JuMP.Model(Cbc.Optimizer)
@variable(model, x[1:2], Bin, start = 0)
@variable(model, y[1:2], Bin, start = 0)
JuMP.@constraints(model, begin
    x[1] <= y[1]     # x[1] => {y[1] == true}
    x[1] <= 1 - y[2] # x[1] => {y[2] == false}
    x[2] <= 1 - y[2] # x[2] => {y[1] == false}
    x[2] <= y[2]     # x[2] => {y[2] == true}
end)
@objective(model, Max, sum(x))
JuMP.optimize!(model)
lassepe commented 2 years ago

I'm on Julia 1.7 and Cbc master:

julia> versioninfo()
Julia Version 1.7.2
Commit bf53498635 (2022-02-06 15:21 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: AMD Ryzen 9 5900HX with Radeon Graphics
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, znver3)
Environment:
  JULIA_NUM_THREADS = 10

(Cbc-double-free-187) pkg> status
      Status `~/worktree/BugReports/Cbc-double-free-187/Project.toml`
  [9961bab8] Cbc v0.9.2 `https://github.com/jump-dev/Cbc.jl.git#master`
  [4076af6c] JuMP v0.22.3
lassepe commented 2 years ago

Also, thank you for your suggestion regarding the MILP formulation. The problem that I actually want to solve is a bit different and is not amenable to this kind of reformulation though. I was just simplifying things for the sake of this MWE.

odow commented 2 years ago

What is the full error message?

lassepe commented 2 years ago

This is the output that I get from the example above:

command line - Cbc_C_Interface -solve -quit (default strategy 1)
Continuous objective value is 2 - 0.00 seconds
Cgl0004I processed model has 2 rows, 6 columns (2 integer (2 of which binary)) and 4 elements
Cbc0045I MIPStart provided solution with cost 0
Cbc0012I Integer solution of 0 found by Reduced search after 0 iterations and 0 nodes (0.00 seconds)
Cbc0036I Heuristics switched off as 4 branching objects are of wrong type
Cbc0013I At root node, 0 cuts changed objective from -2 to -2 in 1 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 1 (Gomory) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.000 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, 0 best solution, best possible -2 (0.00 seconds)
free(): invalid next size (fast)

signal (6): Aborted
in expression starting at /home/lassepe/worktree/BugReports/Cbc-double-free-187/main.jl:14
gsignal at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
abort at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x7fec773553ed)
unknown function (ip: 0x7fec7735d47b)
unknown function (ip: 0x7fec7735ed2b)
_ZN8ClpModel12gutsOfDeleteEi at /home/lassepe/.julia/artifacts/e97485d553a667a1cb8326bdc10f885eb053590b/lib/libClp.so (unknown line)
_ZN8ClpModelD1Ev at /home/lassepe/.julia/artifacts/e97485d553a667a1cb8326bdc10f885eb053590b/lib/libClp.so (unknown line)
_ZN21OsiClpSolverInterface6crunchEv at /home/lassepe/.julia/artifacts/e97485d553a667a1cb8326bdc10f885eb053590b/lib/libOsiClp.so (unknown line)
_ZN21OsiClpSolverInterface7resolveEv at /home/lassepe/.julia/artifacts/e97485d553a667a1cb8326bdc10f885eb053590b/lib/libOsiClp.so (unknown line)
_ZN8CbcModel7resolveEP18OsiSolverInterface at /home/lassepe/.julia/artifacts/7b3566e62109d63a8e7e1d4d6ea6f721aa0b36f2/lib/libCbc.so (unknown line)
_ZN8CbcModel7resolveEP11CbcNodeInfoiPdS2_S2_ at /home/lassepe/.julia/artifacts/7b3566e62109d63a8e7e1d4d6ea6f721aa0b36f2/lib/libCbc.so (unknown line)
_ZN8CbcModel13solveWithCutsER7OsiCutsiP7CbcNode at /home/lassepe/.julia/artifacts/7b3566e62109d63a8e7e1d4d6ea6f721aa0b36f2/lib/libCbc.so (unknown line)
_ZN8CbcModel9doOneNodeEPS_RP7CbcNodeS3_ at /home/lassepe/.julia/artifacts/7b3566e62109d63a8e7e1d4d6ea6f721aa0b36f2/lib/libCbc.so (unknown line)
_ZN8CbcModel14branchAndBoundEi at /home/lassepe/.julia/artifacts/7b3566e62109d63a8e7e1d4d6ea6f721aa0b36f2/lib/libCbc.so (unknown line)
_Z8CbcMain1iPPKcR8CbcModelPFiPS2_iER19CbcSolverUsefulData at /home/lassepe/.julia/artifacts/7b3566e62109d63a8e7e1d4d6ea6f721aa0b36f2/lib/libCbcSolver.so (unknown line)
Cbc_solve at /home/lassepe/.julia/artifacts/7b3566e62109d63a8e7e1d4d6ea6f721aa0b36f2/lib/libCbcSolver.so (unknown line)
Cbc_solve at /home/lassepe/.julia/packages/Cbc/N9PM4/src/gen/libcbc_api.jl:301 [inlined]
optimize! at /home/lassepe/.julia/packages/Cbc/N9PM4/src/MOI_wrapper/MOI_wrapper.jl:739
optimize! at /home/lassepe/.julia/packages/MathOptInterface/lRbIA/src/MathOptInterface.jl:81 [inlined]
optimize! at /home/lassepe/.julia/packages/MathOptInterface/lRbIA/src/Utilities/cachingoptimizer.jl:285
unknown function (ip: 0x7febe9b25489)
optimize! at /home/lassepe/.julia/packages/MathOptInterface/lRbIA/src/Bridges/bridge_optimizer.jl:348 [inlined]
optimize! at /home/lassepe/.julia/packages/MathOptInterface/lRbIA/src/MathOptInterface.jl:81 [inlined]
optimize! at /home/lassepe/.julia/packages/MathOptInterface/lRbIA/src/Utilities/cachingoptimizer.jl:285
free(): invalid pointer
odow commented 2 years ago

Can you save this to a file called bug.mps

NAME          
ROWS
 N  OBJ
 E  c1
 E  c2
 E  c3
 E  c4
COLUMNS
    MARKER    'MARKER'                 'INTORG'
    x[1]      OBJ       -1
    x[2]      OBJ       -1
    y[1]      c1        1
    y[1]      c3        1
    y[2]      c2        1
    y[2]      c4        1
    MARKER    'MARKER'                 'INTEND'
    x5        c1        1
    x6        c2        1
    x7        c3        1
    x8        c4        1
RHS
    rhs       c1        1
    rhs       c2        0
    rhs       c3        0
    rhs       c4        1
RANGES
BOUNDS
 BV bounds    x[1]
 BV bounds    x[2]
 BV bounds    y[1]
 BV bounds    y[2]
 FR bounds    x5
 FR bounds    x6
 FR bounds    x7
 FR bounds    x8
SOS
 S1 SOS1
    x5        0.4
    x[1]      0.6
 S1 SOS2
    x6        0.4
    x[1]      0.6
 S1 SOS3
    x7        0.4
    x[2]      0.6
 S1 SOS4
    x8        0.4
    x[2]      0.6
ENDATA

and then run

Cbc_jll.cbc() do exe
    run(`$(exe) bug.mps`)
end

This looks like an internal issue in Cbc, so the likelihood of getting something fixed is small. I suggest you use a different solver that supports indicator constraints directly like Gurobi.

lassepe commented 2 years ago

The test case via the bug.mps that you posted above passes without errors.

Thank you for pointing me to Gurobi. I already made the switch to that earlier today and was able to encode my problem there so for me this is not a time-critical bug right now.

odow commented 2 years ago

I don't know then. It's pretty much impossible to debug if we can't reproduce.

Can you simplify the problem any future?

What is ] st -m?

lassepe commented 2 years ago

I tried to reduce the problem further and this seems to be the smallest instance where it happens:

using Cbc: Cbc
using JuMP: JuMP, @constraint, @objective, @variable

model = JuMP.Model(Cbc.Optimizer)
@variable(model, x[1:2], Bin, start = false)
@variable(model, y[1:2], Bin, start = false)

@constraint(model, x[1] => {y[1] == true})
@constraint(model, x[2] => {y[1] == false})

@objective(model, Max, sum(x))
JuMP.optimize!(model)

Interestingly, the issue disappears in this example if I be a single-element-container or a scalar. The full manifest status is the following:

(Cbc-double-free-187) pkg> st -m
      Status `~/worktree/BugReports/Cbc-double-free-187/Manifest.toml`
  [6e4b80f9] BenchmarkTools v1.3.1
  [b99e7846] BinaryProvider v0.5.10
  [fa961155] CEnum v0.4.1
  [49dc2e85] Calculus v0.5.1
  [9961bab8] Cbc v0.9.2 `https://github.com/jump-dev/Cbc.jl.git#master`
  [d360d2e6] ChainRulesCore v1.12.0
  [9e997f8a] ChangesOfVariables v0.1.2
  [523fee87] CodecBzip2 v0.7.2
  [944b1d66] CodecZlib v0.7.0
  [bbf7d656] CommonSubexpressions v0.3.0
  [34da2185] Compat v3.41.0
  [864edb3b] DataStructures v0.18.11
  [163ba53b] DiffResults v1.0.3
  [b552c78f] DiffRules v1.9.1
  [ffbed154] DocStringExtensions v0.8.6
  [f6369f11] ForwardDiff v0.10.25
  [3587e190] InverseFunctions v0.1.2
  [92d709cd] IrrationalConstants v0.1.1
  [692b3bcd] JLLWrappers v1.4.1
  [682c06a0] JSON v0.21.3
  [4076af6c] JuMP v0.22.3
  [2ab3a3ac] LogExpFunctions v0.3.6
  [1914dd2f] MacroTools v0.5.9
  [b8f27783] MathOptInterface v0.10.8
  [d8a4904e] MutableArithmetics v0.3.3
  [77ba4419] NaNMath v0.3.7
  [bac558e1] OrderedCollections v1.4.1
  [69de0a69] Parsers v2.2.2
  [21216c6a] Preferences v1.2.3
  [276daf66] SpecialFunctions v2.1.2
  [90137ffa] StaticArrays v1.3.5
  [3bb67fe8] TranscodingStreams v0.9.6
  [ae81ac8f] ASL_jll v0.1.3+0
  [6e34b625] Bzip2_jll v1.0.8+0
  [38041ee0] Cbc_jll v200.1000.501+0
  [3830e938] Cgl_jll v0.6000.300+0
  [06985876] Clp_jll v100.1700.601+0
  [be027038] CoinUtils_jll v200.1100.400+0
  [d00139f3] METIS_jll v5.1.1+0
  [d7ed1dd3] MUMPS_seq_jll v5.4.1+0
  [656ef2d0] OpenBLAS32_jll v0.3.17+0
  [efe28fd5] OpenSpecFun_jll v0.5.5+0
  [7da25872] Osi_jll v0.10800.600+0
  [0dad84c5] ArgTools
  [56f22d72] Artifacts
  [2a0f44e3] Base64
  [ade2ca70] Dates
  [8bb1440f] DelimitedFiles
  [8ba89e20] Distributed
  [f43a241f] Downloads
  [b77e0a4c] InteractiveUtils
  [b27032c2] LibCURL
  [76f85450] LibGit2
  [8f399da3] Libdl
  [37e2e46d] LinearAlgebra
  [56ddb016] Logging
  [d6f4376e] Markdown
  [a63ad114] Mmap
  [ca575930] NetworkOptions
  [44cfe95a] Pkg
  [de0858da] Printf
  [9abbd945] Profile
  [3fa0cd96] REPL
  [9a3f8284] Random
  [ea8e919c] SHA
  [9e88b42a] Serialization
  [1a1011a3] SharedArrays
  [6462fe0b] Sockets
  [2f01184e] SparseArrays
  [10745b16] Statistics
  [fa267f1f] TOML
  [a4e569a6] Tar
  [8dfed614] Test
  [cf7118a7] UUIDs
  [4ec0a83e] Unicode
  [e66e0078] CompilerSupportLibraries_jll
  [deac9b47] LibCURL_jll
  [29816b5a] LibSSH2_jll
  [c8ffd9c3] MbedTLS_jll
  [14a3606d] MozillaCACerts_jll
  [4536629a] OpenBLAS_jll
  [05823500] OpenLibm_jll
  [83775a58] Zlib_jll
  [8e850b90] libblastrampoline_jll
  [8e850ede] nghttp2_jll
  [3f19e933] p7zip_jll
odow commented 2 years ago

We have the same exact set of packages, including binary dependencies, so it looks like this is specific to your AMD processor. I'd just move on to Gurobi.

lassepe commented 2 years ago

Okay, sounds good. Thank you for your help debugging this :+1: Are you aware of any other open-source solvers that support indicator constraints?

odow commented 2 years ago

Are you aware of any other open-source solvers that support indicator constraints?

No. Note that Cbc also doesn't support indicator constraints, but it does support SOS constraints. We use a reformulation from SOS to indicator.

In general though, you're probably better off formulating an explicit big-M formulation of your MILP, rather than using indicator constraints. Then you can use any MILP solver, and you'll have a bit more control over the numerics: https://jump.dev/JuMP.jl/stable/tutorials/linear/tips_and_tricks/#Trick-2

odow commented 2 years ago

I've reproduced the failure here: https://github.com/jump-dev/Cbc.jl/pull/191

But it is specific to Windows and Linux (but not macOS). I don't have any suggested work-arounds.