Providing custom start value causes double free

[lassepe]

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]

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]

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]

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]

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]

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]

What is the full error message?

[lassepe]

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]

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]

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]

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]

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]

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]

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

[odow]

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