2

Can someone please explain the computational complexity of MINLP and MILP, though both are NP-Hard. What is the advantage of having an MILP formulation over MINLP formulation for a same optimization problem?

I have an MINLP problem of 32 binary integer variables with some nonlinear constraints. I perform exact linearization for some of the constraints and employ piecewise linear approximation for the constraint exact linearization is not possible. But the MINLP formulation now have additional 32 binary integer variables (because of SOS type 2 variables).

Can you please explain which one I should prefer in terms of computational complexity.

Dipankar Narayanan
  • 39

1 Answers1

1

IP problems are generally solved by using a relaxation to the (N)LP formulation. Branch and bound algorithms and cutting plane algorithms utilize a relaxation of some sort.

Non-Linear Programming is much harder than LP, especially when the feasible region is non-convex, as it can be hard to determine which points are actually optimal. So if you have a choice, a MILP is probably a better choice. The constraints will be easier to deal with, and the LP relaxation will give you an LP optimum.

ml0105
  • 14,674