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

Question

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

Answer 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$.

Answer 2

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: \begin{equation} 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) \end{equation} That is, \begin{align} x &\le \sum_i x_i\\ x_i &\le x &&\text{for all $i$} \end{align}