14
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

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"

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – independentvariable Jun 16 '19 at 1:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Jun 16 '19 at 1:31
  • 3
    $\begingroup$ YALMIP creates the baron options through barons own function baronset, so it is not YALMIP selecting these values. $\endgroup$ – Johan Löfberg Jun 16 '19 at 5:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Jun 16 '19 at 9:08
  • $\begingroup$ @JohanLöfberg I meant I am just using optimize command with 'solver', 'baron' without any extra baron options. $\endgroup$ – independentvariable Jun 16 '19 at 22:03
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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).

$\endgroup$

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.