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?