Speaker: Wilco van den Heuvel, Erasmus University of Rotterdam

Title: Sandwich approximation algorithms for lot-sizing problem

Abstract

We consider 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) certain 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 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.

______
Organisers: Sanne Wøhlk and Marcel Turkensteen