Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Providing custom start value causes double free #187

Open
lassepe opened this issue Feb 13, 2022 · 15 comments
Open

Providing custom start value causes double free #187

lassepe opened this issue Feb 13, 2022 · 15 comments
Labels
Upstream Issue with upstream library

Comments

@lassepe
Copy link

lassepe commented Feb 13, 2022

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
Copy link
Member

odow commented Feb 13, 2022

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
Copy link
Author

lassepe commented Feb 14, 2022

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
Copy link
Member

odow commented Feb 14, 2022

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
Copy link
Author

lassepe commented Feb 14, 2022

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
Copy link
Author

lassepe commented Feb 14, 2022

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
Copy link
Member

odow commented Feb 14, 2022

What is the full error message?

@lassepe
Copy link
Author

lassepe commented Feb 14, 2022

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
Copy link
Member

odow commented Feb 14, 2022

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
Copy link
Author

lassepe commented Feb 14, 2022

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
Copy link
Member

odow commented Feb 14, 2022

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
Copy link
Author

lassepe commented Feb 14, 2022

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
Copy link
Member

odow commented Feb 14, 2022

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
Copy link
Author

lassepe commented Feb 14, 2022

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

@odow
Copy link
Member

odow commented Feb 15, 2022

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 odow added the Upstream Issue with upstream library label Feb 28, 2022
odow added a commit that referenced this issue Mar 2, 2022
@odow
Copy link
Member

odow commented Mar 2, 2022

I've reproduced the failure here: #191

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Upstream Issue with upstream library
Development

No branches or pull requests

2 participants