Enumerating the set of non-dominated vectors in multiple objective integer linear programming
RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 371-387.

An algorithm for enumerating all nondominated vectors of multiple objective integer linear programs is presented. The method tests different regions where candidates can be found using an auxiliary binary problem for tracking the regions already explored. An experimental comparision with our previous efforts shows the method has relatively good time performance.

DOI : 10.1051/ro:2008018
Classification : 90C10, 90C11, 90C29
Mots clés : integer programming, multiple objective programming, parametric programming
@article{RO_2008__42_3_371_0,
     author = {Sylva, John and Crema, Alejandro},
     title = {Enumerating the set of non-dominated vectors in multiple objective integer linear programming},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {371--387},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {3},
     year = {2008},
     doi = {10.1051/ro:2008018},
     mrnumber = {2444493},
     zbl = {1153.90511},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2008018/}
}
TY  - JOUR
AU  - Sylva, John
AU  - Crema, Alejandro
TI  - Enumerating the set of non-dominated vectors in multiple objective integer linear programming
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2008
SP  - 371
EP  - 387
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2008018/
DO  - 10.1051/ro:2008018
LA  - en
ID  - RO_2008__42_3_371_0
ER  - 
%0 Journal Article
%A Sylva, John
%A Crema, Alejandro
%T Enumerating the set of non-dominated vectors in multiple objective integer linear programming
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2008
%P 371-387
%V 42
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2008018/
%R 10.1051/ro:2008018
%G en
%F RO_2008__42_3_371_0
Sylva, John; Crema, Alejandro. Enumerating the set of non-dominated vectors in multiple objective integer linear programming. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 3, pp. 371-387. doi : 10.1051/ro:2008018. http://www.numdam.org/articles/10.1051/ro:2008018/

[1] M.J. Alves and J.o Clímaco, An interactive reference point approach for multiobjective mixed-integer programming using branch and bound. Eur. J. Oper. Res. 124 (2000) 478-494. | MR | Zbl

[2] G.R. Bitran, Linear multiple objective programs with zero-one variables. Math. Program. 13 (1977) 121-139. | MR | Zbl

[3] J. Climaco, C. Ferreira and M.E. Captivo, Multicriteria integer programming: An overview of different algorithmic approaches, in Multicriteria Analysis, edited by J. Climaco, Springer-Verlag, Berlin, 1997, pp. 248-258. | Zbl

[4] COIN-OR, Computational infrastructure for operations research home page, http://www.coin-or.org/, Acceso 26/03/2006.

[5] J. Karaivanova, S. Narula and V. Vassilev, An interactive algorithm for integer programming. Eur. J. Oper. Res. 68 (1993) 344-351. | Zbl

[6] M. Laumanns, L. Thiele and E. Zitzler, An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur. J. Oper. Res. 169 (2006) 932-942. | MR | Zbl

[7] L.M. Rasmussen, Zero-one programming with multiple criteria. Eur. J. Oper. Res. 26 (1986) 83-95. | MR | Zbl

[8] R.M. Soland, The design of multiactivity multifacility systems. Eur. J. Oper. Res. 12 (1983) 95-104. | Zbl

[9] R.E. Steuer, Multiple criteria optimization-theory, computation and application, John Wiley and Sons, (1986). | MR | Zbl

[10] J. Sylva and A. Crema, A method for finding the set of nondominated vectors for multiple objective integer linear programs. Asia-Pacific J. Oper. Res. 158 (2004) 46-55. | MR | Zbl

[11] J. Sylva and A. Crema, A method for finding well-dispersed subsets of nondominated vectors for multiple objective mixed integer linear programs. Eur. J. Oper. Res. 180 (2007) 1011-1027. | MR | Zbl

[12] J. Teghem and P.L. Kunsch, A survey of techniques for finding efficient solutions to multi-objective integer linear programming. Asia-Pacific J. Oper. Res. 3 (1986) 95-108. | Zbl

[13] D. Tenfelde-Podehl, A recursive algorithm for multiobjective combinatorial optimization problems with q criteria. Tech. report, Institut für Mathematik, Technische Universität Graz, (2003).

[14] E.L. Ulungu and J. Teghem, Multi-objective combinatorial optimization problems: A survey. J. Multi-Criteria Decision Anal. 3 (1994), 83-104. | Zbl

Cité par Sources :