Program 2014

September 11, 18:00-21:00 – Welcome Reception
September 12, 9:00-18:00 – Scientific Program
September 12, 19:30 – Workshop Dinner

Scientific Program:

9:00 – 10:00 Opening and Keynote I

9:10 – 10:00: Matthias Ehrgott, Lancaster University Management School:
Bridging the Gap Between Real-world Decision Making and Mathematics: Multiobjective Optimisation in Action (Abstract)
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.

10:00 – 10:10 Break

10:10 – 11:25 Session 1 – Applications I

10:10 – 10:35: Axel Werner, Zuse-Institut Berlin:
Solving ILPs with three and more objectives (Abstract)
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)
10:35 – 11:00: Sebastian Schenker, Zuse-Institut Berlin:
Multi-criteria linear programming with reverse search (Abstract)
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)
11:00 – 11:25: Fabien Tricoire, University of Vienna:
Linear programming for bi-objective stochastic logistics (Abstract)
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)

11:25 – 11:40 Coffee Break

11:40 – 13:10 Session 2 – Branch-and-Bound Algorithms

11:40 – 12:10: Valentina Cacchiani, University of Bologna:
A branch-and-bound algorithm for convex multi-objective Mixed Integer Non-Linear Programming Problems (Abstract)
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.)
12:10 – 12:40: Pietro Belotti, FICO:
A branch-and-bound algorithm for biobjective mixed integer linear optimization (Abstract)
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.)
12:40 – 13:10: Thomas Riis Stidsen, Technical University of Denmark:
Parallelization of Multi-Objective Branch & Bound Algorithms (Abstract)
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)

13:10 – 14:00 Lunch Break

14:00 – 15:30 Session 3 – Optimization with Three or More Objectives

14:00 – 14:30: Fritz Bökler, Technische Universität Dortmund:
Running Time Analyses of Benson Type Algorithms with an Application to Multiobjective Combinatorial Optimization Problems (Abstract)
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)
14:30 – 15:00: Kerstin Dächert, University of Wuppertal:
A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems (Abstract)
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.)
15:00 – 15:30: Jonas Ide, Georg-August-Universität Göttingen:
Set-based minmax robust efficiency for uncertain multi-objective optimization (Abstract)
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)

15:30 – 15:50 Coffee Break

15:50 – 16:50 Session 4 – Applications II

15:50 – 16:20: Marta Pascoal, University of Coimbra:
Finding bicriteria shortest pairs of disjoint paths: related problems and algorithms (Abstract)
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.)
16:20 – 16:50: Nicolas Jozefowiez, Université de Toulouse:
On the use of column generation for bi-objective vehicle routing problems (Abstract)
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.)

16:50 – 17:00 Break

17:00 – 18:00 Keynote II and Closing
17:00 – 17:50: Anthony Przybylski and Xavier Gandibleux, University of Nantes:
Multi-objective branch and bound: survey, architecture, application

Branch and bound is a well-known generic method for computing an optimal
solution of a single objective optimization problem. Until now, rather few
multi-objective branch and bound algorithm have been proposed. This
situation is not surprising as the contributions on the extensions of the
components of the branch and bound for multi-objective optimization are
This talk presents a state-of-the-art of multi-objective branch and bound.
It focusses on the contributions belonging to the class of optimization
problems who has received the most of attention in this context from 1983
until 2014: the linear optimization problems with (1) zero-one variables
and (2) mixed 0-1/continuous variables. Moreover, only papers aiming to
compute a complete set of efficient solutions are discussed. An example of
algorithm for the 0/1 Multi Objective Uncapacitated Facility Location
problem is presented. Here, the multi-objective branch and bound provides
a paving of the objective space, containing the potential exact
non-dominated points.