# Equivalence of formulations

I have a simple model such as:

\begin{align}\max&\quad z=X_1+X_2+X_3+X_4\\\text{s.t.}&\quad y_1+y_2+y_3+y_4=2\\&\quad X_1 \leq y_1\\&\quad X_2 \leq y_1+y_2\\&\quad X_3 \leq y_2+y_3\\&\quad X_4 \leq y_1+y_4\\&\quad x,y \in \{0,1\}.\end{align}

The above formulation can be simplified by removing $$X_1$$ variable, $$X_1 \leq y_1$$ constraint and adding $$y_1$$ to the objective function to get:

\begin{align}\max&\quad z=y_1+X_2+X_3+X_4\\\text{s.t.}&\quad y_1+y_2+y_3+y_4=2\\&\quad X_2 \leq y_1+y_2\\&\quad X_3 \leq y_2+y_3\\&\quad X_4 \leq y_1+y_4\\&\quad x,y \in \{0,1\}\end{align}

because

1. The direction of optimization is maximization,
2. Objective function coefficients are $$1$$,
3. $$y$$'s are bounding $$x$$'s and
4. Variables are all binary.

Is it possible to assess any results on the polytopes or (extreme points of the polytopes) of these two formulations, something like "these two polytopes are equivalent as they yield the same optimal solution with this objective function"? What would be your approach to prove the equivalence of these two formulations?

• Are you sure that the problems are equivalent? – independentvariable Dec 19 '19 at 21:29
• – Kevin Dalmeijer Dec 22 '19 at 14:39

This kind of depends on how one defines "equivalent", but in my opinion these formulations are not equivalent. Notice that in the original expression $$X_1$$ can be $$0$$ when $$y_1=1$$. By performing that substitution, you effectively fix that degree of freedom because now your objective will be incremented by $$1$$ if $$y_1=1$$, which was not necessarily the case in the original formulation.
• Thanks for the answer. However, since objective is maximization in the first formulation, if $y_1=1$, then $x_1$ will be forced to become one. So these two formulations will always give the same optimal objective value. Actually, this second formulation is what i get from the presolve of modern solvers (CPLEX, Gurobi). So I give the first formulation, I run presolve and stop there and export the resulting formulation, which is the second formulation. – Evren Guney Dec 20 '19 at 11:43