Sandwich approximation algorithms for lot-sizing problems

Examples are lot-sizing problems with (i) batch procurement, (ii) particular types of quantity discounts, (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.

This is a joint work with Albert Wagelmans (Erasmus School of Economics)

About Wilco van den Heuvel

Wilco van den Heuvel is an associate professor at the Econometric Institute of the Erasmus School of Economics. His main research interests are in deterministic production planning, in particular in extensions of the economic lot-sizing model.

The focus of the research is on developing efficient algorithms.

His work is published in journals like Operations Research, Omega, European Journal of Operational Research, Computers & Operations Research, and Operations Research Letters.

Coordinators

• Michal Mankowski
• Olga Kuryatnikova