Search

Ridepooling services require efficient optimization algorithms to simultaneously plan routes and pool users in shared rides. We consider a static dial-a-ride problem (DARP) where a series of origin-destination requests have to be assigned to routes of a fleet of vehicles. Thereby, all requests have associated time windows for pick-up and delivery, and may be denied if they can not be serviced in reasonable time or at reasonable cost. Rather than using a spatial representation of the transportation network we suggest an event-based formulation of the problem, resulting in significantly improved computational times. While the corresponding MILP formulations require more variables than standard models, they have the advantage that capacity, pairing and precedence constraints are handled implicitly. The approach is tested and validated using a standard IP-solver on benchmark data from the literature. Moreover, the impact of, and the trade-off between, different optimization goals is evaluated on a case study in the city of Wuppertal (Germany).

In engineering applications one often has to trade-off among several objectives as, for example, the mechanical stability of a component, its efficiency, its weight and its cost. We consider a biobjective shape optimization problem maximizing the mechanical stability of a ceramic component under tensile load while minimizing its volume. Stability is thereby modeled using a Weibull-type formulation of the probability of failure under external loads. The PDE formulation of the mechanical state equation is discretized by a finite element method on a regular grid. To solve the discretized biobjective shape optimization problem we suggest a hypervolume scalarization, with which also unsupported efficient solutions can be determined without adding constraints to the problem formulation. FurthIn this section, general properties of the hypervolumeermore, maximizing the dominated hypervolume supports the decision maker in identifying compromise solutions. We investigate the relation of the hypervolume scalarization to the weighted sum scalarization and to direct multiobjective descent methods. Since gradient information can be efficiently obtained by solving the adjoint equation, the scalarized problem can be solved by a gradient ascent algorithm. We evaluate our approach on a 2 D test case representing a straight joint under tensile load.

This article focuses on the optimization of a complex system which is composed of several subsystems. On the one hand, these subsystems are subject to multiple objectives, local constraints as well as local variables, and they are associated with an own, subsystem-dependent decision maker. On the other hand, these subsystems are interconnected to each other by global variables or linking constraints. Due to these interdependencies, it is in general not possible to simply optimize each subsystem individually to improve the performance of the overall system. This article introduces a formal graph-based representation of such complex systems and generalizes the classical notions of feasibility and optimality to match this complex situation. Moreover, several algorithmic approaches are suggested and analyzed.

In this paper, the identification and exclusion of very distant facilities in center location problems is modeled by k-max functions: One or several new facilities are to be located such that not the largest, but the kth largest weighted distance to the customers is minimized, with k ≥ 1. It is shown that k-max location problems on networks can be solved efficiently by enumerating candidate solutions from a finite dominating set (FDS) that is independent from the particular value of k. As a consequence, k-max locations can be found for all reasonable values of k at little extra cost as compared to a single solver call, for one fixed value of k. The location of several new facilities is naturally more complex. An FDS based recursive algorithm is developed for this case that allows the exact solution of medium size instances.

We introduce a new interactive multiobjective optimization method operating in the objective space called Nonconvex Pareto Navigator . It extends the Pareto Navigator method for nonconvex problems. An approximation of the Pareto optimal front in the objective space is first generated with the PAINT method using a relatively small set of Pareto optimal outcomes that is assumed to be given or computed prior to the interaction with the decision maker. The decision maker can then navigate on the approximation and direct the search for interesting regions in the objective space. In this way, the decision maker can conveniently learn about the interdependencies between the conflicting objectives and possibly adjust one’s preferences. To facilitate the navigation, we introduce special cones that enable extrapolation beyond the given Pareto optimal outcomes. Besides handling nonconvexity, the new method contains new options for directing the navigation that have been inspired by the classification-based interactive NIMBUS method. The Nonconvex Pareto Navigator method is especially well-suited for computationally expensive problems, because the navigation on the approximation is computationally inexpensive. We demonstrate the method with an example. Besides proposing the new method, we characterize interactive navigation based methods in general and discuss desirable properties of navigation methods overall and in particular with respect to Nonconvex Pareto Navigator .

This paper describes the project GivEn that develops a novel multiobjective optimization process for gas turbine blades and vanes using modern “adjoint” shape optimization algorithms. Given the many start and shut-down processes of gas power plants in volatile energy grids, besides optimizing gas turbine geometries for efficiency, the durability understood as minimization of the probability of failure is a design objective of increasing importance. We also describe the underlying coupling structure of the multiphysical simulations and use modern, gradient based multiobjective optimization procedures to enhance the exploration of Pareto-optimal solutions.

The reliable simulation of pedestrian movement is an essential tool for the security aware design and analysis of buildings and infrastructure. We developed HyDEFS, an event-driven dynamic flow simulation software which is designed to simulate pedestrian movement depending on varying routing decisions of the individual users and varying constraints. HyDEFS uses given density depending velocities to model congestions and evaluates flow distributions with respect to average and maximum travel time. This is of particular importance when considering evacuation scenarios. We apply HyDEFS on two small networks and cross validate its results by time-discrete and time-continuous calculations.

In practical situations, complex systems are often composed of subsystems or subproblems with single or multiple objectives. These subsystems focus on different aspects of the overall system, but they often have strong interactions with each other and they are usually not sequentially ordered or obviously decomposable. Thus, the individual solutions of subproblems do not generally induce a solution for the overall system. Here, we strive to identify "re-composition architectures" of such "interwoven" systems. Our intention is to connect the subsystems adequately, analyze the resulting performance, model/solve the overall system, and improve the overall solution instead of just solving each subsystem separately. We review recent developments in this field and discuss modeling and solution paradigms in a general and unified framework using the example of an interwoven system consisting of two interacting subsystems.

We consider the simultaneous optimization of the reliability and the cost of a ceramic component in a biobjective PDE constrained shape optimization problem. A probabilistic Weibull-type model is used to assess the probability of failure of the component under tensile load, while the cost is assumed to be proportional to the volume of the component. Two different gradient-based optimization methods are suggested and compared at 2D test cases. The numerical implementation is based on a first discretize then optimize strategy and benefits from efficient gradient computations using adjoint equations. The resulting approximations of the Pareto front nicely exhibit the trade-off between reliability and cost and give rise to innovative shapes that compromise between these conflicting objectives.

Every student in North Rhine-Westphalia, Germany, studying to become a teacher, has to complete a semester of practical training at a school. In order to assign students to schools and thereby satisfy the requests of the students, without exceeding capacity limitations at the schools, a discrete, assignment-like optimization problem is formulated and solved to optimality. Since students study two major subjects, a school has to provide capacities in both of them to be a candidate for a feasible assignment. An additional requirement comes from the fact that students have to attend seminar courses in the respective subjects during their internship. The overall optimization problem is a generalized assignment problem, which has an alternative interpretation as a fixed-charge multicommodity flow problem.

Multiobjective optimization problems are often solved using methods from scalar-valued optimization: One – or a series of – associated scalarizations are formulated and solved using appropriate methods from scalar-valued optimization. Conversely, tools from multiobjective optimization can be applied in combination with appropriate filtering techniques to approach scalar-valued optimization problems. This shows that both topics have a substantial relationship which can be exploited for mutual benefit. In this work we analyze this relationship and suggest to adapt a deterministic multiobjective branch-and-bound algorithm (originally designed for nonconvex multiobjective optimization problems) to solve scalar-valued optimization problems with nonconvex constraints.

Building on previous work of the authors, this paper formally defines and reviews the first approach, referred to as navigation, towards a common understanding of search and decision making strategies to identify the most preferred solution among the Pareto set for a multiobjective optimization problem. In navigation methods, the decision maker interactively learns about the problem, while the decision support system learns about the preferences of the decision maker. This work introduces a detailed view on navigation leading to the identification of integral components and features. A number of different existing navigation methods are reviewed and characterized. Finally, an overview of applications involving navigation is given, and promising future research directions are discussed.

General 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, and if an appropriate scalarization is employed, 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, given an appropriate initial search space, requires the solution of a number of subproblems which is at most two times the number of nondominated points. For higher dimensional problems, no linear methods were known up to now. We present a new procedure for finding the entire nondominated set of tricriteria optimization problems for which the number of scalarized subproblems to be solved is at most three times the number of nondominated points of the underlying problem. The approach includes an iterative update of the search space that, given a (sub-)set of nondominated points, describes the area in which additional nondominated points may be located. In particular, we show that the number of boxes, into which the search space is decomposed, depends linearly on the number of nondominated points., 32 pages, 8 figures, Journal of Global Optimization, 2014

This paper analyzes a multi-objective variant of the well-known Traveling Salesman Problem (TSP) and the Traveling Repairman Problem (TRP) in order to address the classical conflict between cost minimization (represented by the TSP) and customer waiting time minimization (represented by the TRP). By simultaneously considering different scenarios with individual travel times, uncertainty in travel data is handled. We interpret each travel time scenario as an individual objective function and introduce deterministic multi-objective counterpart models denoted as the Multi-Objective TSP (MOTSP), Multi-Objective TRP (MOTRP), and the combined Multi-Objective TSP and TRP models (MOTSRP), respectively. Problems with and without additional deadline restrictions are considered, and the complexity status of computing the Pareto fronts of various problem variants for different underlying networks is resolved. As a particularly interesting case, we consider the MOTSRP with deadlines on a line and show that the problem is intractable even in this simple setting. Nevertheless, we propose a Dynamic Programming approach that solves random instances to optimality in reasonable time. Moreover, the computational study additionally evaluates the average complexity of the Line-MOTSRP with deadlines for different numbers of scenarios. The computational study also analyzes the Pareto fronts that are generated for specifically designed extremal instances.

This report documents the program and outcomes of the Dagstuhl Seminar 15031 Understanding Complexity in Multiobjective Optimization. This seminar carried on the series of four previous Dagstuhl Seminars (04461, 06501, 09041 and 12041) that were focused on Multiobjective Optimization, and strengthening the links between the Evolutionary Multiobjective Optimization (EMO) and Multiple Criteria Decision Making (MCDM) communities. The purpose of the seminar was to bring together researchers from the two communities to take part in a wide-ranging discussion about the different sources and impacts of complexity in multiobjective optimization. The outcome was a clarified viewpoint of complexity in the various facets of multiobjective optimization, leading to several research initiatives with innovative approaches for coping with complexity. Seminar January 11–16, 2015 – http://www.dagstuhl.de/15031 1998 ACM Subject Classification G.1.6 Optimization, H.4.2 Types of Systems, I.2.6 Learning, I.2.8 Problem Solving, Control Methods, and Search, I.5.1 Models

Oncologic therapy of laryngeal cancer may necessitate a total excision of the larynx which results in loss of voice. Voice rehabilitation can be achieved using mucosal tissue vibrations at the upper part of the esophagus which serves as substitute voice generating element (PE segment). The quality of the substitute voice is closely related to vibratory characteristics of the PE segment. By means of a high-speed camera the dynamics of the PE segment can be recorded in real-time. Using image processing the deformations of the PE segment are extracted from the image series as deforming contours. Commonly, the characterization of PE dynamics bases on the spectral analysis of the time varying contour area. However, this constitutes an integral approach which masks most of the specific dynamics of PE deformations. We present an algorithm that automatically registers one segmented contour in a frame of the video sequence to the contour in the next frame to derive discrete 2-D trajectories of PE vibrations. By concatenation of the obtained transformations this approach provides a total registration of PE segment contours. We suggest a mixed-integer programming formulation for the problem that combines an advanced outlier and deformation handling with the introduction of dummy points in regions that newly open up, and that includes normal information in the objective function to avoid unwanted deformations. Numerical experiments show that the implemented alternate convex search algorithm produces robust results which is demonstrated at the example of five high-speed recordings of laryngectomee subjects.

Center location problems have many applications, for example, in the public sector, and various different algorithms have been developed for their solution. This paper suggests a novel solution strategy to the problem that is based on the propagation of circular wavefronts. The approach is discussed theoretically and implemented both as a physical experiment and as a computer simulation.

We introduce a nonpreemptive single-machine scheduling model with time-dependent multiple criteria. We formulate the problem as a knapsack problem and propose a dynamic programming (DP)-based algorithm to finding all efficient schedules. An illustrative example is enclosed.

In this chapter we consider the goals and objectives arising in wastewater management in the context of a multiobjective analysis. This allows, among others, the individual consideration of (1) the overflow volume (i.e., the total amount of released water), (2) the pollution load in the released water, and (3) the cost of the generated control. Given a specific sewage network and data of typical inflow scenarios, a multiobjective offline analysis of the problem and, in particular, of the trade-off between the different goals provides the decision maker with valuable information of the problem characteristics. This information can then be used to specify a suitable scalarized, single-objective optimization problem for the real-time optimal control that represents the decision makers preferences in a best possible way. If an efficient solver for such scalarizations is available (which is the case for the problems considered here), this leads to an efficient online procedure that is justified by an extensive offline problem analysis.

Based on the work Dearing et al. (2002), this chapter considers center problems with barriers.

Multiple objective location problems involve locating a new facility with respect to a given set of existing facilities so that a vector of performance criteria is optimized. In a major part of location planning, especially in regional and social planning, several decision-makers with different priorities are involved in the locational decision, which causes a growing need for efficient solution strategies for location models, including multiple objective functions; see, for example, Kuhpfahl et al. (1995).

Up to now the advantages of polyhedral barriers have been exploited by using the extreme points of the barrier sets as reference points for related unconstrained location problems. In the case of nonpolyhedral barriers, a different approach will be needed.

In the previous chapters we have dealt with the question of how best to define a distance between two fixed points in the n-dimensional real space ℝ n if constraints for traveling in the form of barriers are given. In this chapter we are free to choose one of these points in space, a new location, as long as we do not interfere with the given barriers.

In this chapter a strong relationship between location problems with polyhedral barriers and the corresponding unconstrained location problems is developed. See also Klamroth (2001b) for related results.

Based on theoretical results on the applicability of specially structured block norms to multicriteria programs, an algorithm to find a piecewise linear approximation of the nondominated set of convex multicriteria programs is proposed. By automatically adapting to the problem’s structure and scaling, the approximation is constructed objectively without interaction with the decision maker. Moreover, all generated extreme points of the approximation are nondominated.

In this chapter we introduce basic properties of network flows and discuss algorithms to find maximal flows and minimal cost flows.

Some of the basic concepts of graph theory will be introduced in this section. Since our main objective is to introduce the notation that will be used later on, the presentation is very brief. For further details we refer to textbooks about graph theory.

If we want to solve large LPs with many variables and many constraints it is of primary importance to have efficient algorithms and solution concepts available. In order to compare the efficiency of different algorithms we therefore introduce the concept of complexity of an algorithm.

In multiple criteria optimization an important research topic is the topological structure of the set X e of efficient solutions. Of major interest is the connectedness of X e , since it would allow the determination of X e without considering non-efficient solutions in the process. We review general results on the subject, including the connectedness result for efficient solutions in multiple criteria linear programming. This result can be used to derive a definition of connectedness for discrete optimization problems. We present a counterexample to the connectivity conjecture, namely that the sets of efficient solutions of the shortest path problem and the minimal spanning tree problem are connected. We will also present a general method to construct non-connected efficiency graphs for these problems.