Dynamic-programming-based inequalities for the capacitated lot-sizing problem

Joseph C. Hartman; I. Esra Büyüktahtakin; J. Cole Smith

doi:10.1080/0740817X.2010.504683

Dynamic-programming-based inequalities for the capacitated lot-sizing problem

Joseph C. Hartman, I. Esra Büyüktahtakin, J. Cole Smith

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

Iterative solutions of forward dynamic programming formulations for the capacitated lot sizing problem are used to generate inequalities for an equivalent integer programming formulation. The inequalities capture convex and concave envelopes of intermediate-stage value functions and can be lifted by examining potential state information at future stages. Several possible implementations that employ these inequalities are tested and it is demonstrated that the proposed approach is more efficient than alternative integer programming-based algorithms. For certain datasets, the proposed algorithm also outperforms a pure dynamic programming algorithm for the problem.

Original language	English (US)
Pages (from-to)	915-930
Number of pages	16
Journal	IIE Transactions (Institute of Industrial Engineers)
Volume	42
Issue number	12
DOIs	https://doi.org/10.1080/0740817X.2010.504683
State	Published - Dec 2010
Externally published	Yes

Keywords

Dynamic programming
capacitated lot sizing
integer programming

ASJC Scopus subject areas

Industrial and Manufacturing Engineering

Access to Document

10.1080/0740817X.2010.504683

Cite this

@article{5c76bfd0eb214b32a0997e17a0eff37d,

title = "Dynamic-programming-based inequalities for the capacitated lot-sizing problem",

abstract = "Iterative solutions of forward dynamic programming formulations for the capacitated lot sizing problem are used to generate inequalities for an equivalent integer programming formulation. The inequalities capture convex and concave envelopes of intermediate-stage value functions and can be lifted by examining potential state information at future stages. Several possible implementations that employ these inequalities are tested and it is demonstrated that the proposed approach is more efficient than alternative integer programming-based algorithms. For certain datasets, the proposed algorithm also outperforms a pure dynamic programming algorithm for the problem.",

keywords = "Dynamic programming, capacitated lot sizing, integer programming",

author = "Hartman, {Joseph C.} and B{\"u}y{\"u}ktahtakin, {I. Esra} and Smith, {J. Cole}",

note = "Funding Information: The authors are grateful to two anonymous referees whose remarks led to an improved revision of this article. Dr. Hartman gratefully acknowledges National Science Foundation support under grant CMMI-0813671 and Dr. Smith gratefully acknowledges the support of the Air Force Office of Scientific Research under grants FA9550-07-1-0404 and FA9550-08-1-0189.",

year = "2010",

month = dec,

doi = "10.1080/0740817X.2010.504683",

language = "English (US)",

volume = "42",

pages = "915--930",

journal = "IIE Transactions (Institute of Industrial Engineers)",

issn = "0740-817X",

publisher = "Taylor and Francis Ltd.",

number = "12",

}

TY - JOUR

T1 - Dynamic-programming-based inequalities for the capacitated lot-sizing problem

AU - Hartman, Joseph C.

AU - Büyüktahtakin, I. Esra

AU - Smith, J. Cole

N1 - Funding Information: The authors are grateful to two anonymous referees whose remarks led to an improved revision of this article. Dr. Hartman gratefully acknowledges National Science Foundation support under grant CMMI-0813671 and Dr. Smith gratefully acknowledges the support of the Air Force Office of Scientific Research under grants FA9550-07-1-0404 and FA9550-08-1-0189.

PY - 2010/12

Y1 - 2010/12

N2 - Iterative solutions of forward dynamic programming formulations for the capacitated lot sizing problem are used to generate inequalities for an equivalent integer programming formulation. The inequalities capture convex and concave envelopes of intermediate-stage value functions and can be lifted by examining potential state information at future stages. Several possible implementations that employ these inequalities are tested and it is demonstrated that the proposed approach is more efficient than alternative integer programming-based algorithms. For certain datasets, the proposed algorithm also outperforms a pure dynamic programming algorithm for the problem.

AB - Iterative solutions of forward dynamic programming formulations for the capacitated lot sizing problem are used to generate inequalities for an equivalent integer programming formulation. The inequalities capture convex and concave envelopes of intermediate-stage value functions and can be lifted by examining potential state information at future stages. Several possible implementations that employ these inequalities are tested and it is demonstrated that the proposed approach is more efficient than alternative integer programming-based algorithms. For certain datasets, the proposed algorithm also outperforms a pure dynamic programming algorithm for the problem.

KW - Dynamic programming

KW - capacitated lot sizing

KW - integer programming

UR - http://www.scopus.com/inward/record.url?scp=77957890455&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77957890455&partnerID=8YFLogxK

U2 - 10.1080/0740817X.2010.504683

DO - 10.1080/0740817X.2010.504683

M3 - Article

AN - SCOPUS:77957890455

SN - 0740-817X

VL - 42

SP - 915

EP - 930

JO - IIE Transactions (Institute of Industrial Engineers)

JF - IIE Transactions (Institute of Industrial Engineers)

IS - 12

ER -

Dynamic-programming-based inequalities for the capacitated lot-sizing problem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this