MIQP: How does Pavito treat convex quadratic functions?


#1

Some Integer Programming solvers, e.g. CPLEX, provide specialised algorithms for convex quadratic constraints and objectives. Does Pavito enable such algorithms for a quadratic objective, or is it treated as a general nonlinear function?


#2

Pavito is for Convex-MINLP, Pajarito is specialized to Convex-MIConicP. If your problem has a QP structure, Pajarito might be the better solver.


#3

Thanks! I have integer problems with linear and convex nonlinear constraints and a convex quadratic objective. Perhaps some combination of Pavito and Pajarito could be best?

Having now studied Pavito’s algorithm.jl in more detail, I understand that quadratics are treated as any nonlinear functions. This could be forgoing some speed. Indeed, using a linear objective produced 50 - 200x speed-ups for different instances, other things being equal. Probably some of these gains could be possible with a quadratic objective if, say, a native MIQP in CPLEX were used.


#4

Got it. This sounds like a good feature to add to Pavito. I would recommend opening an issue in that repo.


#5

Good idea. I guess a quad objective shouldn’t be too hard to add.


#6

If you’re interested in performance, consider writing your convex constraints in conic form. Doing so allows the solver to take advantage of extended formulations and is often more reliable (our paper). I don’t know enough about your use case to say whether it’s a clear win or not, however.

The analogue of your question in Pajarito is addressed by the soc_in_mip option that enables passing second-order cone constraints to the MIP solver instead of outer-approximating them.


#7

I’ve had a look at the paper. It is very interesting, and the approach seems quite promising. I’ll look into applying it. Thank you!