Finding non-dominated solutions in bi-objective integer network flow problems

被引:21
作者
Eusebio, Augusto [1 ,2 ]
Figueira, Jose Rui [2 ,3 ]
机构
[1] Inst Politecn Leiria, Escola Super Tecnol & Gestao, P-2411901 Leiria, Portugal
[2] Univ Tecn Lisboa, Inst Super Tecn, Ctr Management Studies, CEG IST, P-2780990 Porto Salvo, Portugal
[3] Univ Paris 09, LAMSADE, F-75775 Paris 16, France
关键词
Bi-objective integer network flows; Network simplex algorithm; Efficient solutions; Non-dominated solutions; ALGORITHM;
D O I
10.1016/j.cor.2008.11.001
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
This paper deals with an algorithm for finding all the non-dominated solutions and corresponding efficient solutions for bi-objective integer network flow problems. The algorithm solves a sequence of epsilon-constraint problems and computes all the non-dominated solutions by decreasing order of one of the objective functions. The optimal integer solutions for the e-constraint problems are determined by exploring a branch-and-bound tree. The algorithm makes use of the network structure to perform the computations, i.e., the network structure of the problem is not destroyed with the inclusion of an epsilon-constraint. This paper presents the main features of the algorithm, the theoretical bases of the proposed approach and some computational issues. Experiments were done and the results are also reported in the paper. (C) 2008 Elsevier Ltd. All rights reserved.
引用
收藏
页码:2554 / 2564
页数:11
相关论文
共 32 条
[1]  
Ahuja RK, 1995, NETWORK FLOWS THEORY
[2]  
[Anonymous], 1896, Cours dEconomie Politique
[3]  
[Anonymous], 2005, MULTICRITERIA OPTIMI
[4]  
[Anonymous], 2008, MULTIOBJECTIVE DECIS
[5]  
Bazaraa Mokhtar S., 2004, Linear Programming and Network Flows
[6]   Statistical analysis of computational tests of algorithms and heuristics [J].
Coffin, M ;
Saltzman, MJ .
INFORMS JOURNAL ON COMPUTING, 2000, 12 (01) :24-44
[8]   On the computation of all supported efficient solutions in multi-objective integer network flow problems [J].
Eusebio, Augusto ;
Figueira, Jose Rui .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 199 (01) :68-76
[9]  
FIGUEIRA JR, 2000, 32000 MSG U COIMBR F, P191
[10]  
FIGUEIRA JR, 2001, FILTERING ALGO UNPUB