6

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!

Laurent Perron
  • 2,690
  • 1
  • 6
  • 18
Shinra_SGr
  • 75
  • 2
  • 2
    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. – prubin Jun 15 '21 at 18:16
  • Thanks ! From what you are telling me, this constraint would make the problem non convex. – Shinra_SGr Jun 16 '21 at 11:50

1 Answers1

3

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

Nikos Kazazakis
  • 12,121
  • 17
  • 59
  • 1
    Mosek (https://mosek.com) for convex problems could be added to that list. – ErlingMOSEK Jun 16 '21 at 10:47
  • 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. – Shinra_SGr Jun 16 '21 at 11:54
  • You can add LocalSolver in the list of commercial and not free solvers. Somewhat strange, but LocalSolver is now a global optimization solver :-) https://www.localsolver.com – Hexaly Jun 16 '21 at 13:55