0
$\begingroup$

Suppose we have variables $x_1,x_2,y \in \{0,1\}$ such that $y=1$ if and only if $x_1 = x_2 = 1$ and we want maximize the value of $y$. I know that this reduces to the following Integer programming problem: \begin{align*} \max y&\\ x_1,x_2, y \in \{0,1\}\\ y \leq x_1\\ y\leq x_2.\\ \end{align*}

The linear relaxation of this problem is then given by: \begin{align*} \max y&\\ 0\leq x_1,x_2, y \leq 1\\ y \leq x_1\\ y\leq x_2.\\ \end{align*} Now in the relaxation we will simply get $y=\min\{x_1,x_2\}$. I was wondering whether there is some alternative formulation for the Integer Program such that, when we take the linear relaxation of the problem, the solution $y$ is stricly smaller than $\min\{x_1,x_2\}$. See also here for more information about reformulations.

$\endgroup$
1
$\begingroup$

This reformulation relies on the optimality condition that $y$ is maximized. The constraints enforce only $y\le \min(x_1,x_2)$, and $y< \min(x_1,x_2)$ is feasible but not optimal. If your problem has a different objective, you can instead impose an additional linear constraint $y \ge x_1 + x_2 - 1$ to enforce $(x_1=1 \land x_2=1) \implies y=1$, as described here.

$\endgroup$
  • $\begingroup$ I am looking for an alternative formulation such that the difference between the optimal solution for the linear relaxation and the integer program is smaller. $\endgroup$ – Darkwizie Nov 25 at 20:14
  • $\begingroup$ The constraints $y\le x_1,y\le x_2,y\ge x_1+x_2-1,y\ge 0$ form the convex hull of the feasible points $\{(x_1,x_2,y)\in\{0,1\}^3:y=x_1 x_2\}$, so you won't find a tighter formulation. $\endgroup$ – Rob Pratt Nov 25 at 20:21
  • $\begingroup$ Important note: the $x_i$ may also change value by the rest of the integer programming problem, this is only a small part of a much bigger problem. The $y$ only appears here $\endgroup$ – Darkwizie Nov 25 at 20:22
  • $\begingroup$ But so I figure the answer is: no $\endgroup$ – Darkwizie Nov 25 at 20:23
  • $\begingroup$ I understand the reasoning, thanks for the reply. $\endgroup$ – Darkwizie Nov 25 at 20:33

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.