The Quadrant Shrinking Method: A simple and efficient algorithm for solving tri-objective integer programs

被引：45

作者：

Boland, Natashia ^{[2
]}

Charkhgard, Hadi ^{[1
]}

Savelsbergh, Martin ^{[2
]}

机构：

[1] Univ Newcastle, Sch Math & Phys Sci, Callaghan, NSW, Australia

[2] Georgia Inst Technol, H Milton Stewart Sch Ind & Syst Engn, Atlanta, GA 30332 USA

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2017年 / 260卷 / 03期

关键词：

Tri-objective integer programs; Quadrant shrinking method; Criterion space search method; Nondominated frontier;

D O I：

10.1016/j.ejor.2016.03.035

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present a new variant of the full 2-split algorithm, the Quadrant Shrinking Method (QSM), for finding all nondominated points of a tri-objective integer program. The algorithm is easy to implement and solves at most 3 vertical bar Y-N vertical bar +1 single-objective integer programs when computing the nondominated frontier, where Y-N is the set of all nondominated points. A computational study demonstrates the efficacy of QSM. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：873 / 885

页数：13

共 15 条

[1] BICRITERIA TRANSPORTATION PROBLEM [J].

ANEJA, YP ;

NAIR, KPK .

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

[2]

Belotti P., 2013, BRANCH AND BOUND ALG

[3] The L-shape search method for triobjective integer programming [J].

Boland N. ;

Charkhgard H. ;

Savelsbergh M. .

Mathematical Programming Computation, 2016, 8 (2) :217-251

[4] 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

[5]

Brunsch T., 2014, Theory of Computing, V10, P237, DOI [10.4086/toc.2014.v010a010, DOI 10.4086/TOC.2014.V010A010]

[6]

Dachert K, 2014, J GLOBAL OPTIM, V1-34

[7] K-PPM: A new exact method to solve multi-objective combinatorial optimization problems [J].

Dhaenens, C. ;

Lemesre, J. ;

Talbi, E. G. .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2010, 200 (01) :45-53

[8] Benchmarking optimization software with performance profiles [J].

Dolan, ED ;

Moré, JJ .

MATHEMATICAL PROGRAMMING, 2002, 91 (02) :201-213

[9] A discussion of scalarization techniques for multiple objective integer programming [J].

Ehrgott, Matthias .

ANNALS OF OPERATIONS RESEARCH, 2006, 147 (01) :343-360

[10] A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems [J].

Kirlik, Gokhan ;

Sayin, Serpil .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2014, 232 (03) :479-488

← 1 2 →