A lexicographic pricer for the fractional bin packing problem

被引：4

作者：

Coniglio, Stefano ^{[1
]}

D'Andreagiovanni, Fabio ^{[2
,3
]}

Furini, Fabio ^{[4
]}

机构：

[1] Univ Southampton, Dept Math Sci, Univ Rd, Southampton SO17 1BJ, Hants, England

[2] CNRS, French Natl Ctr Sci Res, Paris, France

[3] Univ Technol Compiegne, Sorbonne Univ, CNRS, Heudiasyc,UMR 7253,CS 60319, F-60203 Compiegne, France

[4] Univ Paris 09, LAMSADE, F-75775 Paris, France

来源：

OPERATIONS RESEARCH LETTERS | 2019年 / 47卷 / 06期

关键词：

Fractional bin packing problem; Column generation; Dynamic programming; Lexicographic optimization; COLUMN; ALGORITHM;

D O I：

10.1016/j.orl.2019.10.011

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We propose an exact lexicographic dynamic programming pricing algorithm for solving the Fractional Bin Packing Problem with column generation. The new algorithm is designed for generating maximal columns of minimum reduced cost which maximize, lexicographically, one of the measures of maximality we investigate. Extensive computational experiments reveal that a column generation algorithm based on this pricing technique can achieve a substantial reduction in the number of columns and the computing time, also when combined with a classical smoothing technique from the literature. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：622 / 628

页数：7

共 32 条

[1] SCIP: solving constraint integer programs [J].

Achterberg, Tobias .

MATHEMATICAL PROGRAMMING COMPUTATION, 2009, 1 (01) :1-41

[2] Coordinated cutting plane generation via multi-objective separation [J].

Amaldi, Edoardo ;

Coniglio, Stefano ;

Gualandi, Stefano .

MATHEMATICAL PROGRAMMING, 2014, 143 (1-2) :87-110

[3]

Amaldi E, 2010, LECT NOTES COMPUT SC, V6049, P266, DOI 10.1007/978-3-642-13193-6_23

[4] Optimizing over the split closure [J].

Balas, Egon ;

Saxena, Anureet .

MATHEMATICAL PROGRAMMING, 2008, 113 (02) :219-240

[5] A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting [J].

Belov, G ;

Scheithauer, G .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 171 (01) :85-106

[6]

Ben Amor H, 2005, COLUMN GENERATION, V5, P131

[7] On the choice of explicit stabilizing terms in column generation [J].

Ben Amor, Hatem M. T. ;

Desrosiers, Jacques ;

Frangioni, Antonio .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (06) :1167-1184

[8] Friendly bin packing instances without Integer Round-up Property [J].

Caprara, Alberto ;

Dell'Amico, Mauro ;

Diaz-Diaz, Jose Carlos ;

Iori, Manuel ;

Rizzi, Romeo .

MATHEMATICAL PROGRAMMING, 2015, 150 (01) :5-17

[9] A survey of dual-feasible and superadditive functions [J].

Clautiaux, Francois ;

Alves, Claudio ;

de Carvalho, Jose Valerio .

ANNALS OF OPERATIONS RESEARCH, 2010, 179 (01) :317-342

[10]

Coffman E. G., 2012, Handbook of Combinatorial Optimization, P455, DOI DOI 10.1007/978-1-4419-7997-135

← 1 2 3 4 →