Big-M Constraints in Benders Decomposition

Question

I am studying a typical MILP problem with the form: $$ \begin{align} \min \;& c^Tx+d^Ty \\ \text{s.t.} \; & Fx\leqslant g\\ \; & Dy\leqslant e\\ \; & y\leqslant Mx\\ \; & x\in\{0,1\}, y\in R\\ \end{align} $$

As you can see, there are big-M constraints linking binary variables $x$ and continuous variables $y$. For example, $x$ determines whether an arc is open and $y$ is the flow quantity over this arc.

By Benders decomposition, the master problem only contains $x$, and the sub problem become linear after $x$ is fixed. Since my sub problem is always feasible, I pay attention to the optimality cut, which takes the form like $\eta\geqslant \alpha(b-Bx)$, where $\eta$ is added to the objective of the master problem, and $\alpha$ are extreme points (dual values) obtained by solving the subproblem.

However, $B$ is big M in my case so I get the classical benders optimality cuts: $\eta\geqslant \text{constant}-Mx$, which seems simply prevent trying the same $\bar{x}$ again (Please correct me if I am wrong). For example, the cut tells you in the first iteration that opening the arc 1 only is not good, and tells you in the second iteration that opening the arc 2 only is not good, and tells you in the third iteration that opening arcs 1 and 2 both is not good... May be after thousands of iterations you know that opening arcs 13, 79, 180, and 211 is good (Numbers are just for example).

Are there any cuts do more than just trying another $x$? I try to look at the combinatorial benders decomposition (Codato and Fischetti, 2006), but it seems to require that the sub problem is a feasibility problem and I want to deal with an optimality sub problem.

Answer 1

This depends at least in part on how tight your choices for $M$ are (noting that each constraint $j$ involving a binary variable can have its own distinct value $M_j$). If you pick a large value for $M_j,$ then when $x_j=1$ the dual multiplier is guaranteed to be 0, because the constraint cannot be binding. So you will only get nonzero coefficients for those $x_j$ that are equal to 0 in the solution passed to the subproblem. In those cases, if $M_j$ is "almost infinity" then I suspect corresponding coefficient in the optimality cut will be large enough to be unhelpful.

Now if you pick tight values of $M,$ such that $y_j = M_j$ is possible when $x_j = 1,$ the coefficient of $x_j$ in the optimality cut is no longer guaranteed to be quasi-infinite, and your Benders cut might actually become binding/push up $\eta$ for other potential $x$ solutions.

Answer 2

One way to find tight big-M values is to solve bounding problems that maximize each variable y over a relaxation of the feasible set where variable x can take any continuous value between 0 and 1. For this to work, you should also include an upper bound on the objective function, that you can compute knowing some good feasible solution of your original problem. You can find more details in our publication "Tight big-Ms for optimal transmission switching", where we solve a problem very similar to yours.