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

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?

The constraint $Cx \nless d$ is can be expressed as a mixed-integer program under certain conditions.
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.
• 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? – Mohammad Fawaz Aug 20 '12 at 20:31
• @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. – David Nehme Aug 20 '12 at 22:24