Program 2016

A pdf of the program can be found here.

The group photo can be found here.

June 24, 8:30-09:00 – Registration
June 24, 9:00-18:00 – Scientific Program

Scientific Program:

9:00 – 10:00 Opening and Keynote I
Chair: Matthias Ehrgott

09:00 – 09:10: Opening

09:10 – 10:00: Gabriele Eichfelder (Technische Universität Ilmenau).
Multi-objective decision uncertainty and set optimization with the set approach(slides)

Set optimization problems arise in multi-objective optimization for instance whenever robust solutions are considered. We present here the concept of decision robust efficiency which allows to handle decision uncertainty in multi-objective optimization. This occurs when values of decision variables cannot be put into practice exactly. Then, for each feasible point, we have to consider the set of all of its possible realizations. Therefore, one has to compare sets instead of points for this optimality notion. We discuss how this concept is related to optimality notions in set optimization. We also give an overview over related concepts in set optimization based on different set relations and discuss their practical relevance. First approaches to solve such problems are also presented.

10:00 – 10:10 Break

10:10 – 11:25 Session 1 – New Exact Solution Algorithms
Chair: Michael Stiglmayr

10:10 – 10:35: Jörg Fliege (University of Southampton).
An SQP-type method for constrained and unconstrained nonlinear multiobjective optimization(slides)

We propose a method for constrained and unconstrained nonlinear multiobjective optimization problems that is based on an SQP-type approach. The proposed algorithm maintains a list of nondominated points that is improved both for spread along the Pareto front and optimality by solving single-objective constrained optimization problems. These single-objective problems are derived as SQP problems based on the given nondominated points. Under appropriate differentiability assumptions we discuss convergence to local optimal Pareto points. We provide numerical results for a set of unconstrained and constrained multiobjective optimization problems in the form of performance and data profiles, where several performance metrics are used. The numerical results confirm the superiority of the proposed algorithm against a state-of-the-art multiobjective solver and a classical scalarization approach, both in the quality of the approximated Pareto front and in the computational effort necessary to compute the approximation.

10:35 – 11:00: Ethan Liu (Lancaster University).
Primal and Dual Methods for Linear Optimisation over the Non-dominated Set of a Multi-objective Linear Programme and Computing the Nadir Point(slides)

This study presents two new algorithms for the optimisation of a linear function over the non-dominated set of a multi-objective linear programme (MOLP). A primal method is developed based on a revised version of Benson’s outer approximation algorithm to compute the non-dominated set of an MOLP. A dual method derived from the dual variant of the outer approximation algorithm is proposed. We compare the two new algorithms with several algorithms from the literature on a set of randomly generated instances. The results show that the new algorithms are considerably faster than the competitors. We adapt the two methods for the determination of the nadir point of an MOLP. The nadir point is characterized by the componentwise worst values of the non-dominated points of a multi-objective optimisation problem and is a pre-requite for many multi-criteria decision making (MCDM) procedures. Computational experiments against another exact method for this purpose from the literature reveal that the new methods are much faster than the competitor.

11:00 – 11:25: Sune Lauth Gadegaard (Aarhus Universitet).
Bound set based branch-and-cut algorithms for bi-objective combinatorial optimization problems(slides)

In this talk we present two branch-and-cut algorithms for bi-objective combinatorial optimization (BOCO) problems. Both are based on bound sets, but the first uses an explicitly generated lower bound set obtained from the bi-objective LP-relaxation, whereas the second takes the lower bound set implicitly into account.

We propose a cutting plane algorithm used to strengthen the lower bound sets, and we show how the explicitly generated lower bound sets can be updated so the bi-objective LP relaxation does not need to be solved at each branching node. Furthermore, we show how the newly proposed Pareto branching strategy can be strengthened to what we call extended Pareto branching.

We conclude by presenting results obtained with the algorithms and compare them to an implementation of the two-phase method.

11:25 – 11:40 Coffee Break

11:40 – 12:40 Session 2 – Representative Sets
Chair: Alexander Engau

11:40 – 12:10: Tobias Kuhn (Technische Universität Kaiserslautern).
A coverage-based box-algorithm to compute a representation for optimization problems with three objective functions(slides)

In this talk, we present a method for computing a substitute of the nondominated set, a so-called representation system, for tricriteria optimization problems. Our algorithm is easy to implement, it is flexibly applicable to a wide range of problems, and it takes several quality measures which have been proposed in the literature into account. The resulting representation system satisfies provably certain quality levels and, thus, it may be utilized to make proper and confident decisions.

12:10 – 12:40: Michael Stiglmayr (Bergische Universität Wuppertal).
Representation of the non-dominated set of multiobjective combinatorial optimization problems(slides)

Since the cardinality of the non-dominated set of combinatorial optimization problems is often too large to present to a decision maker, the selection of a representative subset is of particular interest. This talk focuses on the computation of good represenations with respect to quality measures like uniformity, coverage, epsilon-indicator or hypervolume. Since the scope of these quality measures is different, the representation problem itself can be considered as multiobjective. In the biobjective case the multiobjective representation problems can be solved efficiently using either dynamic programming or a theshold approach.

12:40 – 12:50 Some Information
12:50 – 14:00 Lunch Break

14:00 – 15:30 Session 3 – Applications and Complexity
Chair: Marc Goerigk

14:00 – 14:30: Britta Schulze (Bergische Universität Wuppertal).
Unconstrained Binary Multiobjective Optimization: Weight Space Decomposition, Arrangements of Hyperplanes and Zonotopes(slides)

We consider a particularly simple class of unconstrained binary optimization problems with two or more objective functions (UBMOP). The cost coefficients can be positive or negative. In this case, there is a one to one correspondence between (1) the extreme supported solutions of UBMOP, (2) a weight space decomposition, (3) the cells of an associated arrangement of hyperplanes, and (4) the nondominated extreme points of a corresponding zonotope. While the interrelation between (1) and (2) holds for general MOCO problems, (3) and (4) rely on the special structure of UBMOP. We take advantage of these relations for efficiently computing the set of extreme supported solutions. As a side effect, nonextreme supported solutions can easily be identified in the arrangement of hyperplanes. Furthermore, for multiobjective knapsack problems with some positive and some negative cost coefficients, the weight space decomposition of a corresponding unconstrained instance of UBMOP can be used to initialize a multiobjective dichotomic search. The efficiency of this approach depends on the constraint slackness of the knapsack problem.

14:30 – 15:00: Alexander Engau (University of Colorado Denver).
Improved discriminant analysis using multi-hyperplane separation and multi-criteria optimization(slides)

Discriminant analysis is a key task for classification, data mining and machine or supervised learning. This presentation begins with a brief overview of some of the most recent exact approaches for the classification problem based on multi-hyperplane separation for piecewise linear models and cutting decision tree induction. To improve their robustness and overall performance, we then focus on a variety of new extensions including the analysis and combination of different objectives using goal programming and multicriteria optimization. Computational results on a large collection of real-world applications including financial and medical data sets will be reported.

15:00 – 15:30: Alain Zemkoho (University of Southampton).
Multiobjective bilevel optimization: A set valued optimization view point(slides)

We consider a multiobjective bilevel optimization problem, and also its scalar objective special case. Based on an apparently naïve set-valued optimization transformation of the problem, it was discovered that most (if not all) well-known results on bilevel optimization optimality conditions theory can be related to this model. In this talk, we will present these results and the connections between the aforementioned set-valued model and the standard optimistic and pessimistic bilevel optimization problems. Some possible paths to solution algorithms and illustrative examples will also be discussed.

15:30 – 15:50 Coffee Break

15:50 – 16:50 Session 4 – Uncertainty and Multi-Objective Optimisation
Chair: Jörg Fliege

15:50 – 16:20: Corinna Krüger (Georg-August-Universität Göttingen).
On Decision Uncertainty in Multiobjective Linear Programming(slides)

We study uncertain multiobjective linear programs in which decision variables are uncertain, i.e., decisions may not be realized as they have been planned. We assume that the deviation between the planned and the realized variable is an element of a polyhedral uncertainty set. The uncertainty is modeled with a point-to-set map by adding all possible perturbations to the considered decision variable. Two cases are considered. At first, the uncertainty is placed in the objective functions and we show that it can be neglected because it does not affect the efficient set of the linear program. Secondly, the uncertainty is carried in the constraints which makes the uncertain linear program amenable to be treated with the robust optimization framework of Ben-Tal and Nemirovski.
We present two ways of generalizing their definition of the robustness gap (RG) from single-objective to multiobjective optimization. On the one hand we quantify the RG by the distance between Pareto sets. On the other hand, the RG is considered as the objective value of a quadratic program. We show that both concepts are closely related with each other.

16:20 – 16:50: Marc Goerigk (Lancaster University).
Robust and Multiobjective Optimisation: Opportunities and Challenges(slides)

We collect the various ways robust and multiobjective optimisation have been interacting in the recent literature: This includes adding robustness as a new objective function to a singeobjective problem, considering the robust counterpart of a multiobjective problem, or using a multiobjective perspective on a classic robust optimisation problem. We discuss the new research challenges this creates, but also analyse the opportunities for both fields to profit from each other.

16:50 – 17:00 Break

17:00 – 18:00 Keynote II and Closing
Chair: Matthias Ehrgott

17:00 – 17:50: Firdevs Ulus (Bilkent Üniversitesi).
Algorithms for Convex Vector Optimization Problems (slides)

In order to solve convex vector optimization problems (CVOPs), a Benson type algorithm and its dual variant have been proposed recently. These algorithms ‘solve’ CVOPs in any size, where the objective and constraint functions are not necessary differentiable and the ordering cones are allowed to be any solid pointed polyhedral cone. Both algorithms work in the image space and they find a ‘finite weak ε-solution’ which provides an inner and an outer approximation of the efficient frontier. These algorithms work well if the feasible region is compact which implies that (1) the problem is bounded in the sense that the ‘ideal objective’ is finite and (2) a finite weak ε-solution to the problem exists. However, in many applications, the feasible region is not necessarily compact and the problem may be unbounded. In this talk, in addition to presenting the algorithms for bounded CVOPs, the aim is to discuss the following questions: 1- Is there a finite solution concept for unbounded convex optimization problems? 2- If this is the case, are there conditions which guarantee the existence of such a solution? 3- Can we extend the forementioned algorithms to unbounded CVOPs?