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

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.


90C29 Multi-objective and goal programming
90C10 Integer programming
Full Text: DOI Link


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.