4
$\begingroup$

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?
$\endgroup$
5
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the great explanation. Please let's say, in the many of papers in the scheduling field I have seen for example the product of two continues variables and the authors use for example the MacCormick linearization to do that. Implementing such methods need skill and tricky. My question is why shouldn't we use a MINLP solver to do that automatically just for worry about the solving time? $\endgroup$ – A.Omidi Oct 25 at 13:15
  • 1
    $\begingroup$ @A.Omidi One of the reasons as to why MINLP solvers exist is that the users (e.g., practitioners) do not re-implement (or worry about) the complex procedures performed under the hood. There is no gurantee your purpose-built algorithm solves the problem faster than a MINLP solver. If you have a MINLP solver, then why not use it? You can start with the solver, and if you are not happy with the result, you can try developing your own algorithm. For research, I would always compare my own algorithm with the existing solvers to evaluate the quality of their solutions as well as their run times. $\endgroup$ – Opt Oct 25 at 22:31
  • $\begingroup$ Many thanks for your hints. :) $\endgroup$ – A.Omidi Oct 26 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.