Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I have a minimization problem of the form $$ \min_{n\in N} \sum_i A_i n_i +\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^2 $$ where $A_i\geq 0$ and $B_{ij}\geq 0$ for all $i,j$. This problem can be written as a convex quadratic integer program.

What are the standard algorithms to solve these problems numerically? Are they guaranteed to find a global solution? How fast are they?

  • $\begingroup$ This seems like a misnomer to me. According to Boyd and Vandenberghe, a Convex Optimization problem is an optimization problem whose domain is a convex set. But an integer programming problem is one where the solutions must be integers. The set of integers is not convex. $\endgroup$ – NicNic8 Jan 10 at 20:16
  • 2
    $\begingroup$ Yes, I know that using the word "convex" here is a bit tricky but several people in the literature use convex in this way for integer programs. $\endgroup$ – user_lambda Jan 10 at 20:17
  • 2
    $\begingroup$ Typically, a mixed integer nonlinear programming problem (MINLP) whose continuous relaxation is convex is referred to as a "Convex MINLP" This is terminology that's been around for at least 25 years... $\endgroup$ – Brian Borchers Jan 10 at 20:45
  • 1
    $\begingroup$ Your terminology is fine. You would think it might be possible to exploit the fact that it is unconstrained (that is, beyond the integrality constraints), but I'm not seeing it. $\endgroup$ – Michael Grant Jan 12 at 2:56

Typically, you'd use a branch and bound algorithm to solve this problem and obtain a globally optimal solution if the problem isn't unbounded. This does require worst-case exponential time.

Several commercial LP/QP packages have support for solving these MIQP problems.

  • $\begingroup$ Thanks. I was hoping that simpler algorithms might work given the nice properties of the problem but maybe that's not the case. $\endgroup$ – user_lambda Jan 10 at 21:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.