# How to solve mixed integer nonlinear programs?

I'm not a math expert so sorry for possible trivial questions.

I have written this mixed integer nonlinear program (MINLP): \begin{align} \min & \sum_{i \in \mathcal{I}}{\left(\alpha_i+\beta_i\sum_{j \in \mathcal{J}}{z_{ij}^{-1}}+\eta_i\left(\sum_{j \in \mathcal{J}}{z_{ij}^{-1}}\right)^{\gamma_i}\right)x_i} + \sum_{i \in \mathcal{I}}{\sum_{j \in \mathcal{J}}{\delta_{ji}y_{ij}}} + \sum_{i \in \mathcal{I}}{\sum_{j \in \mathcal{J}}{\left(\frac{z_{ij}}{\zeta_i}-1\right)}y_{ij}}\\ \text{subject to} & \notag \\ & \sum_{j \in \mathcal{J}} z_{ij} \le Z_i,\quad i \in \mathcal{I} \\ & \sum_{i \in \mathcal{I}} y_{ij} = 1,\quad j \in \mathcal{J} \\ & y_{ij} \le x_i,\quad i \in \mathcal{I},j \in \mathcal{J} \\ & x_i \in \left\{0,1\right\},\quad i \in \mathcal{I} \\ & y_{ij} \in \left\{0,1\right\},\quad i \in \mathcal{I},j \in \mathcal{J} \\ & z_{ij} \in [0,1]\quad i \in \mathcal{I},j \in \mathcal{J} \\ \text{where} & \notag \\ & \alpha_i,\beta_i,\eta_i \in \mathbb{R},\quad i \in \mathcal{I} \\ & \zeta_i \in \mathbb{R}\setminus\{0\},\quad i \in \mathcal{I} \\ & \delta_{ji} \in \mathbb{R},\quad i \in \mathcal{I},j \in \mathcal{J} \\ & \gamma_i \ge 0\quad i \in \mathcal{I} \\ \end{align}

and now I want to solve. My decision variables are $x_i$, $y_{ij}$, and $z_{ij}$. The other terms are constants.

I really appreciate if someone can guide me in solving it. I've read somewhere that the first step I should perform is a convexity test on objective and constraint functions. I have to compute the Hessian of each function, but how to do it? Then, what next?

Is there any (possibly free) tool that is able to automatically solve this problem for me?

Is a there a good introductory book where I can start?

Thank you very much in advance!

-
There's nothing wrong with asking trivial questions on this site. Please do not be sorry :) –  Srivatsan Sep 1 '11 at 10:12
Do you have any reason why you assume your problem would be easy to solve? Just because you managed to write it as a "mixed integer nonlinear program"? Your constraints are convex, if we neglect the "integer constraints" ($x_i\in\{0,1\}$ is equivalent to the non-convex constraint $x_i(x_i-1)=0$). For fixed $y_{ij}$ and $\gamma_i>=1$, also your target function would be convex. Regarding your book recommendation request, where do you currently stand? Do you know convex functions, linear programming and constrained optimization principles? What do you want to learn? –  Thomas Klimpel Sep 1 '11 at 19:17
@thomas: I did not assume my problem is easy to solve (sorry for this misunderstanding). I read MINLP is a hard topic. I would like to know the way to solve this problem. I also read of many solution techniques, but honestly I don't know what to choose. For what concerns my math knowledge, I am a PhD Student in Computer Science, so I (should) know intermediate math. Indeed, I know what convex functions are and how to solve a linear program with the simplex method. For what regards constrained optimization principles...I give up. Now, I'm trying to compute the Hessian but with some trouble. –  seg.fault Sep 2 '11 at 7:28
OK, you seem to know enough basics. Just look at <or-exchange.com>; or <math.stackexchange.com/questions/4146/…; for book recommendations. There are simpler ways than computing the Hessian to see whether a function is convex. For example, $f(x,y)=xy$ is definitively not convex, so you either have to fix $x_i$ and $y_{ij}$ or $z_{ij}$ in order for you objective function to be convex. The sum of convex functions is convex, so it is sufficient to look at the individual terms. $z^{-1}$ is convex for $z\in(0,1]$, but $-z^{-1}$ is not. So ... –  Thomas Klimpel Sep 2 '11 at 15:18
@thomas: thank you for the hints! I will try to rearrange the problem in order to avoid the product of two decision variables. –  seg.fault Sep 3 '11 at 12:38

There are several techniques to numerically solve MINLP problems (MINLP = Mixed-Integer Non-Linear Programming).

I am most familiar with the research made by Grossmann, et. al. in Carnegie Mellon University - they have an important computational tool called Dicopt (which is available via the GAMS optimization tool). It uses a technique called "Outer Approximation", which proceeds as follows: take a solution to the "relaxed" problem (i.e., one where the integer constraints are allowed to take on continuous values). If the solution to the relaxed problem yields an integer solution, you are done. Otherwise, the solution to the relaxed problem provides a lower-bound to the original problem; add a constraint with that lower bound; relax again; and so on.

In concrete, you can look at the following references:

http://egon.cheme.cmu.edu/software.html Carnegie Mellon Site http://www.minlp.org/resources/index.php#solvers IBM site with links to MINLP solvers http://egon.cheme.cmu.edu/papers.html Grossmann papers

-

There are many good MINLP solvers available such as Bonmin, APOPT, Dicopt, Baron, etc. I'm currently working on the APOPT and APMonitor software. An easy way to solve models using APOPT is through this web-interface. To declare binary or integer variables, you need to preface the variable name with the characters int. There are also MATLAB and Python interfaces available if you are more comfortable with those languages.

-