2
$\begingroup$

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?
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – Mark L. Stone Jan 22 at 17:01
  • $\begingroup$ Either solutiontarget to 3 or 2, the problem is the same (``` Matrix Q must be either symmetric or triangular ```) $\endgroup$ – Angelo Aliano Filho Jan 22 at 17:09
  • $\begingroup$ 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. $\endgroup$ – prubin Jan 22 at 19:22
  • $\begingroup$ 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? $\endgroup$ – prubin Jan 22 at 19:24
  • $\begingroup$ 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. $\endgroup$ – Angelo Aliano Filho Jan 22 at 19:37
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Angelo Aliano Filho Jan 22 at 21:49
  • $\begingroup$ Carrying the discussion here: discourse.julialang.org/t/… $\endgroup$ – Oscar Dowson Jan 23 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.