# Minimizing a quadratic binary nonconvex function by CPLEX

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
_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



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?
• 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. 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 ) 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. 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? 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. Jan 22 '21 at 19:37