# CPLEX non-convex Quadratic Programming algorithms

CPLEX solves non-convex quadratic problems to global optimality with a global optimality option (in version 12). The relevant pages are this and this. I benchmarked many solvers, and see that CPLEX is by far the best solver in this problem. I am curious about the algorithms they use. Are these generally hidden, or can I find more about this?

• can anyone of you tell me how can i set the Cplex solver to handle non convex quadratic constraints?? Commented Apr 1, 2023 at 16:38
• @AnouarNahi This might help: ibm.com/docs/en/icos/22.1.1?topic=qcp-changing-problem-type-in.
– prubin
Commented Apr 1, 2023 at 17:29
• @Anouar Nah You can't set the CPLEX solver to accept non-convex quadratic constraints. CPLEX only allows non-convex quadratics in the objective function, not in constraints, which CPLEX requires to be convex. Starting with Gurobi 9.0 (released Nov 2019),, Gurobi allows non-convex quadratics in objective function and constraints, and attempts to solve them to global optimality. Commented Apr 1, 2023 at 17:43
• HI guys thanks for your answers, in that case what are my options then ? given that the non convex constraints are a must in the model Commented Apr 4, 2023 at 8:00

The best publicly available CPLEX global QP algorithm description I am aware of is the tutorial presentation by Ed Klotz of IBM at the March 2018 INFORMS Optimization conference.

Performance Tuning for Cplex’s Spatial Branch-and-Bound Solver for Global Nonconvex (Mixed Integer) Quadratic Programs

ABSTRACT:

MILP solvers have been improving for more than 40 years, and performance tuning tactics regarding both adjusting solver strategies and model formulations have evolved as well. State-of-the-art global nonconvex MIQP solvers have improved dramatically in recent years, but they lack the benefit of 40 years of evolution. Also, they use a broader notion of branching that can create different performance challenges. This talk will assess the effectiveness of existing MILP tuning tactics for solving nonconvex MIQPs, as well as consider more specific strategies for spatial branching. It will also examine in detail some tightening strategies specific to nonconvex MIQPs involving bilinear terms of binary variables and their associated linearizations.

Note: If you haven;t already done so, it might be worthwhile benchmarking BARON (which unlike CPLEX, only globally optimizes) on non-convex (possibly mixed-integer) QPs.

Update: As follow-up to the matter discussed in the comments to this answer of the different default values in BARON of epsR, the relative convergence tolerance: Going forward, the default value of epsR will be 1e-9 in all BARON interfaces.

Update 2: The newly released BARON 19.7.13 "Changed default value of epsr (relative optimality tolerance) to 1e-9 to guarantee better solutions"

• It's a great source. Thank you so much! I tried BARON, but it is very slow. I see that it finds the global optimum at a reasonable time, but certificates the global optimality very late. Although I use it via Yalmip without giving any special options. Maybe there are some important options, do you know any? Commented Jun 16, 2019 at 1:21
• epsa and epsr are absolute and relative gap tolerances for BARON in YALMIP. Default values in YALMIP are 1e-6 and 1e-9 respectively, which are rather stringent. Increasing them might make termination much quicker. Default in "native" BARON for epsR is 1e-4, not 1e-9. So I'm guessing the default epsr = 1e-9 in YALMIP is killing you. Commented Jun 16, 2019 at 1:31
• YALMIP creates the baron options through barons own function baronset, so it is not YALMIP selecting these values. Commented Jun 16, 2019 at 5:53
• Indeed you are correct @Johan Lofberg. I am inquiring and will report back on this, as it seems the baronset, and hence YALMIP, default for epsR of 1e-9 is rather small. My guess is it was intended to be 1e-6. Commented Jun 16, 2019 at 9:08
• @JohanLöfberg I meant I am just using optimize command with 'solver', 'baron' without any extra baron options. Commented Jun 16, 2019 at 22:03

When you call optimize without any options set, the default values will be used, and those are created by the function baronset.

In addition to the reference of Mark, you can have a look at his technical report:

Solving standard quadratic programming by cutting planes. by P. Bonami, A.Lodi, J. Schweiger, A. Tramontani

Since the authors are involved with the development of CPLEX, I guess this paper is relevant to your question.

Be aware that also Gurobi will soon have support for binary non convex quadratic problem. You can have a look at the slides of Tobias Achterberg at CPAIOR 2019 last June:

Products in Mixed Integer Programming

In both cases, it looks that a careful combination of cutting planes and spatial branch-and-bound is the winning approach.

A non-convex QP is solved to global optimality by generating the McCormick relaxation of the objective and using that relaxation in a branch-and-bound framework. For non-convex MIQPs, we also introduce integer cuts during the branch-and-bound procedure (branch-and-cut).