1
$\begingroup$

Consider a polytope in $\mathbb{R}^n$ inside the unit cube given by

$$ A\vec{x} \le b \\ 0 \le x_i \le 1 $$

And consider one particular row of $A$ that we consider as a cut $A_ix \le b_i$. I am interested in the behavior of this cut AFTER branching on two variables $x_0, x_1$.

In particular we have the following 4 systems that result and I assume these 4 systems are all feasible (this is a very important assumption):

$$ \begin{matrix} \text{I}: \begin{matrix} Ax \le b \\ (x_0, x_1) = (0,0) \end{matrix} & \text{II}: \begin{matrix} Ax \le b \\ (x_0, x_1) = (1,0) \end{matrix} \\ \\ \text{III}: \begin{matrix} Ax \le b \\ (x_0, x_1) = (0,1) \end{matrix} & \text{IV}: \begin{matrix} Ax \le b \\ (x_0, x_1) = (1,1) \end{matrix} \end{matrix} $$

Now the cut $A_i x \le b_i$ can have the following behavior:

  1. It is tight for NONE of these four systems.
  2. It is only tight for 2 directly adjacent systems (ex: (I,II) or (II, IV) )
  3. It is only tight for some 3 systems
  4. It is tight for all 4 systems
  5. It is only tight for (I,IV) but not the others
  6. It is only tight for (II, III) but not the others.

I am wondering whether (5) or (6) can ACTUALLY happen. I have suspicions that these are not actually possible and just 1-4 describe all possible ways the cut can be tight.

Can anyone describe a specific polytope where either (5) or (6) is true OR can it be proven that (5) and (6) cannot occur.

Naively if I dropped the all 4 systems are feasible then perhaps the cut could have been $x-y \le 0$.

$\endgroup$
6
  • 1
    $\begingroup$ How are you using the term "tight" here? Do you satisfied as an equality by at least one point? $\endgroup$
    – prubin
    Commented Jul 6 at 3:00
  • $\begingroup$ I think i'm mixing up my notation here. Tight for me means non-redundant. I.E. you cannot remove this inequality without changing the polytope. $\endgroup$ Commented Jul 6 at 3:11
  • $\begingroup$ Actually we can go with the standard notion of tight. My question is still preserved. So lets allow tight to mean "equality satisfied by at least one point" as you nicely put it. $\endgroup$ Commented Jul 6 at 3:15
  • 1
    $\begingroup$ @SidharthGhoshal, finding a tight cut is equivalent to finding an inequality that defines a facet of the original polyhedron. (Please, see this link). Also, about the cut be tight across a diagonal in a polytope? it seems the disjunctive cuts may do what you want. E.g. what you proposed as ($x=y$) can be written as ($x \leq y \lor x \geq y$). The same thing can be held for ($1-x = y$). $\endgroup$
    – A.Omidi
    Commented Jul 6 at 9:08
  • 1
    $\begingroup$ @A.Omidi In this case, based on the response to my question above, I don't think we can assume the cut need be facet-defining. If the hyperplane corresponding to the cut is tangent to the feasible region at one vertex, it meets the OP's criterion of equality at one point without defining a facet (the vertex already being defined by other constraints). $\endgroup$
    – prubin
    Commented Jul 6 at 16:30

1 Answer 1

1
$\begingroup$

I'll use $(x,y,z)$ for the coordinate system in three dimensions. Consider the polytope $P$ defined by the following. \begin{align*} x-y+z & \le1\\ -x+y+z & \le1\\ \frac{1}{2}x-\frac{1}{2}y+z & \le1\\ x,y,z & \in\left[0,1\right] \end{align*}

The third inequality is the ``cut''. The four subsystems are all feasible since $P$ contains (0, 0, 0), (1, 0, 0), (0, 1, 0) and (1, 1, 0). The third inequality is satisfied as an equality by (0, 0, 1) and (1, 1, 1), both of which are feasible. If $x=1$ and $y=0,$ the cut would be binding when $z=1/2,$ which violates the first constraint. If $x=0$ and $y=1,$ the cut would be binding at $z=3/2,$ which violates the upper bound on $z.$ So this demonstrates option 5.

$\endgroup$

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.