Fathoming rules for biobjective mixed integer linear programs: Review and extensions

被引：18

作者：

Belotti, Pietro ^{[1
]}

Soylu, Banu ^{[2
]}

Wiecek, Margaret M. ^{[3
]}

机构：

[1] FICO, Xpress Optimizer Team, Birmingham B37 7GN, W Midlands, England

[2] Erciyes Univ, Dept Ind Engn, TR-38039 Kayseri, Turkey

[3] Clemson Univ, Dept Math Sci, Clemson, SC 29630 USA

来源：

DISCRETE OPTIMIZATION | 2016年 / 22卷

关键词：

Nadir point; Nadir set; Bound set; Pareto point; Branch-and-bound; SPACE SEARCH ALGORITHM; BOUND ALGORITHM; OPTIMIZATION PROBLEMS; LOCATION PROBLEM; SOLVE;

D O I：

10.1016/j.disopt.2016.09.003

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the class of biobjective mixed integer linear programs (BOMILPs). We review fathoming rules for general BOMILPs and present them in a unified manner. We then propose new fathoming rules that rely on solving specially designed LPs, hence making no assumption on the type of problem and only using polynomial-time algorithms. We describe an enhancement for carrying out these rules by performing a limited number of pivot operations on an LP, and then we provide insight that helps to make these rules even more efficient by either focusing on a smaller number of feasible solutions or by resorting to heuristics that limit the number of LPs solved. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：341 / 363

页数：23

共 34 条

[1] AN INTERACTIVE BRANCH-AND-BOUND ALGORITHM FOR BICRITERION NONCONVEX MIXED INTEGER PROGRAMMING [J].

AKSOY, Y .

NAVAL RESEARCH LOGISTICS, 1990, 37 (03) :403-417

[2] A review of interactive methods for multiobjective integer and mixed-integer programming [J].

Alves, Maria Joao ;

Climaco, Joao .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 180 (01) :99-115

[3] BICRITERIA TRANSPORTATION PROBLEM [J].

ANEJA, YP ;

NAIR, KPK .

MANAGEMENT SCIENCE, 1979, 25 (01) :73-78

[4]

[Anonymous], 2005, MULTICRITERIA OPTIMI

[5]

Belotti P., 2013, BRANCH AND BOUND ALG

[6]

Belotti P., 2016, BRANCH AND BOU UNPUB

[7] A COMBINED APPROACH TO SOLVE BINARY MULTICRITERIA PROBLEMS [J].

BITRAN, GR ;

RIVERA, JM .

NAVAL RESEARCH LOGISTICS, 1982, 29 (02) :181-201

[8] A Criterion Space Search Algorithm for Biobjective Integer Programming: The Balanced Box Method [J].

Boland, Natashia ;

Charkhgard, Hadi ;

Savelsbergh, Martin .

INFORMS JOURNAL ON COMPUTING, 2015, 27 (04) :735-754

[9] A Criterion Space Search Algorithm for Biobjective Mixed Integer Programming: The Triangle Splitting Method [J].

Boland, Natashia ;

Charkhgard, Hadi ;

Savelsbergh, Martin .

INFORMS JOURNAL ON COMPUTING, 2015, 27 (04) :597-618

[10]

Cohon J.L., 1978, Multiobjective programming and planning

← 1 2 3 4 →