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
    There's nothing wrong with asking trivial questions on this site. Please do not be sorry :)2011-09-01
  • 0
    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?2011-09-01
  • 0
    @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.2011-09-02
  • 1
    OK, you seem to know enough basics. Just look at or 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 ...2011-09-02
  • 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