On finding representative non-dominated points for bi-objective integer network flow problems

• Published in: Computers & operations research 2014-08, Vol.48, p.1-10
• Main Authors: Eusébio, A., Figueira, J.R., Ehrgott, M.
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Bi-objective network flow problem; Branch & bound algorithms; Decision theory. Utility theory; Effectiveness; Exact sciences and technology; Flows in networks. Combinatorial problems; Integer programming; Integers; Iterative methods; Mathematical problems; Mathematical programming; Multi-objective optimisation; Network flow problem; Network optimisation; Networks; Operational research and scientific management; Operational research. Management science; Operations research; Representation; Representations; Studies; Variability; ε-Constraint method
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2014.02.009

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 ε-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 ε-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.