Practical enhancements to the Magnanti-Wong method

被引：154

作者：

Papadakos, Nikolacis ^{[1
,2
]}

机构：

[1] Univ London Imperial Coll Sci Technol & Med, Dept Comp, London SW7 2AZ, England

[2] Decisal Ltd, London SW6 7PB, England

来源：

OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 04期

关键词：

accelerated benders decomposition; benders cut dominance; pareto-optimal cut; Magnanti-Wong algorithm;

D O I：

10.1016/j.orl.2008.01.005

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

The Magnanti-Wong method - accelerating Benders decomposition - is shown to exhibit difficulties due to its dependence on the subproblem; an independent version is therefore introduced. The method additionally requires a - sometimes intractable - master problem core point; for several applications it is proved and experimentally verified that alternative points may be used. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：444 / 449

页数：6

共 14 条

[1]

Barnhart C, 1998, OPERATIONS RES AIRLI, V9, P384

[2]

BENDERS JF, 1962, NUMER MATH, V4, P238, DOI [10.1007/BF01386316, DOI 10.1007/BF01386316, DOI 10.1007/S10287-004-0020-Y]

[3]

CHEADLE AM, 2003, ICPARC031

[4] A benders decomposition approach for the locomotive and car assignment problem [J].

Cordeau, JF ;

Soumis, F ;

Desrosiers, J .

TRANSPORTATION SCIENCE, 2000, 34 (02) :133-149

[5] Simultaneous assignment of locomotives and cars to passenger trains [J].

Cordeau, JF ;

Soumis, F ;

Desrosiers, J .

OPERATIONS RESEARCH, 2001, 49 (04) :531-548

[6]

Lasdon LeonS., 2013, OPTIMIZATION THEORY

[7] ACCELERATING BENDERS DECOMPOSITION - ALGORITHMIC ENHANCEMENT AND MODEL SELECTION CRITERIA [J].

MAGNANTI, TL ;

WONG, RT .

OPERATIONS RESEARCH, 1981, 29 (03) :464-484

[8] MODIFIED BENDERS PARTITIONING ALGORITHM FOR MIXED INTEGER PROGRAMMING [J].

MCDANIEL, D ;

DEVINE, M .

MANAGEMENT SCIENCE, 1977, 24 (03) :312-319

[9] A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem [J].

Mercier, A ;

Cordeau, JF ;

Soumis, F .

COMPUTERS & OPERATIONS RESEARCH, 2005, 32 (06) :1451-1476

[10]

MERCIER A, 2006, COMPUTERS OPERATIONS, V34, P2251

← 1 2 →