2
$\begingroup$

In this question, we see how to model boolean logic in $0 - 1$ ILPs. Moving to a relaxation, modelling $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ with $x,y,z \in [0,1]$ with linear constraints is quite simple:

$$z \geq x\\ z \geq y\\ x+y \geq z$$

However, if I want to replace $\vee$ with $\wedge$ in that statement, I'm unable to do this. Can this be done? It seems to me this might imply something about quadratic problems in general, but I'm not familiar with that problem, and I can't prove that it can't be done either. Assuming we could linearize this $\wedge$ relation, would this imply something like polynomial-time equivalence between LP and QP?

Thinking about it geometrically, the set $\{(x,y,z) \in [0,1]^3: (x > 0 \wedge y > 0) \Leftrightarrow z > 0\}$ is equivalent to the unit cube $[0,1]^3$ minus the three faces that intersect the origin, but plus the two edges that emanate from the origin that satisfy $z=0$. This is neither an open nor a closed set. I don't know whether that tells us anything about the applicability of linear programming, but considering I've never come across a linear program with strict inequalities, I suspect it might be a problem.

In fact, strict inequalities can't be allowed in linear programs since

$$\min x\\ x>0$$

has no solution.


@KlausDraeger pointed out that the above constraints and the logical statement with $\vee$ aren't equivalent, and for reasons similar to those that apply to the case with $\wedge$, I suspect we can't find equivalent constraints. The subset of $[0,1]^3$ defined by $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ is also neither open nor closed. I overlooked this because for the purposes I had in mind, it seemed to suffice that the linear constraints implied the truth of the logical statement - which isn't the case, I need equivalence between the set of linear constraints and the logical statement.

(Just in case someone is interested, there is a simpler constraint that also implies the truth of $(x > 0 \vee y > 0) \Leftrightarrow z > 0$, and that's $0.5(x+y) = z$; I could not find a set of constraints equivalent to the logical statement, though.)

$\endgroup$
  • $\begingroup$ You can introduce complementary variables $x'=1-x$, $y'=1-y$ and $z'=1-z$ coding for the negations of $x$, $y$ and $z$. $\endgroup$ – phs Nov 26 '15 at 14:46
  • $\begingroup$ @phs That works if the variables are integers; if they are from the interval $[0,1]$ and I want to distinguish $x = 0$ and $x > 0$, I don't see how to use that. $\endgroup$ – G. Bach Nov 26 '15 at 14:47
  • $\begingroup$ Are you sure that your original encoding works? $(0,1,0.5)$ satisfies $(x>0\vee y>0)\Leftrightarrow z>0$, but not $z>y$. $\endgroup$ – Klaus Draeger Nov 26 '15 at 21:18
  • 2
    $\begingroup$ Is your solution set convex? If not, there is no chance. $\endgroup$ – Yuval Filmus Nov 26 '15 at 22:48
  • 2
    $\begingroup$ The set of vectors satisfying LP constraints is closed. If yours isn't, you can't express it as an LP. $\endgroup$ – Yuval Filmus Nov 27 '15 at 0:45
4
$\begingroup$

A linear program consists of a finite collection of inequalities of the form $\sum_i a_ix_i \leq b_i$. Each such inequality defines a closed convex set, and so their intersection defines a closed convex set. Any domain which is not closed and convex thus cannot be represented using linear programming constraints.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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