**Problem Detail:**

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.)

###### Asked By : G. Bach

#### Answered By : Yuval Filmus

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.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50001

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback