en
Report
English

A Lagrangian Relaxation of the Capacited Multi-Item Lot Sizing Problem Solved with an Interior Point Cutting Plane Algorithm

Collection
  • Cahiers de recherche; 1997.11
Publication date1997
Abstract

The capacitated multi-item lot sizing problem consists of finding a production shedule that minimizes over a finite number of periods the total production, holding inventory, and setup costs subject to demand and capacity constraints. The CLSP problem is NP-hard, while the problem of finding a feasible solution, which is polynomial if there are no set-up times, becomes NP-complete when set-up-times are included. Approximate solution can be obtained by heuristics. In this paper we consider an approach based on a Lagrangian relaxation of the capacity constraints. The relaxation is used in two ways. First, generates a lower bound for the optimal value. Second, the primal and dual solutions of the relaxation (if available) are used to generate integer feasible solutions by primal or dual heuristics. We compare three methods of solving the Lagrangian relaxation: subgradient method, Kelley's cutting plane method - also known as Dantzig-Wolfe decomposition - and the analytic center cutting plane method. We conclude that the analytic center cutting plane method performs as well, and sometimes better than subgradient optimization or Kelley's cuting plane method

Citation (ISO format)
DU MERLE, Olivier et al. A Lagrangian Relaxation of the Capacited Multi-Item Lot Sizing Problem Solved with an Interior Point Cutting Plane Algorithm. 1997
Identifiers
  • PID : unige:5922
490views
0downloads

Technical informations

Creation04/15/2010 12:21:15 PM
First validation04/15/2010 12:21:15 PM
Update time03/14/2023 3:27:03 PM
Status update03/14/2023 3:27:03 PM
Last indexation01/15/2024 7:46:11 PM
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack