The multiobjective discrete optimization problem: A weighted min-max two-stage optimization approach and a bicriteria algorithm

被引:60
作者
Sayin, S [1 ]
Kouvelis, P
机构
[1] Koc Univ, Coll Adm Sci & Econ, TR-34450 Istanbul, Turkey
[2] Washington Univ, John M Olin Sch Business, St Louis, MO 63130 USA
关键词
multiple objective optimization; efficient set; min-max optimization; bicriteria knapsack problem;
D O I
10.1287/mnsc.1050.0413
中图分类号
C93 [管理学];
学科分类号
12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];
摘要
We study the multiple objective discrete optimization (MODO) problem and propose two-stage optimization problems as subproblems to be solved to obtain efficient solutions. The mathematical structure of the first level subproblem has similarities to both Tchebycheff type of approaches and a generalization of the lexicographic max-ordering problem that are applicable to multiple objective optimization. We present some results that enable us to develop an algorithm to solve the bicriteria discrete optimization problem for the entire efficient set. We also propose a modification of the algorithm that generates a sample of efficient solutions that satisfies a prespecified quality guarantee. We apply the algorithm to solve the bicriteria knapsack problem. Our computational results on this particular problem demonstrate that our algorithm performs significantly better than an equivalent Tchebycheff counterpart. Moreover, the computational behavior of the sampling version is quite promising.
引用
收藏
页码:1572 / 1581
页数:10
相关论文
共 24 条
[1]
[Anonymous], EUROPEAN J OPERATION
[2]
LINEAR MULTIPLE OBJECTIVE PROGRAMS WITH ZERO-ONE VARIABLES [J].
BITRAN, GR .
MATHEMATICAL PROGRAMMING, 1977, 13 (02) :121-139
[3]
BOWMAN VJ, 1975, LECTURES NOTES EC MA, V130, P76
[4]
Captivo ME, 2003, COMPUT OPER RES, V30, P1865, DOI 10.1016/S0305-0548(02)00112-0
[5]
AN ALGORITHM FOR THE BI-CRITERION INTEGER PROGRAMMING PROBLEM [J].
CHALMET, LG ;
LEMONIDIS, L ;
ELZINGA, DJ .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 25 (02) :292-300
[6]
A survey and annotated bibliography of multiobjective combinatorial optimization [J].
Ehrgott M. ;
Gandibleux X. .
OR-Spektrum, 2000, 22 (4) :425-460
[7]
Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach [J].
Ehrgott, M ;
Skriver, AJV .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 147 (03) :657-664
[8]
EHRGOTT M, 1997, MULTIPLE CRITERIA OP
[9]
ALGORITHMS FOR NONLINEAR INTEGER BICRITERION PROBLEMS [J].
ESWARAN, PK ;
RAVINDRAN, A ;
MOSKOWITZ, H .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1989, 63 (02) :261-279
[10]
*ILOG, 2002, ILOG CPLEX 8 0 US MA