3
$\begingroup$

I am trying to work on a scheduling problem based on its polyhedron reformulations. For that, I would like to reformulate a BigM model into its equivalent C-hull formulation. The transforming map is depicted in the following picture:

enter image description here

Now, the first thing coming to mind is that, Is it proven that always a C-hull formulation has better relaxation than a BigM or time-indexed formulation? Also, can we infer this may lead to reducing the solving process in a MIP?

Suppose there is a simple scheduling as of the form:

\begin{align*} \text{minimize} \quad & s_1 + s_2 \\ \text{subject to} \quad & LB \leq s_1 \leq UB \\ \ & LB \leq s_2 \leq UB \\ \ & (s_1 \geq s_2+\alpha) \lor (s_2 \geq s_1+\beta)\\ & s_1, s_2 \geq 0. \end{align*}

It's linearized as:

\begin{align*} \text{minimize} \quad & s_1 + s_2 \\ \text{subject to} \quad & LB \leq s_1 \leq UB \\ \ & LB \leq s_2 \leq UB \\ \ & s_1 - s_2 + (M+\beta)y_1 \leq M \\ \ & s_2 - s_1 + (M+\alpha)y_2 \leq M \\ \ & y_1 + y_2 = 1 \\ & s_1, s_2 \geq 0, y_1, y_2 \in \{0,1\}. \end{align*}

and its C-hull equivalent would be:

\begin{align*} \text{minimize} \quad & s_1 + s_2 \\ \text{subject to} \quad & s_1 = w_1 + w_2 \\ \ & s_2 = w_3 + w_4 \\ \ & LB \leq s_1 \leq UB \\ \ & LB \leq s_2 \leq UB \\ \ & y_1 + y_2 = 1\\ \ & w_1 - w_3 + \beta y_1 \leq 0\\ \ & w_4 - w_2 + \alpha y_2 \leq 0\\ \ & w_i - UBy_j \leq 0 ,\ \forall i \in I, j \in J\\ & s_1, s_2 \geq 0, y_j \in \{0,1\}, w_i \geq 0. \end{align*}

The second question is, is my transformation correct? (I can take the same objective value, but I would like to ensure I am not being lucky). Also, I am unsure what exactly the $w_1, w_2$ means.

I have tried to solve a large instance of the above formulation. In that case, it seems the BigM model has a better performance against the C-hull formulation. Maybe it is back to the internal mechanism of the modern MIP solvers to deal with BigM formulation rather than whose C-hull model! May I have your insight?

$\endgroup$
3
  • $\begingroup$ Cross-posted: math.stackexchange.com/questions/4945400/… $\endgroup$
    – RobPratt
    Commented Jul 13 at 15:27
  • 2
    $\begingroup$ Your proposed equivalent does not even mention $LB$, $UB$, $\alpha$, or $\beta$. $\endgroup$
    – RobPratt
    Commented Jul 13 at 15:28
  • $\begingroup$ Dear @RobPratt, thanks. Actually, I missed adding the first two constraints from the first model into the second. Also, $\alpha $ and $\beta$ are two constants and are corresponding to $m_1, m_2$ in the second model. $\endgroup$
    – A.Omidi
    Commented Jul 13 at 20:07

1 Answer 1

1
$\begingroup$

Rewrite as \begin{align} &\text{minimize} & s_1 + s_2 \\ &\text{subject to} & (s_2 - s_1 \le -\alpha) &\lor (s_1 - s_2 \le -\beta) \\ && \text{LB} \le s_i &\le \text{UB} \end{align} Note that I have omitted $s_i \ge 0$, which is redundant to $\text{LB} \le s_i$.

The big-M formulation is \begin{align} &\text{minimize} & s_1 + s_2 \\ &\text{subject to} & s_2 - s_1 &\le -\alpha + M_1 (1-\lambda_1) \\ && s_1 - s_2 &\le -\beta + M_2 (1-\lambda_2) \\ && \text{LB} \le s_i &\le \text{UB} \\ && \lambda_1 + \lambda_2 &= 1 \\ && \lambda_j &\in\{0,1\} \end{align}

The convex hull formulation is \begin{align} &\text{minimize} & s_1 + s_2 \\ &\text{subject to} & s_1 &= t_{1,1} + t_{1,2} \\ && s_2 &= t_{2,1} + t_{2,2} \\ && t_{2,1} - t_{1,1} &\le -\alpha \lambda_1 \\ && t_{1,2} - t_{2,2} &\le -\beta \lambda_2 \\ && \text{LB} \lambda_j \le t_{i,j} &\le \text{UB} \lambda_j \\ && \lambda_1 + \lambda_2 &= 1 \\ && \lambda_j &\in\{0,1\} \\ && t_{i,j} &\ \text{free} \end{align} The interpretation is that $s_i=t_{i,j}$ when $\lambda_j=1$. This formulation is not the same as what you proposed, even if you rename $\lambda_j$ as $y_j$ and the $t_{i,j}$ as $w_1,w_2,w_3,w_4$.

$\endgroup$
13
  • $\begingroup$ Dear Rob, thanks for your reply. I just updated my question. Would you please, elaborate more on what you mentioned as This formulation is not the same as what you proposed, even if you rename λj as yj and the ti,j as w1,w2,w3,w4? Both seem very similar except in the defining LB on $w_i$ as I left it on default. $\endgroup$
    – A.Omidi
    Commented Jul 14 at 7:04
  • $\begingroup$ Also, may I have your insight regarding my other questions? $\endgroup$
    – A.Omidi
    Commented Jul 14 at 7:07
  • $\begingroup$ Check the signs of $w_i$ in your inequalities. $\endgroup$
    – RobPratt
    Commented Jul 14 at 11:10
  • $\begingroup$ As the LB equal to zero is a valid LB for the original variables $s_1,s_2$, I defined the $w_i \geq 0$. Do you think it yields wrong results and I must define them as ($w_i = free$)? $\endgroup$
    – A.Omidi
    Commented Jul 14 at 13:53
  • 1
    $\begingroup$ Your big-M formulation is correct but is weaker than the screenshot. In particular, $\beta$ and $\alpha$ need not be multiplied by the $y_j$ variables. Now that you have interchanged $\alpha$ and $\beta$, your convex hull formulation is getting closer, but you have too many inequality constraints. The last one should not be $\forall i, \forall j$, which would yield $8$ inequalities instead of $4$. $\endgroup$
    – RobPratt
    Commented 2 days ago

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.