About Benders decomposition for MILP

Question

I have been using Benders decomposition for the following MILP:

Original problem

I put the binary y variables into the residual subproblem, which is as follows:

Residual subproblem

The dual form is:

Dual

Then I formulate the relaxed master problem of Benders decomposition:

RMP

Since the SP is always feasible and DSP is always bounded, there will be no Benders feasibility cut. The only type of cuts is the Benders optimality cut:

Benders optimality cut

which are generated iteratively.

The problem is, the procedure works well for small scale problems. For large instances however, the above Benders optimality cuts have insanely large constant terms, making the LB very bad, which are generated by solving the RMP, and the optimal solution becomes impossible to approach. For example, for a large instance, the first Benders optimality cut I get is:

9729 y1,0,6 + 86139 y1,0,7 + 5590 y2,1,6 + 195000 y2,1,7 + ... + 1306498 <= w

All y terms have positive coefficients, so the minimum value of w is 1306498, which is far from the optimal value.

How can I fix this? Did I do something wrong? If I did, where is it?

Update:

As mentioned by prubin, in (4.35) the term $S_{iu} + T_{ij}$ should be $S_{ju} + T_{ij}$, that was a typo in my manuscript. However in my programme the DSP objective as well as the cut are indeed correctly calculated using the latter.

Here's what I found after a double check.

1. I solved the primal SP instead of the DSP and get exactly the same values of dual multipliers. Also its objective value is strictly equal to the LHS of the generated cut (after plugging $y_{iju}$ values).
2. I solved the original MILP to get a set of optimal $y_{iju}$ values. After inserting these $y_{iju}$ values into the SP, it generates the same optimal solution. The generated cut is of course reasonable as well.
3. However suppose I start with another set of $y_{iju}$ values, which are feasible but suboptimal, say: for all $u$, $y_{11u} = 1$, $y_{iju} = 1$ for $i > 1$ and $j = i - 1$, $y_{iju} = 0$ for all other values of $j$. These values of $y_{iju}$ satisfy (3.7) (3.8a) and (3.8b). After plugging them into the SP I get a very bad but feasible solution, and (4.43) yields a lower bound of $w$, which is much larger than the optimal objective value as in step 2. Further iteration of the Benders decomposition procedure could improve the solution, but finally, stuck by this lower bound of $w$, and never could the optimal solution as found in step 2 be reached. This means that, the very first Benders optimality cut generated in the first iteration, is actually violated by the optimal solution. To the best of my knowledge, this is abnormal in Benders decomposition.

I am even more confused now. Could not figure out where the bug is.

Update 2:

I think I have spotted where the problem is. As hinted by @prubin. The big-M constraint (4.28) in the original problem, is replaced by (4.31) in the residual SP, leading to the implicit non-linear structure of the solution space, in which the optimality of the Benders decomposition cannot be guaranteed.

Now the problem is, how to deal with this big-M constraint? If it is taken into the SP as its original form, then the generated cuts become rather weak and the BD performance is rather poor.

I have also checked this paper: Combinatorial Benders' Cuts for Mixed-Integer Linear Programming, G. Codato and M. Fischetti (2006), Operations Research 54(4):756-766. The authors claimed that the case "$c\neq 0$ and $d\neq 0$" cannot be dealt with effectively by their approach, which seemed to be the case in my problem.

Answer 1

My first suggestion would be to omit $y$ from the subproblem objective and make the RMP objective minimization of $w + \sum_{i,u} C^U_u y_{iiu}.$ Mathematically it should make no difference, but it may make things a little easier to sort out.

Next, I would try solving the primal RMP rather than its dual, then asking the solver for the dual solution and using it to calculate the optimality cut manually. Plug the values of $y$ passed down to the subproblem into that cut and confirm that the subproblem objective problem (as $w$) satisfies the cut as an equality (i.e., the left portion of the cut evaluates to the subproblem objective value). If not, something is broken. If it does, I would tend to suspect a formulation error in the subproblem dual. I don't have time to check your dual formulation, and in any case you don't need it if you solve the primal and just ask the solver for the dual values.

Answer 2

Consider, for simplicity, a subproblem with a single "big M" constraint, of the following form:\begin{align*} z=\min\:c'x\\ \textrm{s.t. }Ax & \ge a\\ b'x & \ge b_{0}-M(1-y)\\ x & \ge0 \end{align*} where $y$ is a binary variable passed down from the master problem. If the dual solution is $(\lambda, \mu),$ the Benders optimality cut should be $$z\ge a'\lambda + b_0\mu -M\mu + M\mu y.$$ Your approach in (4.31) was to implicitly rewrite the last subproblem constraint as $b'x \ge b_0 y,$ turning the optimality cut into $$z\ge a'\lambda +b_0 \mu y.$$ This produces the correct result when $y=1,$ but when $y=0$ your version becomes $$z\ge a'\lambda$$ as opposed to $$z\ge a'\lambda + (b_0 - M)\mu.$$ So your version is too tight when $y=0.$