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?

Improve this question
$\endgroup$
4
  • $\begingroup$ can anyone of you tell me how can i set the Cplex solver to handle non convex quadratic constraints?? $\endgroup$
    – Anouar Nahi
    Apr 1 at 16:38
  • $\begingroup$ @AnouarNahi This might help: ibm.com/docs/en/icos/22.1.1?topic=qcp-changing-problem-type-in. $\endgroup$
    – prubin ♦
    Apr 1 at 17:29
  • $\begingroup$ @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. $\endgroup$
    – Mark L. Stone
    Apr 1 at 17:43
  • $\begingroup$ 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 $\endgroup$
    – Anouar Nahi
    Apr 4 at 8:00

4 Answers 4

Reset to default
13
$\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"

Improve this answer
$\endgroup$
10
  • $\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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 22:03
4
$\begingroup$

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

Improve this answer
$\endgroup$
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.

Improve this answer
$\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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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