Sandwich approximation algorithms for lot-sizing problems

EI-ERIM-OR seminar
Helicopter view of an array of different colour containers on a cargo ship
Wilco van den Heuvel
Friday 3 Jun 2022, 12:00 - 13:00
Spoken Language
Polak Building
Add to calendar
Helicopter view of an array of different colour containers on a cargo ship

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, (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.


  • Michal Mankowski
  • Olga Kuryatnikova
More information

Zoom broadcasting:
Meeting ID: 951 5698 6071
Passcode: 385550

Secretariat Econometrics
Phone: +31 (0)10 408 12 59/ 12 64

Related links
Department of Econometrics

Compare @count study programme

  • @title

    • Duration: @duration
Compare study programmes