9
$\begingroup$

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?

$\endgroup$
2

1 Answer 1

4
$\begingroup$

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.

While this might or might not give you the same optimal value, there is no guarantee that your active set will be the same (and although it's hard to tell without solving the problem in this case I suspect they will not be).

In terms of the polytope, you created a different polytope which possibly shares one or more vertices with the original one.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Dec 20, 2019 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.