Sandwich approximation algorithms for lot-sizing problems

We consider certain single-item lot-sizing problems which are (NP-)hard because of the shape of the objective function, typically non-concave. Examples are lot-sizing problems with (i) batch procurement, (ii) particular types of quantity discounts, and (iii) transportation by multiple vehicle types. We propose polynomial-time approximation algorithms based on a `sandwich' technique, in which the objective function of the original problem is bounded from below by an easier objective function and from above by the same easier function but multiplied with a constant. In fact, finding the tightest sandwich function can be an optimization problem on its own, of which the result determines the obtained approximation ratio, typically depending on the problem parameters. One of the interesting features of the approach is that we can obtain multiple solutions within the performance bound by using an approach based on parametric optimization. Finally, we have implemented such a sandwich approximation algorithm for a multi-level lot-sizing problem with batch procurement. We are able to find solutions deviating a few percent from optimality in a fraction of a second for reasonably sized instances.

Zoom link: https://eur-nl.zoom.us/j/95156986071?pwd=NmhWa2pYbWRoL3F1SWtxcElGZUhOQT09