# Reformulation logical AND in integer programming maximization problem

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.

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.
• 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. – Rob Pratt Nov 25 at 20:21
• 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 – Darkwizie Nov 25 at 20:22