A comparison of lower bound set algorithms for multi-objective branch-and-bound

Description

We investigate multi-objective optimisation problems where the multiple objectives are conflicting. Since there is, in the general case, no solution which optimises all objectives simultaneously, the aim is to obtain the Pareto optimal set. The branch-and-bound algorithm is one method that produces this set of solutions. To extend an existing bi-objective branch-and-bound to the three-dimensional case, finding lower bound sets is the first step. Since the computational effort spent obtaining lower bound sets represents a major portion of the whole effort, we investigate three different approaches. Those methods are based on a Benson’s algorithm and its dual variant, on a dichotomic scheme, and on a parametric simplex for multi-objective problems. In this presentation, we compare the performance of all three algorithms by applying them to widely used benchmark problems (assignment problems, knapsack problems, mixed integer problems). Furthermore, we look into factors which influence the efficiency of each algorithm.

Period	05 Sept 2019
Event title	Operations Research 2019
Event type	Conference
Location	GermanyShow on map