Publication Type

Journal Article

Version

publishedVersion

Publication Date

6-2015

Abstract

We study the multi-item capacitated lot sizing problem with setup times. Based on two strong reformulations of the problem, we present a transformed reformulation and valid inequalities that speed up column generation and Lagrange relaxation. We demonstrate computationally how both ideas enhance the performance of our algorithm and show theoretically how they are related to dual space reduction techniques. We compare several solution methods and propose a new efficient hybrid scheme that combines column generation and Lagrange relaxation in a novel way. Computational experiments show that the proposed solution method for finding lower bounds is competitive with textbook approaches and state-of-the-art approaches found in the literature. Finally, we design a branch-and-price-based heuristic and report computational results. The heuristic scheme compares favorably or outperforms other approaches.

Keywords

lot sizing, column generation, Lagrange relaxation, branch and price, heuristics

Discipline

Business Administration, Management, and Operations | Numerical Analysis and Computation

Research Areas

Operations Management

Publication

INFORMS Journal on Computing

Volume

27

Issue

3

First Page

431

Last Page

448

ISSN

1091-9856

Identifier

10.1287/ijoc.2014.0636

Publisher

INFORMS (Institute for Operations Research and Management Sciences)

Embargo Period

8-29-2021

Download

Share

COinS