Multi-objective integer programming: a general approach for generating all non-dominated solutions. (English) Zbl 1176.90554

Özlen, Melih; Azizoğlu, Meral

Eur. J. Oper. Res. 199, No. 1, 25-35 (2009).

Summary: We develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical \(\epsilon \)-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical \(\epsilon \)-constraint method on the bi-objective integer programming problem for the sake of completeness and comment on its efficiency. Then present our method on tri-objective integer programming problem and then extend it to the general MOIP problem with \(k\) objectives. A numerical example considering tri-objective assignment problem is also provided.

MSC:

90C29	Multi-objective and goal programming
90C10	Integer programming

Keywords:

multiple objective programming; integer programming

References:

[1]	Ehrgott, M., A discussion of scalarization techniques for multiple objective integer programming, Annals of Operational Research, 147, 343-360 (2006) · Zbl 1188.90236
[2]	Ehrgott, M.; Gandibleux, X., A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spectrum, 22, 425-460 (2000) · Zbl 1017.90096
[3]	(Ehrgott, M.; Gandibleux, X., Multiple Criteria Optimization State of the Art Annotated Bibliographic Surveys: International Series in Operations Research and Management Science, vol. 52 (2002), Springer) · Zbl 1024.00020
[4]	Ehrgott, M.; Gandibleux, X., Approximate solution methods for multiobjective combinatorial optimization, TOP, 12, 1-63 (2004)
[5]	Klamroth, K.; Tind, J.; Zust, S., Integer programming duality in multiple objective programming, Journal of Global Optimization, 29, 1-18 (2004) · Zbl 1073.90041
[6]	Klein, D.; Hannan, E., An algorithm for the multiple objective integer linear programming problem, European Journal of Operational Research, 9, 378-385 (1982) · Zbl 0477.90075
[7]	Laumanns, M.; Thiele, L.; Zitzler, E., An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method, European Journal of Operational Research, 169, 932-942 (2006) · Zbl 1079.90122
[8]	Sylva, J.; Crema, A., A method for finding the set of non-dominated vectors for multiple objective integer linear programs, European Journal of Operational Research, 158, 46-55 (2004) · Zbl 1061.90103
[9]	Sylva, J.; Crema, A., A method for finding well-dispersed subsets of non-dominated vectors for multiple objective mixed integer linear programs, European Journal of Operational Research, 180, 1011-1027 (2007) · Zbl 1122.90055