How/when can we use MINLP engines instead of linearizing MP models?

Question

Nowadays, mathematical programming solvers have been frequently used to solve lots of practical/academic problems. Many of these might be interpreted as a MIP or MINLP to represent a specific problem (e.g. VRP variants). Some of the nonlinear terms in these models contain:

• Product of two or more different variables
• Using either min, max or abs functions in the objective, constraints or both.
• Applying some mathematical functions, etc.

Also, there are some linearizing tricks to change these nonlinear terms into whose linear forms. For example, the multiplier of two or more binary variables.

My questions are:

• Is there any reasonable way to use MINLP engine instead of MIP to solve such problems?
• May these linearizations cause to increase the solving time?
• Is there any way to speed up the solving time by using both engines?

Answer 1

I think by MIP you mean MILP which stands for mixed integer linear program(ming).

Q1. Is there any reasonable way to use MINLP engine instead of MIP to solve such problems?

Of course you can use a MINLP solver, but such solvers may eventually use some form of linearization. I would first try to linearize a non-linear formulation (if possible) and then use a linear solver to solve the linear formulation. The reason is that modern linear solvers are quite enhanced and optimized for solving linear programs compared to non-linear solvers and you know what linear formulation is actually being solved. If a linear solver/reformulation is not an option for any reason, using the MINLP solvers is the only option. Note that some MILP problems (e.g., the Minimum Sum-of-Squared Clustering) can be represented as pure continuous but non-linear formulations. For such problems, using a non-linear solver may prove better (in finding feasible or optimal solutions) than a modern linear solver.

Q2. May these linearizations cause to increase the solving time?

It depends on 1) the problem itself, 2) the linearization technique (there are sometimes a number of different ways) and 3) the solver used to solve the linearized problem. So anything is possible.

Q3. Is there any way to speed up the solving time by using both engines?

Depending on the problem, it is possible. For example, you may be able to reformulate the problem and decompose it into the so-called master problem and subproblem(s). In a scenario, the master problem is linear while the subproblem(s) are non-linear problems that can be solved by specialized algorithms (or MINLP solvers) more efficiently. In addition, modern MILP solvers are based on LP-based branch and bound (B&B) in which an LP is solved at each node of the B&B tree. You may be able to employ the same strategy, but solve a non-linear problem at each node (instead of an LP) to obtain stronger bounds. For example, semidefinite programs usually provide bounds that are stronger than their LP-relaxation counterparts (again, check the Minimum Sum-of-Squared Clustering as an example).