When should we avoid linearizing a quadratic term?

Question

Some solvers like Gurobi can handle mixed-integer quadratically-constrained quadratic models regardless of their nonconvexity. I have some experience that Gurobi can handle instances of the max $k$-cut problem with nonconvex objective function better than the linearized version of the formulation.

My question is, when should we avoid linearizing those quadratic terms?

Answer 1

I have a problem where all the products over {-1,0,1}. I can rephrase the products in terms of binary variables. This turned out to be way more performant and interacted better with symmetry breaking constraints i introduce. In general if there exist a non trivial linear relaxation which is tight, use that linear relaxation. Using linear relaxations also allows you to run it on others solvers which can be faster for certain problems or lead to insights about the problem.

You have to try both, see what works better. In case there is heterogeneity in your model, you might even want to try a combinations of both. As rules of thumb:

• If it is a product of more than one continuous variable always leave those to Gurobi.
• Tighter bounds are particularly valuable in the objective, so linearising might hurt performance by making the branch and bound tree a lot bigger
• If finding an initial integer valued solution with not linearized products takes a long time, remove the objective if it is non linear and consider trying different linearizations of constraints involving products of integers of bounded range. Use this solution (or a feasible solution found by it) to warm start the non-linear solve.
• Mixed Integer solvers are fickle beasts. If the domain changes, always revisit your assumption. While you can almost always trust the result, you have to verify the performance if the compute is expensive enough to be worth your time.

Answer 2

The answer is that no-one knows - that's largely why quadratic programming is hard in practice.

A solver is such a chaotic system that it's no use even trying to predict how such modelling decisions will affect the outcome. Most of the time something works we don't really know why.

My advice is to never linearise yourself prematurely, as by doing so you are removing information from your model that the solver might be able to exploit. One exception to this rule is if your linearisation is not exact (e.g. you are outer approximating a continuous term). In this case, you are actually telling the solver that you are ok with sacrifising accuracy for that term, which can in turn improve performance. This is not a decision that the solver can make for you, so it needs to come from the modeller.

Generally speaking though, high performance solvers are advanced enough that linearising manually should only really be done as a very last resort. I generally advice users to first play around with solver settings before making any such changes to their models.

Note the "high performance" here - if you are using a less advanced solver, the situation is different and it becomes more likely that your linearisation might pay off.