How to add multiple cuts as lazy constraints

91 Views Asked by At

I have a minimization problem where I implement Benders decomposition and add my cuts as lazy constraints. I am able to add multiple cuts at each iteration since the sub problem is seperable. Also, I am only concerned with the optimality cuts meaning that I do not have a feasibility issue.

Let me use $t$ as the continues variable used in master problem to estimate the objective of sub problem. Now, I can seperate $t$ as $t_i, \forall i=1...n.$

By the nature of the lazy cuts, before generating the cut, I check whether I underestimate the objective of dual problem (i.e., if $t \leq \mu$) where $\mu$ is the objective value obtained after solving the sub problem.

Now, if I intend to create multiple optimality cuts, should I conduct the same operation in an aggregate way (if $\sum_{i=1..n} t_i \leq \sum_{i=1..n} \mu_i$ , then geenrate $n$ cuts) or should I do it for each $i$ individually? For instance, should I do (if $t_2 <= \mu_2$, generate a cut, if $t_5 \nleq \mu_5$, then do not generate a cut)?

1

There are 1 best solutions below

1
On

The disaggregated cuts $t_i \le \mu_i$ will yield a tighter feasible region (and hence a better lower bound) than the aggregated cut $\sum_i t_i \le \sum_i \mu_i$, but it is worth trying both ways.