# Formulation for IP of large OR statement which gives a good linear relaxation

Let $$N$$ be a very large number. I want a good way to program that $$x$$ should be one if and only if one of $$x_i$$ is equal to one.We can write the following Integer Programming problem:

\begin{align*} \max x\\ x \leq \sum_{i=1}^N x_i\\ x_i \in \{0,1\}\\ x\in \{0,1\} \end{align*} Then clearly, we have that $$x$$ will be one whenever at least one $$x_i$$ is equal to one.

My problem with this is that when we take the Linear relaxation of this problem we obtain: \begin{align*} \max x\\ x \leq \sum_{i=1}^N x_i,\\ 0 \leq x_i\\ 0\leq x \end{align*} if now all $$x_i = \frac{1}{N}$$ we still obtain $$x=1$$ while for very large $$N$$ this is extremely inaccurate to what we actually want. I am thus looking for a way to rewrite the IP problem such that the linear relaxation behaves in a way that at least one $$x_i$$ needs to be large in order for $$x$$ to be large.

Notes :

1. This is only a part of a much larger IP problem, therefore I can not simply change the max with a min etc.

2. This $$x$$ is used as follows : I have in my problem an $$x$$ and a $$y$$ : the $$x$$ is $$1$$ when any of the $$x_i$$ is equal to $$1$$ while the $$y$$ is equal to $$1$$ if any of the $$y_i$$ is equal to one. Then we further have a $$z$$ which is one if both $$x$$ and $$y$$ are equal to $$1$$, we have: $$z\leq x$$ $$z\leq y$$ and we want to maximize $$z$$ (indeed then we get $$z=1$$ iff $$x=1$$ AND $$y=1$$).

Approach #1 :

Use Dantzig Wolfe decomposition, which is always at least as tight as the initial formulation. To do this, define the set $$\Omega$$ of combinations that define your "master problem" : $$\Omega := \{(x_1,x_2,...,x_N,x) \in \mathbb{B}^{N+1} \; | \; x=1 \Leftrightarrow \; \exists i\in | x_i=1 \}$$ For example $$(0,...,0) \in \Omega$$, as well as $$(1,...,1)$$, or $$(1,0,1,...,1)$$.

And let $$\lambda_i$$ be a binary variable that takes value $$1$$ if and only if combination $$i \in \Omega$$ is selected.

Your problem can then be formulated as follows : $$\max \; \sum_{i\in \Omega | x =1} \lambda_i$$ subject to $$\sum_{i\in \Omega } \lambda_i = 1 \\ \lambda_i \in \{0,1\}$$ You will certainly have to add the other constraints (that you have not explicitey written in your question).

You can easily generate $$\Omega$$ explicitely beforehand, or dynamically with column generation.

Approach #2 :

Transform the problem into the following minimization problem $$\min z$$ subject to \begin{align*} &x_i \le x \quad \forall i=1,...,N \\ &y_i \le x \quad \forall i=1,...,N \\ &x +y \le 2z \\ &x,y,z \in \mathbb{B} \\ &x_i,y_i \in \mathbb{B} \end{align*}

The constraint $$x+y \le 2z$$ makes sure that when $$x=y=1$$, $$z$$ takes value $$1$$. Otherwise, since you are minimizing $$z$$ it will take value $$0$$.

This formulation is interesting as the solution with $$x_i=1/N$$ and $$x=1$$ is not optimal when relaxing integrality constraints. Indeed, since you are minimizing $$z$$, if $$x_i=1/N$$, $$x$$ will also take value $$1/N$$ (and not $$1$$), in order for $$z$$ to be minimized in the constraint $$x+y\le 2z$$.

• But this $x$ is exactly what I want to maximize, so penalizing for it doesn't really make sense here? – HolyMonk Nov 28 at 13:54
• Then in that case use both constraints (yours and this one). – Kuifje Nov 28 at 13:55
• I don't see how your inequality $x_i \leq x$ is adding anything here : $x$ will automatically maximize itself thus with only the constraint $x \leq \sum_i x_i$ we will always have $x = \sum_i x_i \geq x_i$ – HolyMonk Nov 28 at 13:59
• The solution with $x_i = 1/N$, and $x=1$ is not optimal for the linear relaxation of $\min\{ x \; | \; x_i \le x \quad x,x_i \in \mathbb{B} \}$ which is why the formulation is interesting. You are maximizing $x$, but $x$ cannot be larger than $1$, and $x$ can only take value $1$ if at least one $x_i$ takes value $1$. This is achieved with $\min\{ x \; | \; x_i \le x \quad x,x_i \in \mathbb{B} \}$. – Kuifje Nov 28 at 14:14
• OK I understand what you suggest : replace my IP problem with this minimization. I agree that this could be a possibility. However in my current problem, this $x$ is merely a small part of a much greater optimization problem, therefore I can not simply "change" the maximization to minimization – HolyMonk Nov 28 at 14:22

You can enforce the relationship without depending on the objective or introducing additional variables. Rewriting your logical proposition in conjunctive normal form somewhat automatically yields linear constraints: $$$$x \iff \bigvee_i x_i \\ \left(x \implies \bigvee_i x_i\right) \bigwedge \left(\bigvee_i x_i \implies x\right) \\ \left(\neg x \lor \bigvee_i x_i\right) \bigwedge \left(\neg \bigvee_i x_i \lor x\right) \\ \left(\neg x \lor \bigvee_i x_i\right) \bigwedge \left(\bigwedge_i \neg x_i \lor x\right) \\ \left(\neg x \lor \bigvee_i x_i\right) \bigwedge \left(\bigwedge_i (\neg x_i \lor x)\right) \\ \left(1 - x + \sum_i x_i \ge 1\right) \bigwedge \left(\bigwedge_i (1 - x_i + x \ge 1)\right) \\ \left(x \le \sum_i x_i\right) \bigwedge \left(\bigwedge_i (x_i \le x)\right)$$$$ That is, \begin{align} x &\le \sum_i x_i\\ x_i &\le x &&\text{for all i} \end{align}

• yes, I understand this and why it is true. What I am asking is whether we can change this $x \leq \sum_i x_i$ which makes the inequality more tight in case $x,x_i \in (0,1)$ – HolyMonk Nov 28 at 16:42
• This does not eliminate the solution $x_i = 1/N$, $x=1$. – Kuifje Nov 28 at 16:43