2018/08/06 by László Csirmaz, Csirmaz, Laszlo · 3 citations
Computer Science · Mathematics · #Advanced Multi-Objective Optimization Algorithms #Advanced Optimization Algorithms Research
paper · pdf · doi:10.48550/arxiv.1808.01786
Benson's outer approximation algorithm and its variants are the most\nfrequently used methods for solving linear multiobjective optimization\nproblems. These algorithms have two intertwined components: one-dimensional\nlinear optimization one one hand, and a combinatorial part closely related to\nvertex numeration on the other. Their separation provides a deeper insight into\nBenson's algorithm, and points toward a dual approach. Two skeletal algorithms\nare defined which focus on the combinatorial part. Using different\nsingle-objective optimization problems - called oracle calls - yield different\nalgorithms, such as a sequential convex hull algorithm, another version of\nBenson's algorithm with the theoretically best possible iteration count, the\ndual algorithm of Ehrgott, L "ohne and Shao, and the new algorithm. The new\nalgorithm has several advantages. First, the corresponding one-dimensional\noptimization problem uses the original constraints without adding any extra\nvariables or constraints. Second, its iteration count meets the theoretically\nbest possible one. As a dual algorithm, it is sequential: in each iteration it\nproduces an extremal solution, thus can be aborted when a satisfactory solution\nis found. The Pareto front can be "probed" or "scanned" from several directions\nat any moment without adversely affecting the efficiency. Finally, it is well\nsuited to handle highly degenerate problems where there are many linear\ndependencies among the constraints. On problems with ten or more objectives the\nimplementation shows a significant increase in efficiency compared to Bensolve\n- due to the reduced number of iterations and the improved combinatorial\nhandling.\n