4
$\begingroup$

I have the following model \begin{align}\max&\quad B_{1} + B_{2}\\\text{s.t.}&\quad 0 \leq B_{1} \leq c_{1}\cdot Y_{1} \\&\quad 0 \leq B_{2} \leq c_{2}\cdot Y_{2} \\&\quad \end{align} where $B_{1}, B_{2}$ are reals, $Y_{1}, Y_{2}$ are binary, and $c_{1}, c_{2}$ are positive constants.

Is the following transformation of advantage when thinking about speeding up B&B?

\begin{align}\max&\quad B_{1} + B_{2} - M_{1} - M_{2}\\\text{s.t.}&\quad B_{1} + M_{1} = c_{1}\cdot Y_{1} \\&\quad B_{2} + M_{2} = c_{2}\cdot Y_{2} \\&\quad\end{align} where $B_{1}, B_{2},M_{1}, M_{2}$ are reals, $Y_{1}, Y_{2}$ are binary, and $c_{1}, c_{2}$ are positive constants.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Let $M_1$ be negative. Now we improve the objective and violate the original inequality by as muih as we want. How is that equivalent? Even if $M_1$ is constrained to be nonnegative, then what happened to $0 \le B_1$, and how is penalizing the slack ($M_1$)in the objective a "proper" thing to do? Of course, same with $M_2, B_2$. $\endgroup$
    – Mark L. Stone
    Commented May 2, 2020 at 12:25
  • $\begingroup$ You cannot get your exact model by eliminating the given inequalities using the equalities proposed by you. $\endgroup$
    – Divyam Aggarwal
    Commented May 2, 2020 at 17:08

1 Answer 1

Reset to default
5
$\begingroup$

The solver will insert slack variables in the inequalities, so effectively all you are doing is penalizing the slacks. That can result in a suboptimal solution if you are not careful, and I can't think of any reason that it would make the problem faster to solve.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The constraints I state here, are part of a bigger model. Think of the Bs as the capacities of a tank: it can contain something between 0 and c. I have an interest in forcing the solver to prefer in its solution path large steps in the values for B, but still feasible ones in terms of the larger model. The original objective function contains only nonnegative terms so, adding -(M1 + M2) will not affect the optimal values of the variables B1, B2. The solver will maximize (B1+B2) and minimize the expession -(M1+M2). The question is, if transforming the inequalities to equalities helps. $\endgroup$
    – Clement
    Commented May 3, 2020 at 8:14

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