2

I am using CPLEX 12.8 to minimize a quadratic binary nonconvex function, according to quadratic function by CPLEX. In particular, my function is the following:

$$ \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{\underset{\bar{f} \neq f}{\bar{f}=1}}^F \sum_{h \in H} \left( D_{f \bar{f}} \cdot \gamma_{i\bar{f}h} \cdot \gamma_{i+1,f,h} \right) $$ over a set $X \neq \varnothing$, where $\gamma_{ifh} \in \{0,1\}$ and $D_{f\bar{f}} > 0$ (distance symetric matrix).

However, when I apply CPLEX in this function (even not knowing if it is convex), the error appears:

Matrix Q must be either symmetric or triangular
error(::String) at error.jl:33
add_qpterms!(::CPLEX.Model, ::Array{Int32,1}, ::Array{Int32,1}, ::Array{Float64,1}) at cpx_quad.jl:17
set(::CPLEX.Optimizer, ::MathOptInterface.ObjectiveFunction{MathOptInterface.ScalarQuadraticFunction{Float64}}, ::MathOptInterface.ScalarQuadraticFunction{Float64}) at MOI_wrapper.jl:727
set(::MathOptInterface.Bridges.LazyBridgeOptimizer{CPLEX.Optimizer}, ::MathOptInterface.ObjectiveFunction{MathOptInterface.ScalarQuadraticFunction{Float64}}, ::MathOptInterface.ScalarQuadraticFunction{Float64}) at bridge_optimizer.jl:718
_pass_attributes(::MathOptInterface.Bridges.LazyBridgeOptimizer{CPLEX.Optimizer}, ::MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}, ::Bool, ::MathOptInterface.Utilities.IndexMap, ::Array{MathOptInterface.AbstractModelAttribute,1}, ::Tuple{}, ::Tuple{}, ::Tuple{}, ::typeof(MathOptInterface.set)) at copy.jl:148
pass_attributes at copy.jl:112 [inlined]
pass_attributes at copy.jl:111 [inlined]
default_copy_to(::MathOptInterface.Bridges.LazyBridgeOptimizer{CPLEX.Optimizer}, ::MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}, ::Bool) at copy.jl:337
#automatic_copy_to#109 at copy.jl:15 [inlined]
automatic_copy_to at copy.jl:14 [inlined]
#copy_to#3 at bridge_optimizer.jl:268 [inlined]
(::MathOptInterface.var"#copy_to##kw")(::NamedTuple{(:copy_names,),Tuple{Bool}}, ::typeof(MathOptInterface.copy_to), ::MathOptInterface.Bridges.LazyBridgeOptimizer{CPLEX.Optimizer}, ::MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}) at bridge_optimizer.jl:268
attach_optimizer(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer,MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}) at cachingoptimizer.jl:149
optimize!(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer,MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.Model{Float64}}}) at cachingoptimizer.jl:185
optimize!(::Model, ::Nothing; bridge_constraints::Bool, ignore_optimize_hook::Bool, kwargs::Base.Iterators.Pairs{Union{},Union{},Tuple{},NamedTuple{(),Tuple{}}}) at optimizer_interface.jl:131
optimize! at optimizer_interface.jl:107 [inlined]
optimize!(::Model) at optimizer_interface.jl:107
top-level scope at Modelo_avancado_graus_dias.jl.jl:139
include_string(::Function, ::Module, ::String, ::String) at loading.jl:1088

I have linerized this function by adding the constraints:

$$ \gamma_{i\bar{f}h} + \gamma_{i+1,f,h} - u_{if\bar{fh}} \leq 1, \quad \quad i=1,...,m,\, \quad f=1,...,F, \quad \bar{f} \in \{1,...,F\} \setminus f, \quad h \in H $$ $$ u_{if\bar{fh}} \leq \gamma_{i\bar{f}h}, \quad \quad i=1,...,m,\, \quad f=1,...,F, \quad \bar{f} \in \{1,...,F\} \setminus f, \quad h \in H $$ $$ u_{if\bar{fh}} \leq \gamma_{i+1,f,h}, \quad \quad i=1,...,m,\, \quad f=1,...,F, \quad \bar{f} \in \{1,...,F\} \setminus f, \quad h \in H $$ where $0 \leq u_{if\bar{fh}} = \gamma_{i\bar{f}h} \cdot \gamma_{i+1,f,h}$. But it was terrible to optimize the linear version: $$ \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{\underset{\bar{f} \neq f}{\bar{f}=1}}^F \sum_{h \in H} D_{f \bar{f}} \cdot u_{if\bar{f}h}.$$

Questions:

  1. How can I fix this?
  2. How can I acess the matrix $Q$?
  3. There is another way to minimize this function by using CPLEX, even I am not knowing if is convex?
SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Angelo Aliano Filho
  • 235
  • 1
  • 3
  • Did you set solutiontarget to 3 (for globally optimal solution) or 2 (for locally optimal solution)? I believe that is necessary, but am not sure whether it's sufficient to avoid the error message you received. – Mark L. Stone Jan 22 '21 at 17:01
  • Either solutiontarget to 3 or 2, the problem is the same

    (Matrix Q must be either symmetric or triangular)

     – Angelo Aliano Filho Jan 22 '21 at 17:09
  • I'm pretty sure the "Q" matrix here refers to $D$. Although $D$ itself is symmetric, the way it is used in the summation is not symmetric. I've never seen a CPLEX error message phrased that way ("must be symmetric or triangular"), so I wonder if that message is coming from JuMP. – prubin Jan 22 '21 at 19:22
  • Your linearization looks correct (give or take whether the upper limit of $i$ is $m$ or $m-1$ in some constraints. Did you declare $u$ to be a binary variable or a nonnegative variable with bounds 0 and 1? – prubin Jan 22 '21 at 19:24
  • My linearization is correct. All is $m-1$. I have declared $u \geq 0$. Works better.But either $u$ binary or $0 \leq u \leq 1$, the problem is the same. – Angelo Aliano Filho Jan 22 '21 at 19:37
  • Yes, I am working in JuMP. – Angelo Aliano Filho Jan 22 '21 at 19:38

1 Answers1

3

The error is coming from an old version of CPLEX.jl.

You should install CPLEX 20.1 and the latest version of CPLEX.jl, which doesn't have this issue.

Oscar Dowson
  • 971
  • 5
  • 6
  • However, when I optmize the quadratic objective and I provide an integer complete feasible solution, CPLEX ignores my solution. CPLEX should not start from this solution? In the linear case is normal. – Angelo Aliano Filho Jan 22 '21 at 21:49
  • Carrying the discussion here: https://discourse.julialang.org/t/optimizing-a-quadratic-binary-function-on-cplex-jump/53800/11 – Oscar Dowson Jan 23 '21 at 22:07