Benders subproblem with product of continuous and discrete variables

I am trying to solve the following problem. The decisions in the problem are $$x, y, v,$$ and $$W$$, where $$x, y$$ are binary and $$v, W$$ are continuous variables.

\label{eq:3} \begin{aligned} & \underset{x, y, v, W}{\text{minimize}} & & c^{T}v + W^{T}\mathbf{1}\\ & \text{subject to} & & Ax \le b\\ & & & \sum_{f = 1}^{q} y_{lf} = x_l, \forall l = 1, ..., p\\ & & & Hv = d\\ & & & v_a \le \left(\sum_{f = 1}^{q} f y_{l(a)f}\right) W_i, \forall a = 1, ..., m, \forall i = 1, .., n \\ & & &x \in \{0, 1\}^p, y \in \{0, 1\}^{p\times q}, v \in \mathbb{R}^{m}_{+}, W \in \mathbb{R}^{n}_{+} \end{aligned}

As we can see that there is a product of continuous and binary variable in the fourth set constraints, so I linearize that using McCormick Relaxation. Assuming $$0 \le W_i \le \bar{W}_{i}$$ and let $$t_{fai} = y_{l(a)f} \times W_i$$, we can state the problem as an exact MIP as below:

\begin{aligned} & \underset{x, y, v, W, t}{\text{minimize}} & & c^{T}v + W^{T}\mathbf{1}\\ & \text{subject to} & & Ax \le b\\ & & & \sum_{f = 1}^{q} y_{lf} = x_l, \forall l = 1, ..., p\\ & & & Hv = d\\ & & & v_a \le \left(\sum_{f = 1}^{q} f t_{fai} \right), \forall a = 1, ..., m, \forall i = 1, .., n \\ & & & W_i - t_{fai} \le \bar{W}_{i} (1 - y_{l(a)f}), \forall f = 1, ..., q, \forall a = 1, ..., m, \forall i = 1, .., n\\ & & & t_{fai} \le \bar{W}_{i} y_{l(a)f}, \forall f = 1, ..., q, \forall a = 1, ..., m, \forall i = 1, .., n\\ & & & W_i - t_{fai} \ge 0, \forall f = 1, ..., q, \forall a = 1, ..., m, \forall i = 1, .., n\\ & & & t_{fai} \ge 0, \forall f = 1, ..., q, \forall a = 1, ..., m, \forall i = 1, .., n\\ & & &x \in \{0, 1\}^p, y \in \{0, 1\}^{p\times q}, v \in \mathbb{R}^{m}_{+}, W \in \mathbb{R}^{n}_{+} \end{aligned}

I am applying Benders Decomposition to solve the problem. The complicating variables are $$x$$ and $$y$$. Due to a large value of $$\bar{W}_{i}$$, the lower bound to the problem is really bad. The iterations look as below. The algorithm does not converge and becomes slow after adding lots of optimality cuts. I tried different values of $$\bar{W}_i$$. Letting $$\bar{W}_i$$ too low makes the subproblem infeasible (but my subproblem has been proved to have feasible solution for any value of $$x, y$$ so it should not gernerate any feasibility cuts). Are there any possible solutions to avoid this problem? I appreciate any help.

(it = 1, LB = -1249013856, UB = 780802)
(it = 2, LB =  -260761666, UB = 647047)
(it = 3, LB = -260385041, UB = 780652)
(it = 4, LB = -255998781, UB = 729034)
(it = 5, LB = -255661092, UB = 765904)


If I'm correct in my understanding of the decomposition, the master problem contains the binary variables (and a surrogate variable for the subproblem objective value) and the subproblem contains all the other variables and all the terms of the original objective function. That being the case, you might look at a paper by Codato and Fischetti [1], specifically the case where (in their notation) $$c=0$$ and $$d \neq 0$$. In essence, they eliminate the big $$M$$ coefficients (your $$\overline{W}$$) by dropping, at each iteration, any subproblem constraint whose RHS is effectively $$\infty$$. They also add a constraint to the subproblem saying that it has to produce a solution with better objective value than the current incumbent, so that a feasible subproblem incapable of improving the incumbent becomes infeasible (and generates a feasibility cut). There is no guarantee it produces better bounds than you are getting, but it might be worth trying.

[1] Codato, G. & Fischetti, M. Combinatorial Benders' Cuts for Mixed-Integer Linear Programming. Operations Research, 2006, 54, 756-766.

• Thank you Prof. Prubin for your suggestion! I implemented the Combinatorial Benders decomposition but it is too slow. I optimized the value of big-M and now the classic Benders decomposition is working fine. What is more insteresting is that Gurobi can handle big-M values and does not suffer from issues while Benders is super sensitive to presence of big-Ms. Nov 11, 2020 at 4:16
• In my experience, Combinatorial Benders is sometimes faster than Benders with big-M constraints and sometimes slower. For that matter, Benders is sometimes faster than solving one large MIP model and sometimes slower. Pretty much everything MIP-related seems to be a roll of the dice.
– prubin
Nov 11, 2020 at 16:29

It would be better to use big-M values that depend on $$f$$, $$a$$, and $$i$$, like $$\bar{W}_{f,a,i}$$, instead of just on $$i$$ only. Also, how are you computing big-M?

For fixed $$x$$ and $$y$$ that satisfy the first two constraints, your original problem is linear and feasible. An alternative approach to linearization is to use combinatorial Benders decomposition, where the Benders optimality cuts are big-M constraints. Because the subproblem is feasible for all $$x$$ and $$y$$, you do not need Benders feasibility cuts.

An idea that might help both approaches is to strengthen the master problem by including, a priori, additional valid inequalities that involve only $$x$$ and/or $$y$$. For example, if you can determine, perhaps by solving some auxiliary problem, that $$x_\ell=1$$ implies that the contribution to the objective for (location?) $$\ell$$ is at least $$g_\ell$$, you can impose master constraint $$\eta \ge \sum_{\ell=1}^p g_\ell x_\ell$$. Otherwise, you are completely relying on weak optimality cuts to guide the algorithm.

• Thank you Rob for your suggestions! I implemented the Combinatorial Benders decomposition but it is too slow. I optimized the value of big-M based on $f,a, i$ as you suggested and now the classic Benders decomposition is working fine. Nov 11, 2020 at 4:16