This talk presents several studies that illustrate the power of multiobjective optimisation in supporting decision makers facing conflicting goals. These studies are drawn from the fields of
transportation (airline operations, traffic modelling), health (radiation therapy treatment), and manufacturing (composite materials). I will illustrate the widely differing mathematical methods used in these applications, but emphasise the common benefits of the multiobejctive optimisation approach: The improved understanding of the problem achieved through additional insight into the problem structure; the improved support for decision makers through the ability to properly account for trade-offs between conflicting goals; and last but not least, the considerable benefits that result in terms of quality of decisions and/or improved decision making processes.

We discuss two methods for solving integer linear programs with three objectives that can be generalized straightforward to multiobjective ILP problems. We computationally compare implementations of the methods by means of problems arising in telecommunication access network planning. (Joint work with M.Leitner, I. Ljubic, M. Sinnl)

This talk presents a reverse search algorithm for multi-criteria linear programming for enumerating efficient basic feasible solutions. In contrast to multi-criteria simplex approaches which require extensive bookkeeping of already visited efficient basic feasible solutions the reverse search algorithm works without bookkeeping and lookup of already visited solutions. (Joint work with R. Borndörfer and M.Skutella)

Real world logistics optimisation problems can incorporate specific features that are difficult to integrate in optimisation approaches that are based on linear programming (LP). This includes features such as uncertainty, robustness, multiple optimisation criteria without a clear picture on how to combine them into a unique preference function, non-linearity of objectives and constraints, intractability of the LP, etc. It is even harder to optimise problems in which several of these features are combined. We tackle bi-objective stochastic optimisation, a topic on which existing contributions are scarce. We develop different approaches based on LP. These approaches are then applied to the context of bi objective stochastic logistics, by looking at generalisations of well-known facility location problems. (Joint work with Walter Gutjahr, Sophie Parragh)

We propose a general-purpose branch-and-bound algorithm for solving convex multi-objective mixed integer non-linear programming problems, which are characterized by a discontinuous Pareto set, due to the integrality requirements. The proposed algorithm is theoretically exact: it consists of a standard branch-and-bound extended to deal with multiple objectives and convex non-linear functions. In particular, it requires to resolve, at each leaf node of the branch-and-bound tree, a convex multi-objective non-linear programming problem. The latter is solved by altering the weights in a Weighted Sum approach. In order to obtain a computationally practical method, only a finite number of weights are evaluated, thus obtaining an approximate the Pareto set. A tailored refinement procedure is designed, which allows to improve the approximated Pareto set. As a proof-of-concept, we present the results obtained on a real-world application concerning power generation. (Joint work with Claudia D’Ambrosio.)

Solving a biobjective optimization problem requires enumerating all of its Pareto-optimal solutions. If the problem is a continuous linear program, the Pareto set can be obtained by applying
techniques such as the parametric simplex method. For the mixed integer linear programming (MILP) case, one needs an implicit enumeration technique such as branch and bound (BB). We describe an implementation of a BB algorithm for biobjective MILPs. Among the main features of the algorithm is a set of fathoming rules to eliminate portions of the feasible set by proving that they contain no Pareto optimal solutions. We report on results obtained using an implementation of our BB algorithm, which was written using a
well-known commercial MILP solver. (Joint work with Banu Soylu,
Erciyes University, and Margaret Wiecek, Clemson University.)

Despite the advances which has been achieved in the last 5 years regarding the size of Multi-Objective Mixed Integer Programming models which can be solved, there is still a long way to go before real-life problems of significant size can be handled. An obvious way to improve the speed is to apply parallelization of the Multi-Objective Branch & Bound algorithms. There are however problems which makes the standard approach for Single-Objective Branch & Bound algorithms less promising. In this talk we will briefly present a new approach which minimizes the amount of information necessary to exchange between the different parallel processes of the parallel Multi-Objective Branch & Bound algorithm. (Joint work with Kim Allan Andersen, University of Aarhus)

Although multi objective optimization often appears in practical applications, it is usually regarded as too expensive to pursue. Albeit, theoretical running time guarantees are seldom considered in the literature. In this talk, we present the first running time analyses of Bensons outer approximation algorithms and its dual variant. We show that they run in polynomial total time, i.e., polynomial in the input and the output size, for a fixed but arbitrary number of objectives with respect to a set of LP oracle problems. Moreover, we suggest improvements to remove an exponential running time burden from both algorithms. Using the above results, we prove that if the single objective optimization variant of a multiobjective combinatorial optimization problem can be solved in strongly polynomial time then enumerating the extreme nondominated points of the Pareto-frontier can be done in polynomial total time for every fixed number of objectives. Since this was only known for biobjective problems, our results close the gap between these problems and problems with three and more objectives. Additionally, we show that this can be accelerated by using our suggested improvements. This enables us to present—to the best of our knowledge—the first computational study for enumerating the extreme nondominated value vectors of the multiobjective assignment and spanning tree problem with more than four objectives. The results show that this algorithm is very competitive compared to the small number of algorithms available to solve this problem for three and four objectives. (Joint work with Petra Mutzel)

Multi-objective optimization problems are often solved by a sequence of parametric single-objective problems, so-called scalarizations. If the set of nondominated points is finite, the entire nondominated set can be generated in this way. In the bicriteria case it is well known that this can be realized by an adaptive approach which requires the solution of at most 2|N|-1 subproblems, where N denotes the nondominated set of the underlying problem and a subproblem corresponds to a scalarized problem. For problems with more than two criteria, no methods were known up to now for which the number of subproblems depends linearly on the number of nondominated points.
We present a new procedure for finding the entire nondominated set of tricriteria optimization problems for which the number of subproblems to be solved is bounded by 3|N|-2, hence, depends linearly on the number of nondominated points. The approach includes an iterative update of the search region that, given a (sub-)set of nondominated points, describes the area in which additional nondominated points may be located. If the e-constraint method is chosen as scalarization, the upper bound can be improved to 2|N|-1. (Joint work with Kathrin Klamroth.)

When solving real world problems with optimization techniques, uncertainties in the problem formulation often have to be taken into account due to disturbances or fluctuation of the input data. For handling these uncertainties in single objective problems, robust optimization is an important tool as it incorporates the uncertain data already into the optimization step even though no probabilistic information on the data might be given.
Even though extensions of the several existing concepts of robustness to the multi-objective setting are of high practical and theoretical interest, this field of research has been investigated only very recently.
In this talk, we present an extension of the most important concept of robustness for single objective optimization (namely the concept of minmax robustness (cf., e.g., Ben-Tal et al., 2009) to multi-objective optimization problems, investigate its properties, and present techniques for calculating minmax robust efficient solutions.
For the latter, we introduce the approach of ‘robust scalarizations’ which are adaptations of well known solution techniques for deterministic multi-objective optimization problems to the uncertain setting, such as the weighted sum scalarization, epsilon constraint method, and Tschebyscheff-methods.
We investigate the connection between these solution techniques and discuss differences and parallels to the deterministic setting.
The talk is concluded with some visualizations of sets of robust efficient solutions found by the various solution techniques. (Joint work with M. Ehrgott, A. Schöbel)

Pairs of disjoint paths between two nodes in a network provide a primary path as well as a backup path, such that the first can be used in case one of the arcs of the second fails. In this talk we address the bicriteria version of the shortest pair of disjoint paths problem and some related problems, and discuss exact algorithms to find their non-dominated solutions. (Joint work with Maria Eugenia Captivo and Joao Climaco.)

We present a generalized column generation scheme to compute bound sets for bi-objective integer linear programs. We also present different strategies for implementing the generalized algorithm and refinements for the case where one of the objectives is a min-max objective. We apply the proposed method to extended formulations for bi-objective vehicle routing problems, such as the bi-objective multi-vehicle covering tour problem. The results show that good lower and upper bounds are obtained in reasonable times if columns are efficiently managed. (Joint work with C. Artigues and B. M. Sarpong.)