6
$\begingroup$

I would like some solver recommendations to solve a problem with boolean/integer variables, mostly linear constraints but also some quadratic constraints. I also have an objective to minimize which is linear.

I think this kind of problem is called mixed integer quadratically constrained program (MIQCP).

The quadratic constraints are sums of linear terms and one quadratic term which is a constant multiplied by a squared variable.

I would like to know if there is some MIP solvers that can handle this kind of problem (I think CPLEX and Gurobi can).

I would also like to know if a CP (Constraint programming) solver can handle this kind of constraint ? I looked at Google's or-tools CP-SAT solver documentation and it appears that there is a function AddMultiplicationEquality() that allows for variable products.

Thanks for your help!

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ A key question is whether the quadratic constraints keep the continuous relaxation of the problem convex or not. Assuming the constant multiplying the squared variable is positive, a <= constraint would maintain convexity; >= or = would not. $\endgroup$
    – prubin ♦
    Jun 15, 2021 at 18:16
  • $\begingroup$ Thanks ! From what you are telling me, this constraint would make the problem non convex. $\endgroup$
    – Shinra_SGr
    Jun 16, 2021 at 11:50

1 Answer 1

Reset to default
3
$\begingroup$

This is by no means a complete list, but this is some of the best stuff for this mathematical structure:

Open source:

Couenne, SCIP

Commercial and free:

Octeract Engine (our own solver).

Commercial and not free:

Gurobi, Lindo Global, Baron, Antigone, LocalSolver.

You might be able to get a free version of Gurobi (and maybe some of the other non-free ones) if you are an academic.

If your problem is convex, you can also use Bonmin (open source), KNITRO (commercial), or MOSEK (commercial).

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Mosek (mosek.com) for convex problems could be added to that list. $\endgroup$
    – ErlingMOSEK
    Jun 16, 2021 at 10:47
  • $\begingroup$ Thanks for the quick answer ! I will give a try to some of them. I will probably do this in Julia with JuMP since a wrapper exist for most of them. $\endgroup$
    – Shinra_SGr
    Jun 16, 2021 at 11:54
  • $\begingroup$ You can add LocalSolver in the list of commercial and not free solvers. Somewhat strange, but LocalSolver is now a global optimization solver :-) localsolver.com $\endgroup$
    – Hexaly
    Jun 16, 2021 at 13:55

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.