UNIGE document Report
previous document  unige:5922  next document
add to browser collection
Title

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

Authors
Goffin, J.-L.
Trouiller, C.
Year 1997
Collection Cahiers de recherche; 1997.11
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
Full text
This document has no fulltext available yet, but you can contact its author by using the form below.
Structures
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 https://archive-ouverte.unige.ch/unige:5922

221 hits

0 download

Update

Deposited on : 2010-04-15

Export document
Format :
Citation style :