On formulations of the stochastic uncapacitated lot-sizing problem

被引：21

作者：

Guan, YP ^{[1
]}

Ahmed, S

Miller, AJ

Nemhauser, GL

机构：

[1] Georgia Inst Technol, Sch Ind & Syst Engn, Atlanta, GA 30332 USA

[2] Univ Wisconsin, Dept Ind Engn, Madison, WI 53706 USA

[3] Univ Oklahoma, Sch Ind Engn, Norman, OK 73019 USA

来源：

OPERATIONS RESEARCH LETTERS | 2006年 / 34卷 / 03期

基金：

美国国家科学基金会;

关键词：

lot-sizing; mixed integer programming; reformulation; convex hull; separation;

D O I：

10.1016/j.orl.2005.05.004

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider two formulations of a stochastic uncapacitated lot-sizing problem. We show that by adding (l, S) inequalities to the one with the smaller number of variables, both formulations give the same LP bound. Then we show that for two-period problems, adding another class of inequalities gives the convex hull of integral solutions. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：241 / 250

页数：10

共 10 条

[1] A multi-stage stochastic integer programming approach for capacity expansion under uncertainty [J].

Ahmed, S ;

King, A ;

Parija, G .

JOURNAL OF GLOBAL OPTIMIZATION, 2003, 26 (01) :3-24

[2]

Atamtürk A, 2000, MATH PROGRAM, V89, P35, DOI 10.1007/s101070000154

[3]

BARANY I, 1984, MATH PROGRAM STUD, V22, P32, DOI 10.1007/BFb0121006

[4]

GUAN Y, 2005, IN PRESS MATH PROGRA

[5]

Guan YP, 2005, LECT NOTES COMPUT SC, V3509, P23

[6] Mixing mixed-integer inequalities [J].

Günlük, O ;

Pochet, Y .

MATHEMATICAL PROGRAMMING, 2001, 90 (03) :429-457

[7]

Krarup J., 1977, NUMERISCHE METHODEN, V36, P155, DOI DOI 10.1007/978-3-0348-5936-3_10

[8] Tight formulations for some simple mixed integer programs and convex objective integer programs [J].

Miller, AJ ;

Wolsey, LA .

MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) :73-88

[9] LOT-SIZING WITH CONSTANT BATCHES - FORMULATION AND VALID INEQUALITIES [J].

POCHET, Y ;

WOLSEY, LA .

MATHEMATICS OF OPERATIONS RESEARCH, 1993, 18 (04) :767-785

[10] POLYHEDRA FOR LOT-SIZING WITH WAGNER-WHITIN COSTS [J].

POCHET, Y ;

WOLSEY, LA .

MATHEMATICAL PROGRAMMING, 1994, 67 (03) :297-323

← 1 →