Indicator constraints in IQP?

The problem I’m trying to solve has grown to the point where it requires quadratic constraints and/or objective. When the problem was linear, I had used indicator constraints successfully. After switching to Juniper or Alpine to solve the quadratic problem, I get an exception (“LoadError: Unable to use IndicatorToMILPBridge because element 2 in the function has a non-finite domain…”) during optimize! if I include an indicator constraint. Is this possibe? Am I missing something?

Minimal example:

using JuMP
using HiGHS
using Alpine
using Ipopt
using LinearAlgebra: dot

ipopt = optimizer_with_attributes(Ipopt.Optimizer, "print_level" => 0)
highs = optimizer_with_attributes(HiGHS.Optimizer, "output_flag" => false)

model = Model(optimizer_with_attributes(
			Alpine.Optimizer,
			"nlp_solver" => ipopt,
			"mip_solver" => highs))

@variable(model, x[1:10,1:2], Bin)

values = [3.0, 4.0]

@objective(model, Max, dot(values[1].*x[:,1], values[2].*x[:,2]) )

@constraint(model, x[5,1] --> { sum(x[6:10,1]) <= 1 })

optimize!(model)

Exception:

ERROR: LoadError: Unable to use IndicatorToMILPBridge because element 2 in the function has a non-finite domain: 0.0 + 1.0 MOI.VariableIndex(6) + 1.0 MOI.VariableIndex(7) + 1.0 MOI.VariableIndex(8) + 1.0 MOI.VariableIndex(9) + 1.0 MOI.VariableIndex(10)
Stacktrace:
  [1] error(s::String)
    @ Base .\error.jl:35
  [2] final_touch(bridge::MathOptInterface.Bridges.Constraint.IndicatorToMILPBridge{Float64, MathOptInterface.VectorAffineFunction{Float64}, MathOptInterface.ACTIVATE_ON_ONE, MathOptInterface.LessThan{Float64}}, model::MathOptInterface.Bridges.LazyBridgeOptimizer{Alpine.Optimizer})
    @ MathOptInterface.Bridges.Constraint C:\Users\jeff.emanuel\.julia\packages\MathOptInterface\IiXiU\src\Bridges\Constraint\bridges\indicator_to_milp.jl:200
  [3] _final_touch(bridges::OrderedCollections.OrderedSet{MathOptInterface.Bridges.Constraint.IndicatorToMILPBridge{Float64, MathOptInterface.VectorAffineFunction{Float64}, MathOptInterface.ACTIVATE_ON_ONE, MathOptInterface.LessThan{Float64}}}, model::MathOptInterface.Bridges.LazyBridgeOptimizer{Alpine.Optimizer})
    @ MathOptInterface.Bridges.Constraint C:\Users\jeff.emanuel\.julia\packages\MathOptInterface\IiXiU\src\Bridges\Constraint\map.jl:326
  [4] final_touch(map::MathOptInterface.Bridges.Constraint.Map, model::MathOptInterface.Bridges.LazyBridgeOptimizer{Alpine.Optimizer})
    @ MathOptInterface.Bridges.Constraint C:\Users\jeff.emanuel\.julia\packages\MathOptInterface\IiXiU\src\Bridges\Constraint\map.jl:333
  [5] final_touch
    @ C:\Users\jeff.emanuel\.julia\packages\MathOptInterface\IiXiU\src\Bridges\bridge_optimizer.jl:461 [inlined]
  [6] final_touch
    @ C:\Users\jeff.emanuel\.julia\packages\MathOptInterface\IiXiU\src\Bridges\bridge_optimizer.jl:466 [inlined]
  [7] default_copy_to(dest::MathOptInterface.Bridges.LazyBridgeOptimizer{Alpine.Optimizer}, src::MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}})
    @ MathOptInterface.Utilities C:\Users\jeff.emanuel\.julia\packages\MathOptInterface\IiXiU\src\Utilities\copy.jl:508
  [8] copy_to
    @ C:\Users\jeff.emanuel\.julia\packages\MathOptInterface\IiXiU\src\Bridges\bridge_optimizer.jl:453 [inlined]
  [9] optimize!
    @ C:\Users\jeff.emanuel\.julia\packages\MathOptInterface\IiXiU\src\MathOptInterface.jl:84 [inlined]
 [10] optimize!(m::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.Bridges.LazyBridgeOptimizer{Alpine.Optimizer}, MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}})
    @ MathOptInterface.Utilities C:\Users\jeff.emanuel\.julia\packages\MathOptInterface\IiXiU\src\Utilities\cachingoptimizer.jl:316
 [11] optimize!(model::Model; ignore_optimize_hook::Bool, _differentiation_backend::MathOptInterface.Nonlinear.SparseReverseMode, kwargs::Base.Pairs{Symbol, Union{}, Tuple{}, NamedTuple{(), Tuple{}}})
    @ JuMP C:\Users\jeff.emanuel\.julia\packages\JuMP\R53zo\src\optimizer_interface.jl:448
 [12] optimize!(model::Model)
    @ JuMP C:\Users\jeff.emanuel\.julia\packages\JuMP\R53zo\src\optimizer_interface.jl:409
 [13] top-level scope
    @ C:\dev\monarch-prodsched-service\cmd\prodsched\src\mwe.jl:23
in expression starting at C:\dev\monarch-prodsched-service\cmd\prodsched\src\mwe.jl:23

versioninfo() prints

Julia Version 1.9.2
Commit e4ee485e90 (2023-07-05 09:39 UTC)
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 12 × Intel(R) Core(TM) i7-10850H CPU @ 2.70GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-14.0.6 (ORCJIT, skylake)
  Threads: 12 on 12 virtual cores
Environment:
  JULIA_NUM_THREADS = 12

Pkg.status:

  [fbe9abb3] AWS v1.90.3
  [07493b3f] Alpine v0.5.6
  [336ed68f] CSV v0.10.11
  [861a8166] Combinatorics v1.0.2
  [a93c6f00] DataFrames v1.6.1
⌃ [cd3eb016] HTTP v1.9.15
  [87dc4568] HiGHS v1.7.5
  [b6b21f68] Ipopt v1.5.1
  [682c06a0] JSON v0.21.4
  [0f8b85d8] JSON3 v1.13.2
  [4076af6c] JuMP v1.17.0
  [2ddba703] Juniper v0.9.1
  [b8f27783] MathOptInterface v1.23.0
⌃ [bac558e1] OrderedCollections v1.6.2
  [aea7be01] PrecompileTools v1.2.0
  [856f2bd8] StructTypes v1.10.0
⌃ [5c2747f8] URIs v1.5.0
  [2a0f44e3] Base64
  [ade2ca70] Dates
  [37e2e46d] LinearAlgebra
  [8dfed614] Test
Info Packages marked with ⌃ have new versions available and may be upgradable.

Thanks for any guidance.

Hmm. Let me take a look. I perhaps would have expected this to work, but I can see why it might not because you’re trying to combine quite a few concepts, and Alpine might reformulate the problem in a way that isn’t compatible with our bridge reformulations.

Do you have access to Gurobi? It can solve IQP with indicator constraints.

Note that if you just have quadratic terms between binaries, they can be reformulated as linear:

model = Model()
@variable(model, x[1:10,1:2], Bin)
values = [3.0, 4.0]
# @objective(model, Max, dot(values[1].*x[:,1], values[2].*x[:,2]) )
@variable(model, y[1:10], Bin)
@constraint(model, y .<= x[:, 1])
@constraint(model, y .<= x[:, 2])
@constraint(model, y .>= x[:, 1] .+ x[:, 2] .- 1)
@objective(model, Max, sum(values[1] .* values[2] .* y))
1 Like

Thanks. I don’t have access to Gurobi. I’ll look at reformulating the quadratic components in my actual problem similarly.

1 Like