Optimization Online


On the Polyhedral Structure of Two-Level Lot-Sizing Problems with Supplier Selection

Ayse N. Arslan (arslan.aysenur***at***gmail.com)
Jean-Philippe P. Richard (richard***at***ise.ufl.edu)
Yongpei Guan (guan***at***ise.ufl.edu)

Abstract: In this paper, we study a two-level lot-sizing problem with supplier selection (LSS). This NP-hard problem arises in different production planning and supply chain management applications. We first present a dynamic programming algorithm for LSS that is polynomial when the number of plants is fixed. We use this algorithm to describe the convex hull of solutions to the problem in an extended space of variables. We then investigate a smaller multi-commodity extended formulation, show that it has fractional vertices, and present a family of valid inequalities to strengthen it. Next, we explore the polyhedral structure of the formulation of the problem with traditional variables. We derive several families of strong valid inequalities for this formulation, and give conditions under which they are facet-defining. We prove that these new families of facet-defining inequalities are sufficient to describe the convex hull of the problem with two plants and two periods. Finally, we show numerically that incorporating these valid inequalities within a cut-and-branch framework leads to significant improvement in computation.

Keywords: lot-sizing, multi-echelon, extended formulations, cutting plane/facet

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Citation: University of Florida, 2015

Download: [PDF]

Entry Submitted: 12/10/2015
Entry Accepted: 12/10/2015
Entry Last Modified: 12/19/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society