On finding representative non-dominated points for bi-objective integer network flow problems. (English) Zbl 1348.90154
Summary: This paper proposes a new algorithm to find a representation of the set of all non-dominated points of the bi-objective integer network flow problem. The algorithm solves a sequence of \(\epsilon\)-constraint problems with a branch-and-bound algorithm to find a subset of non-dominated points that represents the set of all non-dominated points well in the sense of coverage or uniformity. At each iteration of the algorithm, one non-dominated point, determined by solving one \(\epsilon\)-constraint problem, is added to the representation until it is guaranteed that the representation has the desired quality. Computational experiments on different problem types show the efficacy of the algorithm.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C10 | Integer programming |
| 90C29 | Multi-objective and goal programming |
Keywords:
multi-objective optimisation; network optimisation; integer programming; \(\epsilon\)-constraint method; bi-objective network flow problem; representationReferences:
| [1] | Ahuja, R.; Magnanti, T.; Orlin, J., Network flows: theory, algorithms, and applications (1993), Prentice Hall: Prentice Hall NJ, ISBN 0-13-617549-X · Zbl 1201.90001 |
| [2] | Ruhe, G., Complexity results for multicriterial and parametric network flows using a pathological graph of Zadeh, Z Oper Res, 32, 9-27 (1988) · Zbl 0641.90037 |
| [3] | Raith, A.; Ehrgott, M., A two-phase algorithm for the biobjective integer minimum cost flow problem, Comput Oper Res, 36, 1945-1954 (2009) · Zbl 1179.90303 |
| [4] | Hamacher, H.; Pedersen, C.; Ruzika, S., Multiple objective minimum cost flow problemsa review, Eur J Oper Res, 176, 1404-1422 (2007) · Zbl 1102.90059 |
| [5] | Eusébio, A.; Figueira, J., Finding non-dominated solutions in bi-objective integer network flow problems, Comput Oper Res, 36, 2554-2564 (2009) · Zbl 1179.90049 |
| [6] | Steuer, R., Multiple criteria optimization: theory, computation, and application (1986), John Wiley & Sons: John Wiley & Sons New York, ISBN 0-471-88846-X · Zbl 0663.90085 |
| [7] | Gass, S.; Saaty, T., The computational algorithm for the parametric objective function, Naval Res Logist Q, 2, 39-45 (1955) |
| [8] | Chankong, V.; Haimes, Y., Multiobjective decision making: theory and methodology (1983), North-Holland: North-Holland New York, ISBN 0-444-00710-5 · Zbl 0622.90002 |
| [9] | Bryson, N., Parametric programming and Lagrangian relaxationthe case of the network flow problem with a single side-constraint, Comput Oper Res, 18, 129-140 (1991) · Zbl 0742.90078 |
| [10] | Faulkenberg, S.; Wiecek, M., On the quality of discrete representations in multiple objective programming, Optim Eng, 11, 3, 423-440 (2010) · Zbl 1273.90184 |
| [11] | Ruzika, S.; Wiecek, M., Approximation methods in multiobjective programming, J Optim Theory Appl, 126, 473-501 (2005) · Zbl 1093.90057 |
| [12] | Sayin, S., Measuring the quality of discrete representations of efficient sets in multiple objective mathematical programming, Math Progr, 87, 543-560 (1999) · Zbl 0970.90090 |
| [13] | Bazaraa, M.; Jarvis, J.; Sherali, H., Linear programming and network flows (2005), John Wiley & Sons: John Wiley & Sons New York, ISBN 0-471-63681-9 · Zbl 1061.90085 |
| [14] | Schechter, M.; Steuer, R., A correction to the connectedness of the Evans-Steuer algorithm of multiple objective linear programming, Found Comput Decis Sci, 30, 351-359 (2005) · Zbl 1204.90100 |
| [15] | Jacobs, R. H., Geometry (1987), W.H. Freeman and Company: W.H. Freeman and Company New York, ISBN 0-7167-1745-X |
| [16] | Klingman, D.; Napier, A.; Stutz, J., NETGENa program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems, Manag Sci, 20, 814-821 (1974) · Zbl 0303.90042 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
