8
$\begingroup$

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!

  • 0
    @thomas: thank you for the hints! I will try to rearrange the problem in order to avoid the product of two decision variables.2011-09-03

2 Answers 2

3

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

1

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.