Recommendations for solver and options to solve a MIQP, just looking for a feasible solution

Specific Domains Optimization (Mathematical)
, ,
1

I formulated a mixed-integer quadratic program (MIQP) using MathOptInterface.jl to solve a problem for a student competition. It’s got some continuous variables that are the solution I’m looking for, and I also had to introduce some Boolean variables and lots of constraints. The individual constraints seem pretty simple, though. I’m just looking for a feasible solution, so there’s no minimization or maximization.

I think all the coefficients in my formulation are integers, so I suppose the numerics of the problem are not difficult.

This is my first time modeling either integer optimization or quadratic optimization, however the MOSEK Modeling Cookbook was very helpful in formulating the program.

I’m trying to solve a smaller variant of my MIQP with the SCIP solver, however it seems to be running forever. Are there any other solvers that I should try and see if they’re faster? I’m not paying for a solver, though.

Should I try tweaking some specific solver options?

SCIP reports this about the problem that it’s solving:

presolved problem has 354200 variables (354000 bin, 0 int, 0 impl, 200 cont) and 354708 constraints

Another thing I’m wondering about: suppose a feasible solution doesn’t exist, how long should/could I expect the solver to run before or if it realizes there’s no solution?

Another thing to note is that the smaller problem that’s currently running is quite big nonetheless, with high memory usage. Any tips for decreasing memory usage? The only thing I can think of is to separate the problem into multiple subproblems, solving them one-by-one, and then combining the solutions; however I’d like to avoid splitting the problem into too many subproblems because this seems like it could lead to a very suboptimal final solution.

A question regarding SCIP: how do I tell whether SCIP managed to realize that my problem is convex? As far as I understand all quadratic programs are convex, but I’m not sure if SCIP can see that my program is quadratic?

2

First, MIQP problems are difficult to solve. Especially ones with 354,000 binary variables! The answer you’re looking for is highly problem dependent, so if you can post a reproducible example, people may have suggestions for modeling improvements. Trying to tune the solver is probably of little benefit.

Are there any other solvers that I should try and see if they’re faster? I’m not paying for a solver, though.

You don’t have many options, unfortunately. If you’re an academic, I’d suggest Gurobi. Otherwise it’s mainly SCIP. Other options like Bonmin are likely to also struggle.

As far as I understand all quadratic programs are convex

This is not true. x^2 <= 1 is convex, x^2 >= 1 is non-convex. (The feasible region is x <= -1 and x >= 1. The range x in (-1, 1) is infeasible.) Similarly, min x^2 is convex, max x^2 is non-convex. Also, terms like x * y are non-convex.

2 Likes
3

I think my problem is, in fact, convex (in addition to quadratic). I see that Pajarito.jl is specialized for MICP problems, so I guess it would make sense to try solving with it instead of with SCIP?

4

Can you share the forumlation? There may be some improvements.

You could try Pajarito, but it also depends on the subsolvers you use. Its mainly intended for more general conic problems, rather than MIQP. SCIP is still a good choice.

1 Like