A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems

Ioannis Fragkos, Kerem Akartunali

Research output: Contribution to conferencePaper

Abstract

We study the big-bucket capacitated lot sizing problem with setup times. We use the novel methodology of Akartunali et al. (2014) that exploits two-period relaxations of the formulation in order to generate inequalities that cut-off the optimal solution of the linear programming relaxation. Our approach applies column generation in an unconventional way, with the master problem being a distance minimizing formulation and the subproblems being combina-torial two-period relaxations of the original problem. We identify a lower bound of the dimensionality of the generated cuts and provide extensive computational experiments that show how the generated bounds compare with other state-of-
the-art approaches. Our results show that, for certain classes of problems, the bound improvement is considerable.
LanguageEnglish
Pages41-45
Number of pages5
Publication statusPublished - Aug 2014
EventInternational Workshop on Lot-Sizing (IWLS) 2014 - Porto, Portugal
Duration: 27 Aug 201429 Aug 2014

Conference

ConferenceInternational Workshop on Lot-Sizing (IWLS) 2014
CountryPortugal
CityPorto
Period27/08/1429/08/14

Fingerprint

Lot Sizing
Convex Hull
Linear programming
Closure
Experiments
Column Generation
Linear Programming Relaxation
Setup Times
Formulation
Computational Experiments
Dimensionality
Optimal Solution
Lower bound
Methodology

Keywords

  • convex hull closures
  • lot-sizing problems
  • two-period relaxations

Cite this

Fragkos, I., & Akartunali, K. (2014). A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems. 41-45. Paper presented at International Workshop on Lot-Sizing (IWLS) 2014, Porto, Portugal.
Fragkos, Ioannis ; Akartunali, Kerem. / A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems. Paper presented at International Workshop on Lot-Sizing (IWLS) 2014, Porto, Portugal.5 p.
@conference{d9e69a756b824dd4ae46b9ae21afc6c1,
title = "A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems",
abstract = "We study the big-bucket capacitated lot sizing problem with setup times. We use the novel methodology of Akartunali et al. (2014) that exploits two-period relaxations of the formulation in order to generate inequalities that cut-off the optimal solution of the linear programming relaxation. Our approach applies column generation in an unconventional way, with the master problem being a distance minimizing formulation and the subproblems being combina-torial two-period relaxations of the original problem. We identify a lower bound of the dimensionality of the generated cuts and provide extensive computational experiments that show how the generated bounds compare with other state-of-the-art approaches. Our results show that, for certain classes of problems, the bound improvement is considerable.",
keywords = "convex hull closures, lot-sizing problems, two-period relaxations",
author = "Ioannis Fragkos and Kerem Akartunali",
year = "2014",
month = "8",
language = "English",
pages = "41--45",
note = "International Workshop on Lot-Sizing (IWLS) 2014 ; Conference date: 27-08-2014 Through 29-08-2014",

}

Fragkos, I & Akartunali, K 2014, 'A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems' Paper presented at International Workshop on Lot-Sizing (IWLS) 2014, Porto, Portugal, 27/08/14 - 29/08/14, pp. 41-45.

A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems. / Fragkos, Ioannis; Akartunali, Kerem.

2014. 41-45 Paper presented at International Workshop on Lot-Sizing (IWLS) 2014, Porto, Portugal.

Research output: Contribution to conferencePaper

TY - CONF

T1 - A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems

AU - Fragkos, Ioannis

AU - Akartunali, Kerem

PY - 2014/8

Y1 - 2014/8

N2 - We study the big-bucket capacitated lot sizing problem with setup times. We use the novel methodology of Akartunali et al. (2014) that exploits two-period relaxations of the formulation in order to generate inequalities that cut-off the optimal solution of the linear programming relaxation. Our approach applies column generation in an unconventional way, with the master problem being a distance minimizing formulation and the subproblems being combina-torial two-period relaxations of the original problem. We identify a lower bound of the dimensionality of the generated cuts and provide extensive computational experiments that show how the generated bounds compare with other state-of-the-art approaches. Our results show that, for certain classes of problems, the bound improvement is considerable.

AB - We study the big-bucket capacitated lot sizing problem with setup times. We use the novel methodology of Akartunali et al. (2014) that exploits two-period relaxations of the formulation in order to generate inequalities that cut-off the optimal solution of the linear programming relaxation. Our approach applies column generation in an unconventional way, with the master problem being a distance minimizing formulation and the subproblems being combina-torial two-period relaxations of the original problem. We identify a lower bound of the dimensionality of the generated cuts and provide extensive computational experiments that show how the generated bounds compare with other state-of-the-art approaches. Our results show that, for certain classes of problems, the bound improvement is considerable.

KW - convex hull closures

KW - lot-sizing problems

KW - two-period relaxations

UR - http://iwls2014.emse.fr/

M3 - Paper

SP - 41

EP - 45

ER -

Fragkos I, Akartunali K. A computational study of the local cuts from two-period convex hull closures for big-bucket lot-sizing problems. 2014. Paper presented at International Workshop on Lot-Sizing (IWLS) 2014, Porto, Portugal.