I have an optimization problem that has a linear objective function. The constraints are of the form: $(Ax \leq b) \wedge (Cx \nless d)$. In other words, I have:

\begin{align} \min &f^T x \notag \\ \text{s.t.} &Ax \leq b \\ &Cx \nless d\\ \end{align}

One way to solve the problem would be to decompose the constraint $Cx \nless d$ into $m$ constraints (assuming $C\in R^{m\times n}$): \begin{align} & c_1^T x &\geq &d_1 \\ \vee & c_2^T x &\geq &d_2 \\ & & \vdots & \\ \vee & c_m^T x &\geq &d_m \\ \end{align} and we end up solving $m$ linear programs that are exactly the same except for one constraint that changes from one LP to another. Global optimum is simply the best among the $m$ optimums obtained.

Can anyone think of a faster way to perform this optimization? What about convex relaxation? How would I relax my problem to a single linear program? How good a convex relaxation solution would be?


1 Answer 1


The constraint $Cx \nless d$ is can be expressed as a mixed-integer program under certain conditions.

\begin{eqnarray} C_i x - M_i y_i &\ge& d_i \hspace{0.3 in} \forall i \in I \\ \sum_{i \in I} y_i &\le& m-1 \\ y_i &\in& \{ 0, 1 \} \hspace{0.2 in} \forall i \in I \end{eqnarray}

Where $I = \{1, \ldots m\}$, $M_i$ is a constant that represents an a-priori upper-bound on $c_i x$. If A good mixed-integer solver should do better than solving the $m$ separate continuous problems.

  • $\begingroup$ Thank you. I am using MOSEK and I hope I can get fast results because $m$ can be very high and I have to repeat the process several times. What do you think convex relaxation would do in this case? If we allow $y_i$ to be real, we obviously get a lower bound. From what I see, the relaxed space boils down to simply $Ax \leq b$. Is that right? $\endgroup$ Commented Aug 20, 2012 at 20:31
  • 2
    $\begingroup$ @Fawaz Depending on the problem, you might be able to or need to do better than just $Ax \le b$. The smaller you can make the $M_i$, the better. It is ok to eliminate a-priori suboptimal solutions. $\endgroup$ Commented Aug 20, 2012 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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