Linear Programming with constraints of the form $Cx \nless d$ where $C\in R^{m\times n}$

Question

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?

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.