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!
Best Answer
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