The search-and-remove algorithm for biobjective mixed-integer linear programming problems

被引:16
作者
Soylu, Banu [1 ]
机构
[1] Erciyes Univ, Dept Ind Engn, TR-38039 Kayseri, Turkey
关键词
Multiple objective programming; Biobjective mixed-integer linear programming; Integer programming; Bound sets; BOUND ALGORITHM; SET; POINTS; SOLVE;
D O I
10.1016/j.ejor.2018.01.026
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
In this study, an exact algorithm, called the search-and-remove (SR) algorithm, is proposed to compute the Pareto frontier of biobjective mixed-integer linear programming problems. At each stage of the algorithm, efficient slices (all integer variables are fixed in a slice) are searched with the dichotomic search algorithm and found slices are recorded and excluded from the decision space with the help of Tabu constraints. The algorithm is also enhanced with lower and upper bounds, which are updated at each stage of the algorithm. The SR algorithm continues until it is proved that all efficient slices of the biobjective mixed-integer linear programming (BOMILP) problem are found. The algorithm finally returns a set of potentially efficient slices including all efficient slices of the problem. Then, an upper envelope finding algorithm merges the Pareto frontiers of these slices to the Pareto frontier of the original problem. A computational analysis is performed on several benchmark problems and the performance of the algorithm is compared with state of the art methods from the literature. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码:281 / 299
页数:19
相关论文
共 39 条
[11]   Bound sets for biobjective combinatorial optimization problems [J].
Ehrgott, Matthias ;
Gandibleux, Xavier .
COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (09) :2674-2694
[12]   The feasibility pump [J].
Fischetti, M ;
Glover, F ;
Lodi, A .
MATHEMATICAL PROGRAMMING, 2005, 104 (01) :91-104
[13]   Local branching [J].
Fischetti, M ;
Lodi, A .
MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) :23-47
[14]  
Gadegaard S., 2016, BI OBJECTIVE BRANCH
[15]  
HAIMES YY, 1971, IEEE T SYST MAN CYB, VSMC1, P296
[16]   ERROR DETECTING AND ERROR CORRECTING CODES [J].
HAMMING, RW .
BELL SYSTEM TECHNICAL JOURNAL, 1950, 29 (02) :147-160
[17]  
Hooker J, 2011, LOGIC BASED METHODS, V2
[18]   PROPER EFFICIENCY AND LINEAR VECTOR MAXIMUM PROBLEM [J].
ISERMANN, H .
OPERATIONS RESEARCH, 1974, 22 (01) :189-191
[19]   Bicriteria p-Hub Location Problems and Evolutionary Algorithms [J].
Koksalan, Murat ;
Soylu, Banu .
INFORMS JOURNAL ON COMPUTING, 2010, 22 (04) :528-542
[20]   Multi-criteria branch and bound: A vector maximization algorithm for Mixed 0-1 Multiple Objective Linear Programming [J].
Mavrotas, G ;
Diakoulaki, D .
APPLIED MATHEMATICS AND COMPUTATION, 2005, 171 (01) :53-71