Lot sizing problem: how to add these cuts efficiently

Question

Consider the set of constraints of the uncapacitated lot sizing problem: $$ \{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\cdots,n\}, $$ where $x_t$ represent the production variables, $s_t$ the stock variables, and $y_t$ the binary production variables.

In Wolsey's book Integer Programming, on page 225, the following cuts are defined for the uncapacitated lot sizing problem: $$ s_{k-1}\ge \left( \sum_{t=k}^{\ell}\right)(1-y_k-\cdots - y_{\ell})\quad \mbox{for}\; 1\le k \le \ell \le n $$

I have ran tests on random instances and added all of the above cuts at the root node to see how effective they are. It turns out that in many cases, it actually increases the computation times, as many of these valid inequalities are unnecessary but still processed.

My question is: is there an efficient strategy to only choose a subset of these cuts ? Is fixing $k$ and $\ell$ randomly a good strategy for example?

Note: I don't want to add the cuts in a dynamic fashion, I am adding them at the root node.

Answer 1

I think you forgot the demand in the sum. The lower bound for storage is too low in your cuts. Whether fixing $k$ and $l$ helps you depends on your problem and how often you produce in the optimal solution. (If you produce in (nearly) every period, it is better to fix them.) I think Wolsey offers the simple option $l=k$ as a good choice. I have the same problem (capacitated) and it is very difficult to find good cuts.