1
$\begingroup$

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

$\endgroup$
1
+100
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But this $x$ is exactly what I want to maximize, so penalizing for it doesn't really make sense here? $\endgroup$ – HolyMonk Nov 28 at 13:54
  • $\begingroup$ Then in that case use both constraints (yours and this one). $\endgroup$ – Kuifje Nov 28 at 13:55
  • $\begingroup$ 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$ $\endgroup$ – HolyMonk Nov 28 at 13:59
  • $\begingroup$ 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} \}$. $\endgroup$ – Kuifje Nov 28 at 14:14
  • $\begingroup$ 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 $\endgroup$ – HolyMonk Nov 28 at 14:22
0
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – HolyMonk Nov 28 at 16:42
  • $\begingroup$ This does not eliminate the solution $x_i = 1/N$, $x=1$. $\endgroup$ – Kuifje Nov 28 at 16:43

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.