Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: zero setup case

Mahdi Doostmohammadi, Kerem Akartunali

Research output: Contribution to journalArticle

  • 1 Citations

Abstract

In this paper, we investigate two-period subproblems for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds. In particular, we investigate the special case of zero setup times and identify two important mixed integer sets representing relaxations of these subproblems. We analyze the polyhedral structure of these sets, deriving several families of valid inequalities and presenting their facet-defining conditions. We then extend these inequalities in a novel fashion to the original space of two-period subproblems, and also propose a new family of valid inequalities in the original space. In order to investigate the true strength of the proposed inequalities, we propose and implement exact separation algorithms, which are computationally tested over a broad range of test problems. In addition, we develop a heuristic framework for separation, in order to extend computational tests to larger instances. These computational experiments indicate the proposed inequalities can be indeed very effective improving lower bounds substantially.
LanguageEnglish
Pages86-95
Number of pages10
JournalEuropean Journal of Operational Research
Volume267
Issue number1
Early online date16 Nov 2017
DOIs
StatePublished - 16 May 2018

Fingerprint

Valid Inequalities
Lot Sizing
Zero
Setup Times
Facet
Computational Experiments
Test Problems
Heuristics
Lower bound
Integer
Experiments
Range of data
Valid inequalities
Lot sizing
Family

Keywords

  • production
  • lot-sizing
  • integer programming
  • polyhedral analysis
  • valid inequalities

Cite this

@article{e27cfcfb51444632be732b36c2a8da1e,
title = "Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: zero setup case",
abstract = "In this paper, we investigate two-period subproblems for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds. In particular, we investigate the special case of zero setup times and identify two important mixed integer sets representing relaxations of these subproblems. We analyze the polyhedral structure of these sets, deriving several families of valid inequalities and presenting their facet-defining conditions. We then extend these inequalities in a novel fashion to the original space of two-period subproblems, and also propose a new family of valid inequalities in the original space. In order to investigate the true strength of the proposed inequalities, we propose and implement exact separation algorithms, which are computationally tested over a broad range of test problems. In addition, we develop a heuristic framework for separation, in order to extend computational tests to larger instances. These computational experiments indicate the proposed inequalities can be indeed very effective improving lower bounds substantially.",
keywords = "production, lot-sizing, integer programming, polyhedral analysis, valid inequalities",
author = "Mahdi Doostmohammadi and Kerem Akartunali",
year = "2018",
month = "5",
day = "16",
doi = "10.1016/j.ejor.2017.11.014",
language = "English",
volume = "267",
pages = "86--95",
journal = "European Journal of Operational Research",
issn = "0377-2217",
number = "1",

}

Valid inequalities for two-period relaxations of big-bucket lot-sizing problems : zero setup case. / Doostmohammadi, Mahdi; Akartunali, Kerem.

In: European Journal of Operational Research, Vol. 267, No. 1, 16.05.2018, p. 86-95.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Valid inequalities for two-period relaxations of big-bucket lot-sizing problems

T2 - European Journal of Operational Research

AU - Doostmohammadi,Mahdi

AU - Akartunali,Kerem

PY - 2018/5/16

Y1 - 2018/5/16

N2 - In this paper, we investigate two-period subproblems for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds. In particular, we investigate the special case of zero setup times and identify two important mixed integer sets representing relaxations of these subproblems. We analyze the polyhedral structure of these sets, deriving several families of valid inequalities and presenting their facet-defining conditions. We then extend these inequalities in a novel fashion to the original space of two-period subproblems, and also propose a new family of valid inequalities in the original space. In order to investigate the true strength of the proposed inequalities, we propose and implement exact separation algorithms, which are computationally tested over a broad range of test problems. In addition, we develop a heuristic framework for separation, in order to extend computational tests to larger instances. These computational experiments indicate the proposed inequalities can be indeed very effective improving lower bounds substantially.

AB - In this paper, we investigate two-period subproblems for big-bucket lot-sizing problems, which have shown a great potential for obtaining strong bounds. In particular, we investigate the special case of zero setup times and identify two important mixed integer sets representing relaxations of these subproblems. We analyze the polyhedral structure of these sets, deriving several families of valid inequalities and presenting their facet-defining conditions. We then extend these inequalities in a novel fashion to the original space of two-period subproblems, and also propose a new family of valid inequalities in the original space. In order to investigate the true strength of the proposed inequalities, we propose and implement exact separation algorithms, which are computationally tested over a broad range of test problems. In addition, we develop a heuristic framework for separation, in order to extend computational tests to larger instances. These computational experiments indicate the proposed inequalities can be indeed very effective improving lower bounds substantially.

KW - production

KW - lot-sizing

KW - integer programming

KW - polyhedral analysis

KW - valid inequalities

UR - http://www.sciencedirect.com/science/article/pii/S0377221717310251

U2 - 10.1016/j.ejor.2017.11.014

DO - 10.1016/j.ejor.2017.11.014

M3 - Article

VL - 267

SP - 86

EP - 95

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -