Benders subproblem with product of continuous and discrete variables

Question

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.

\begin{equation}\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} \end{equation}

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{equation} \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} \end{equation}

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)

Answer 1

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.

Answer 2

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.