Optimization Online


A Polyhedral Study of Two-Period Relaxations for Big-Bucket Lot-Sizing Problems: Zero Setup Case

Mahdi Doostmohammadi(mahdi.doostmohammadi***at***strath.ac.uk)
Kerem Akartunali(kerem.akartunali***at***strath.ac.uk)

Abstract: In this paper, we investigate the two-period subproblems proposed by Akartunal{\i} et al. (2014) for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds for these problems. In particular, we study the polyhedral structure of the mixed integer sets related to two relaxations of these subproblems for the special case of zero setup times, derive several families of valid inequalities and present their facet-defining conditions. Then we discuss the separation problems associated with these valid inequalities and propose exact separation algorithms. Finally, we investigate the computational strength of these cuts when they are integrated into a cutting plane framework. Our computational experiments indicate they can be indeed very effective improving lower bounds substantially.

Keywords: Lot-Sizing; Integer Programming; Polyhedral Analysis; Valid Inequalities.

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

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Integer Programming

Citation: Technical Report, University of Strathclyde, February 2015.

Download: [PDF]

Entry Submitted: 02/04/2015
Entry Accepted: 02/04/2015
Entry Last Modified: 02/04/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