90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
Document Type
- ZIB-Report (175)
- Master's Thesis (17)
- Bachelor's Thesis (9)
- Doctoral Thesis (6)
- Article (2)
- In Proceedings (1)
Keywords
Institute
- Mathematical Optimization (156)
- Mathematical Optimization Methods (34)
- Network Optimization (29)
- Applied Algorithmic Intelligence Methods (14)
- AI in Society, Science, and Technology (9)
- Mathematics of Telecommunication (7)
- Mathematics of Transportation and Logistics (6)
- Mathematical Algorithmic Intelligence (4)
- Numerical Mathematics (4)
- ZIB Allgemein (4)
Gas networks are an important application area for optimization. When considering long-range transmission, compressor stations play a crucial role in these applications. The purpose of this report is to collect and systematize the models used for compressor stations in the literature. The emphasis is on recent work on simple yet accurate polyhedral models that may replace more simplified traditional models without increasing model complexity. The report also describes an extension of the compressor station data available in GasLib (http://gaslib.zib.de/) with the parameters of these models.
The topic of this thesis is the examination of an optimization model
which stems from the clustering process of non-reversible markov processes.
We introduce the cycle clustering problem und formulate it as a mixed
integer program (MIP).
We prove that this problem is N P-hard and discuss polytopal aspects
such as facets and dimension. The focus of this thesis is the development of
solving methods for this clustering problem. We develop problem specific
primal heuristics, as well as separation methods and an approximation
algorithm. These techniques are implemented in practice as an application
for the MIP solver SCIP.
Our computational experiments show that these solving methods result
in an average speedup of ×4 compared to generic solvers and that our
application is able to solve more instances to optimality within the given
time limit of one hour.
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.
This article describes new features and enhanced algorithms made available in version 5.0 of the SCIP Optimization Suite. In its central component, the constraint integer programming solver SCIP, remarkable performance improvements have been achieved for solving mixed-integer linear and nonlinear programs. On MIPs, SCIP 5.0 is about 41 % faster than SCIP 4.0 and over twice as fast on instances that take at least 100 seconds to solve. For MINLP, SCIP 5.0 is about 17 % faster overall and 23 % faster on instances that take at least 100 seconds to solve. This boost is due to algorithmic advances in several parts of the solver such as cutting plane generation and management, a new adaptive coordination of large neighborhood search heuristics, symmetry handling, and strengthened McCormick relaxations for bilinear terms in MINLPs. Besides discussing the theoretical background and the implementational aspects of these developments, the report describes recent additions for the other software packages connected to SCIP, in particular for the LP solver SoPlex, the Steiner tree solver SCIP-Jack, the MISDP solver SCIP-SDP, and the parallelization framework UG.
Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.
The analysis of infeasibility plays an important role in solving satisfiability problems (SAT) and mixed integer programs (MIPs). In mixed integer programming, this procedure is called conflict analysis. So far, modern MIP solvers use conflict analysis only for propagation and improving the dual bound, i.e., fathoming nodes that cannot contain feasible solutions. In this short paper, we present a new approach which uses conflict information to improve the primal bound during a MIP solve. To derive new improving primal solutions we use a conflict driven diving heuristic called conflict diving that uses the information obtained by conflict analysis. Conflict diving pursues a twofold strategy. By using conflict information the new diving approach is guided into parts of the search space that are usually not explored by other diving heuristics. At the same time, conflict diving has a fail-fast-strategy to reduce the time spent if it cannot find a new primal solution. As a byproduct, additional valid conflict constraints can be derived, from which a MIP solver can gain benefit to improve the dual bound as well. To show the added-value of conflict diving within a MIP solver, conflict diving has been implemented within the non-commercial MIP solver SCIP. Experiments are carried out on general MIP instances from standard public test sets, like MIPLIB2010 or Cor@l.
Compressor machines are crucial elements in a gas transmission network, required to compensate for the pressure loss caused by friction in the pipes. Modelling all physical and technical details of a compressor machine involves a large amount of nonlinearity, which makes it hard to use such models in the optimization of large-scale gas networks. In this paper, we are going to describe a modelling approach for the operating range of a compressor machine, starting from a physical reference model and resulting in a polyhedral representation in the 3D space of mass flow throughput as well as in- and outlet pressure.
Mixed integer linear programming (MIP) is a general form to model combinatorial optimization problems and has many industrial applications. The performance of MIP solvers has improved tremendously in the last two decades and these solvers have been used to solve many real-word problems. However, against the backdrop of modern computer technology, parallelization is of pivotal importance. In this way, ParaSCIP is the most successful parallel MIP solver in terms of solving previously unsolvable instances from the well-known benchmark instance set MIPLIB by using supercomputers. It solved two instances from MIPLIB2003 and 12 from MIPLIB2010 for the first time to optimality by using up to 80,000 cores on supercomputers. ParaSCIP has been developed by using the Ubiquity Generator (UG) framework, which is a general software package to parallelize any state-of-the-art branch-and-bound based solver. This paper discusses 7 years of progress in parallelizing branch-and-bound solvers with UG.
PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve MIPs with a dual-block angular structure, which is characteristic of deterministic-equivalent Stochastic Mixed-Integer Programs (SMIPs). In this paper, we present two different parallelizations of Branch & Bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator (UG), a universal framework for parallelizing B&B tree search that has been successfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.
Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems
(2017)
This article introduces new preprocessing techniques for the Steiner tree problem in graphs and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. The correctness of the new methods is shown, but also their NP-hardness is demonstrated. Despite this pessimistic worst-case complexity, several relaxations are discussed that are expected to allow for a strong practical efficiency of these techniques in strengthening both exact and heuristic solving approaches.
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral.
We investigate how the numerical properties of the LP relaxations evolve
throughout the solution procedure in a solver employing the branch-and-cut
algorithm. The long-term goal of this work is to determine whether the effect
on the numerical conditioning of the LP relaxations resulting from the
branching and cutting operations can be effectively predicted
and whether such predictions can be used to make better algorithmic
choices. In a first step towards this goal, we discuss here the numerical
behavior of an existing solver in order to determine whether our
intuitive understanding of this behavior is correct.
Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.
The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the
timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.
Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables.
We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.
Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs.
This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation.
Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound.
Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.
In this paper, we compare several approaches for the problem of gas network expansions using loops, that is, to build new pipelines in parallel to existing ones. We present different model formulations for the problem of continuous loop expansions as well as discrete loop expansions. We then analyze problem properties, such as the structure and convexity of the underlying feasible regions. The paper concludes with a computational study comparing the continuous and the discrete formulations.
In the context of gas transmission in decoupled entry-exit systems, many approaches to determine the network capacity are based on the evaluation of realistic and severe transport situations. In this paper, we review the Reference Point Method, which is an algorithm used in practice to generate a set of scenarios using the so-called transport moment as a measure for severity. We introduce a new algorithm for finding severe transport situations that considers an actual routing of the flow through the network and is designed to handle issues arising from cyclic structures in a more dynamical manner. Further, in order to better approximate the physics of gas, an alternative, potential based flow formulation is proposed. The report concludes with a case study based on data from the benchmark library GasLib.
A railway operator creates (rolling stock) rotations in order to have a precise master plan for the
operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply
traverses a set of operational days while covering trips of the timetable. As it is well known,
the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging
and still a topical research subject. Nevertheless, we study a completely different but strongly
related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce
a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In
our industrial application at DB Fernverkehr AG, the handout is exactly as important as the
rotation itself. Moreover, it turns out that also other European railway operators use exactly the
same methodology (but not terminology). Since a rotation can have many handouts of different
quality, we show how to compute optimal ones through an integer program (IP) by standard
software. In addition, a construction as well as an improvement heuristic are presented. Our
computational results show that the heuristics are a very reliable standalone approach to quickly
find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a
computational comparison to the IP approach.
Portfolio parallelization is an approach that runs several solver instances in parallel and terminates when one of them succeeds in solving the problem. Despite it's simplicity portfolio parallelization has been shown to perform well for modern mixed-integer programming (MIP) and boolean satisfiability problem (SAT) solvers. Domain propagation has also been shown to be a simple technique in modern MIP and SAT solvers that effectively finds additional domain reductions after a variables domain has been reduced. This paper investigates the impact of distributed domain propagation in modern MIP solvers that employ portfolio parallelization. Computational experiments were conducted for two implementations of this parallelization approach. While both share global variable bounds and solutions they communicate differently. In one implementation the communication is performed only at designated points in the solving process and in the other it is performed completely asynchronously. Computational experiments show a positive performance impact of communicating global variable bounds and provide valuable insights in communication strategies for parallel solvers.
SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.
We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions.
The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs.
In this paper, we provide a comprehensive analysis of the problem. In particular,
we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.
The analysis of infeasible subproblems plays an import role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. There are two fundamentally different concepts to generate valid global constraints from infeasible subproblems. The first is to analyze the sequence of implications obtained by domain propagation that led to infeasibility. The result of the analysis is one or more sets of contradicting variable bounds from which so-called conflict constraints can be generated. This concept has its origin in solving satisfiability problems and is similarly used in constraint programming. The second concept is to analyze infeasible linear programming (LP) relaxations. The dual LP solution provides a set of multipliers that can be used to generate a single new globally valid linear constraint. The main contribution of this short paper is an empirical evaluation of two ways to combine both approaches. Experiments are carried out on general MIP instances from standard public test sets such as Miplib2010; the presented algorithms have been implemented within the non-commercial MIP solver SCIP. Moreover, we present a pool-based approach to manage conflicts which addresses the way a MIP solver traverses the search tree better than aging strategies known from SAT solving.
Software for mixed-integer linear programming can return incorrect results for a number of reasons, one being the use of inexact floating-point arithmetic. Even solvers that employ exact arithmetic may suffer from programming or algorithmic errors, motivating the desire for a way to produce independently verifiable certificates of claimed results. Due to the complex nature of state-of-the-art MILP solution algorithms, the ideal form of such a certificate is not entirely clear. This paper proposes such a certificate format, illustrating its capabilities and structure through examples. The certificate format is designed with simplicity in mind and is composed of a list of statements that can be sequentially verified using a limited number of simple yet powerful inference rules. We present a supplementary verification tool for compressing and checking these certificates independently of how they were created. We report computational results on a selection of mixed-integer linear programming instances from the literature. To this end, we have extended the exact rational version of the MIP solver SCIP to produce such certificates.
We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.
The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation.
We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012.
The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this paper we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize-collecting Steiner tree problem, the rooted prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem.
By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90 percent of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state-of-the-art Steiner problem solver SCIP-Jack.
In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.
In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst.
The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different
Steiner tree problem variants can be observed, solution approaches employed so far have been
prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that
can be used to solve both the classical Steiner tree problem and many of its variants without
modification. This versatility is achieved by transforming various problem variants into a
general form and solving them by using a state-of-the-art MIP-framework. The result is
a high-performance solver that can be employed in massively parallel environments and is
capable of solving previously unsolved instances.
Bus rapid transit systems in developing and newly
industrialized countries often consist of a trunk with a path
topology. On this trunk, several overlapping lines are operated
which provide direct connections. The demand varies heavily over the
day, with morning and afternoon peaks typically in reverse
directions. We propose an integer programming
model for this problem, derive a structural property of line plans
in the static (or single period) ``unimodal demand'' case, and
consider approaches to the solution of the multi-period version that
rely on clustering the demand into peak and off-peak service
periods. An application to the Metrobüs system of Istanbul is
discussed.
Optimization-based bound tightening (OBBT) is one of the most effective procedures to reduce variable domains of nonconvex mixed-integer nonlinear programs (MINLPs). At the same time it is one of the most expensive bound tightening procedures, since it solves auxiliary linear programs (LPs)—up to twice the number of variables many. The main goal of this paper is to discuss algorithmic techniques for an efficient implementation of OBBT.
Most state-of-the-art MINLP solvers apply some restricted version of OBBT and it seems to be common belief that OBBT is beneficial if only one is able to keep its computational cost under control. To this end, we introduce three techniques to increase the efficiency of OBBT: filtering strategies to reduce the number of solved LPs, ordering heuristics to exploit simplex warm starts, and the generation of Lagrangian variable bounds (LVBs). The propagation of LVBs during tree search is a fast approximation to OBBT without the need to solve auxiliary LPs.
We conduct extensive computational experiments on MINLPLib2. Our results indicate that OBBT is most beneficial on hard instances, for which we observe a speedup of 17% to 19% on average. Most importantly, more instances can be solved when using OBBT.
Generic Branch-Cut-and-Price
(2010)
Modern MIP solving software
incorporates dozens of auxiliary algorithmic components for supporting
the branch-and-bound search in finding and improving solutions and in strengthening the relaxation.
Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process.
We propose an adaptive solver behavior that dynamically reacts
on transitions between the three typical phases of a MIP solving process:
The first phase objective is to find a feasible solution. During the second phase,
a sequence of incumbent solutions gets constructed
until the incumbent is eventually optimal. Proving
optimality is the central objective of the remaining third phase.
Based on the MIP-solver SCIP, we demonstrate
the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide
heuristic alternatives to make use of the concept in practice.
The operation of a railway network as large as Deutsche Bahn's Intercity Express (ICE) hinges on a number of factors, such as the availability of personnel and the assignment of physical vehicles to a timetable schedule, a problem known as the rolling stock rotation problem (RSRP). In this paper, we consider the problem of creating an alternative timetable in the case that there is a long-term disruption, such as a strike, and the effects that this alternative timetable has on the resulting vehicle rotation plan. We define a priority measure via the Analytic Hierarchy Process (AHP) to determine the importance of each trip in the timetable and therefore which trips to cancel or retain. We then compare our results with those of a limited timetable manually designed by Deutsche Bahn (DB). We find that while our timetable results in a more expensive rotation plan, its flexibility lends itself to a number of simple improvements. Furthermore, our priority measure has the potential to be integrated into the rolling stock rotation optimization process, in particular, the Rotation Optimizer for Railways (ROTOR) software, via the cost function. Ultimately, our method provides the foundation for an automated way of creating a new timetable quickly, and potentially in conjunction with a new rotation plan, in the case of a limited scenario.
This paper describes how we solved 12 previously unsolved mixed-integer program-
ming (MIP) instances from the MIPLIB benchmark sets. To achieve these results we
used an enhanced version of ParaSCIP, setting a new record for the largest scale MIP
computation: up to 80,000 cores in parallel on the Titan supercomputer. In this paper
we describe the basic parallelization mechanism of ParaSCIP, improvements of the
dynamic load balancing and novel techniques to exploit the power of parallelization
for MIP solving. We give a detailed overview of computing times and statistics for
solving open MIPLIB instances.
We present two algorithms to solve a 3-objective optimization problem arising in telecommunications access network planning, the k-Architecture Connected Facility Location Problem. The methods can also be used to solve any 3-objective integer linear programming model and can be extended to the multiobjective case. We give some exemplary computations using small and medium-sized instances for our problem.
Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics
can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and
airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.
Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.
Rising traffic in telecommunication networks lead to rising energy costs for the network operators. Meanwhile, increased flexibility of the networking hardware may help to realize load-adaptive operation of the networks to cut operation costs. To meet network operators’ concerns over stability, we propose to switch network configurations only a limited number of times per day. We present a method for the integrated computation of optimal switching times and network configurations that alternatingly solves mixed-integer programs and constrained shortest cycle problems in a certain graph. Similarly to the Branch & Bound Algorithm, it uses lower and upper bounds on the optimum value and allows for pivoting strategies to guide the computation and avoid the solution of irrelevant subproblems. The algorithm can act as a framework to be adapted and applied to suitable problems of different origin.
We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.
The selection of a good branching variable is crucial for small search trees in Mixed Integer Programming. Most modern solvers employ a strategy guided by history information, mainly the variable pseudo-costs, which are used to estimate the objective gain. At the beginning
of the search, such information is usually collected via an expensive look-ahead strategy called strong-branching until variables are considered reliable.
The reliability notion is thereby mostly based on fixed-number thresholds, which may lead to ineffective branching decisions on problems with highly varying objective gains.
We suggest two new notions of reliability motivated by mathematical statistics that take into account the sample variance of the past observations on each variable individually. The first method prioritizes additional strong-branching look-aheads on variables whose pseudo-costs
show a large variance by measuring the relative error of a pseudo-cost confidence interval. The second method performs a two-sample Student-t test for filtering branching candidates with a high probability to be better than the best history candidate.
Both methods were implemented in the MIP-solver SCIP and computational results on standard MIP test sets are presented.
Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.
We propose a composite step method, designed for equality constrained optimization with partial differential equations. Focus is laid on the construction of a globalization scheme, which is based on cubic regularization of the objective and an affine covariant damped Newton method for feasibility. We show finite termination of the inner loop and fast local convergence of the algorithm. We discuss preconditioning strategies for the iterative solution of the arising linear systems with projected conjugate gradient. Numerical results are shown for optimal control problems subject to a nonlinear heat equation and subject to nonlinear elastic equations arising from an implant design problem in craniofacial surgery.
We apply customized versions of the ε-constraint Method and the Two-Phase Method to a problem originating in access network planning. We introduce various notions of quality measures for approximated/partial sets of nondominated points, utilizing the concept of hypervolume for biobjective problems. We report on computations to assess the performance of the two methods in terms of these measures.
Planning and operating railway transportation systems is an extremely
hard task due to the combinatorial complexity of the underlying discrete
optimization problems, the technical intricacies, and the immense size of
the problem instances. Because of that, however, mathematical models
and optimization techniques can result in large gains for both railway cus-
tomers and operators, e.g., in terms of cost reductions or service quality
improvements. In the last years a large and growing group of researchers
in the OR community have devoted their attention to this domain devel-
oping mathematical models and optimization approaches to tackle many
of the relevant problems in the railway planning process. However, there
is still a gap to bridge between theory and practice, with
a few notable exceptions. In this paper we address three success stories,
namely, long-term freight train routing (part I), mid-term rolling stock
rotation planning (part II), and real-time train dispatching (part III). In
each case, we describe real-life, successful implementations. We will dis-
cuss the individual problem setting, survey the optimization literature,
and focus on particular aspects addressed by the mathematical models.
We demonstrate on concrete applications how mathematical optimization
can support railway planning and operations. This gives proof that math-
ematical optimization can support the planning of rolling stock resources.
Thus, mathematical models and optimization can lead to a greater effi-
ciency of railway operations and will serve as a powerful and innovative
tool to meet recent challenges of the railway industry.
We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials.
Energy storages can be of great value when added to power grids. They introduce the possibility to store and release energy whenever this is favorable. This is particularly relevant, for example, if power supply is volatile (as is the case with renewable energy) and the network is small (so that there are few other nodes that might balance fluctuations in consumption or production). We present models and methods from mathematical optimization for computing an optimized storage schedule for this purpose. We look at alternative optimization objectives, such as smallest possible peak load, low energy costs, or the close approximation of a prescribed load curve. The optimization needs to respect general operational and economic constraints as well as limitations in the use of storage, which are imposed by the chosen storage technology. We therefore introduce alternative approaches for modeling the non-linear properties of energy storages and study their impact on the efficiency of the optimization process. Finally, we present a computational study with batteries as storage devices. We use this to highlight the trade-off between solution quality and computational tractability. A version of the model for the purpose of leveling peaks and instabilities has been implemented into a control system for an office-building smart grid scenario.
One quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology extension problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. In this article we offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speed-up for the necessary computations.
The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an
opportunity for high-achieving graduate-level students to work in teams on a
real-world research project proposed by a sponsor from industry or the public
sector. Each G-RIPS team consists of four international students (two from
the US and two from European universities), an academic mentor, and an industrial sponsor.
This is the report of the Rail-Lab project on the definition and integration of
robustness aspects into optimizing rolling stock schedules. In general, there is
a trade-off for complex systems between robustness and efficiency. The ambitious
goal was to explore this trade-off by implementing numerical simulations and
developing analytic models.
In rolling stock planning a very large set of industrial railway requirements,
such as vehicle composition, maintenance constraints, infrastructure capacity,
and regularity aspects, have to be considered in an integrated model. General
hypergraphs provide the modeling power to tackle those requirements.
Furthermore, integer programming approaches are able to produce high quality
solutions for the deterministic problem.
When stochastic time delays are considered, the mathematical programming problem
is much more complex and presents additional challenges. Thus, we started with a
basic variant of the deterministic case, i.e., we are only considering
hypergraphs representing vehicle composition and regularity.
We transfered solution approaches for robust optimization
from the airline industry to the setting of railways and attained a
reasonable measure of robustness. Finally, we present and discuss different
methods to optimize this robustness measure.
The Cycle Embedding Problem
(2014)
Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design
efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor
details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to the find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems.
We provide an overview of new theoretical results that we obtained while further investigating multiband robust optimization, a new model for robust optimization that we recently proposed to tackle uncertainty in mixed-integer linear programming. This new model extends and refines the classical Gamma-robustness model of Bertsimas and Sim and is particularly useful in the common case of arbitrary asymmetric distributions of the uncertainty. Here, we focus on uncertain 0-1 programs and we analyze their robust counterparts when the uncertainty is represented through a multiband set. Our investigations were inspired by the needs of our industrial partners in the research project ROBUKOM.
We investigate the Robust Multiperiod Network Design Problem, a generalization of the classical Capacitated Network Design Problem that additionally considers multiple design periods and provides solutions protected against traffic uncertainty.
Given the intrinsic difficulty of the problem, which proves challenging even for state-of-the art commercial solvers, we propose a hybrid primal heuristic based on the combination of ant colony optimization and an exact large neighborhood search. Computational experiments on a set of realistic instances from the SNDlib show that our heuristic can find solutions of extremely good quality with low optimality gap.
A central assumption in classical optimization is that all the input data of a
problem are exact. However, in many real-world problems, the input data are subject
to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal
solutions that are actually suboptimal or even infeasible. Robust optimization
offers a remedy for optimization under uncertainty by considering only the subset of
solutions protected against the data deviations. In this paper, we provide an overview
of the main theoretical results of multiband robustness, a new robust optimization
model that extends and refines the classical theory introduced by Bertsimas and Sim.
After introducing some new results for the special case of pure binary programs, we
focus on the harvest scheduling problem and show how multiband robustness can
be adopted to tackle the uncertainty affecting the volume of produced timber and
grant a reduction in the price of robustness.
We present a novel heuristic algorithm to identify feasible solutions of a mixed-integer nonlinear programming problem arising in natural gas transportation: the selection of new pipelines to enhance the network's capacity to a desired level in a cost-efficient way. We solve this problem in a linear programming based branch-and-cut approach, where we deal with the nonlinearities by linear outer approximation and spatial branching. At certain nodes of the branching tree, we compute a KKT point for a nonlinear relaxation. Based on the information from the KKT point we alter some of the integer variables in a locally promising way. We describe this heuristic for general MINLPs and then show how to tailor the heuristic to exploit our problem-specific structure. On a test set of real-world instances, we are able to increase the chance of identifying feasible solutions by some order of magnitude compared to standard MINLP heuristics that are already built in the general-purpose MINLP solver SCIP.
We consider a system dynamics model that describes the effect of human activity on natural resources. The central stocks are the accumulated profit, the industry structures, and the water resources. The model can be controlled through two time-dependent parameters. The goal in this paper is to find a parameter setting that leads to a maximization of a performance index, which reflects both environmental and economic aspects. Thus, the goal is to identify the most sustainable stock of industry structures within the model's constraints and assumptions. In order to find a proven global optimal parameter set, we formulate the System Dynamics Optimization model as a mixed-integer nonlinear problem that is accessible for numerical solvers. Due to the dynamic structure of the model, certain steps of the solution process must be handled with greater care, compared to standard non-dynamic problems. We describe our approach of solving the industry structure model and present computational results. In addition, we discuss the limitations of the approach and next steps.
A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value.
We provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks.
The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/).
We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension.
Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR.
Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated.
The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, i.e., vehicle composition, maintenance constraints, and regularity aspects.
In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites.
We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG.
The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties.
This thesis represents a game-theoretic investigation of the allocation of inspectors in a transportation network, comparing Nash and Stackelberg equilibrium strategies to a strategy in which inspections are conducted proportionally to the traffic volume. It contains specifications for the integration of space and time dependencies and extensive experimental tests for the application on the transportation network of German motorways using real data. Main results are that - although the formulated spot-checking game is not zero-sum - we are able to compute a Nash equilibrium using linear programming and secondly, that experimental results yield that a Nash equilibrium strategy represents a good trade-off for the Stackelberg equilibrium strategy between efficiency of controls and computation time.
We consider the following freight train routing problem (FTRP). Given is a
transportation network with fixed routes for passenger trains and a
set of freight trains (requests), each defined by an origin and
destination station pair. The objective is to calculate a feasible
route for each freight train such that a sum of all expected delays and
all running times is minimal. Previous research concentrated on
microscopic train routings for junctions or inside major stations. Only
recently approaches were developed to tackle larger corridors or even
networks. We investigate the routing problem from a strategic
perspective, calculating the routes in a macroscopic transportation
network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of
complex real-world structures are into fewer network elements. Moreover, the
departure and arrival times of freight trains are approximated.
The problem has a strategic
character since it asks only for a coarse routing through the network
without the precise timings. We give a mixed-integer nonlinear programming~(MINLP)
formulation for FTRP, which is a multi-commodity flow model on a time-expanded
graph with additional routing constraints. The model's nonlinearities are due to
an algebraic approximation of the delays of the trains on the arcs of
the network
by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP)
by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances.
We consider a nonlinear nonconvex network flow problem that arises, for example, in natural gas or water transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. The problem is how to numerically compute this flow and pressures. We review an existing approach of Maugis (1977) and extend it to the case of networks with active elements (for example, compressors). We further examine different ways of relaxations for the nonlinear network flow model. We compare different approaches based on nonlinear optimization numerically on a set of test instances.
In this paper we study the cost-optimal deployment of optical access networks considering variants of the problem such as fiber to the home (FTTH), fiber to the building (FTTB), fiber to the curb (FTTC), or fiber to the neighborhood (FTTN). We identify the combinatorial structures of the most important sub-problems arising in this area and model these, e.g., as capacitated facility location, concentrator location, or Steiner tree problems. We discuss modeling alternatives as well. We finally construct a “unified” integer programming model that combines all sub-models and provides a global view of all these FTTx problems. We also summarize computational studies of various special cases.
We introduce a new variant of the connected facility location problem that allows for modeling mixed deployment strategies (FTTC/FTTB/FTTH) in the design of local access telecommunication networks. Several mixed integer programming models and valid inequalities are presented. Computational studies on realistic instances from three towns in Germany are provided.
The System Dynamics (SD) methodology is a framework for modeling and simulating the dynamic behavior of socioeconomic systems. Characteristic for the description of such systems is the occurrence of feedback loops together with stocks and flows. The mathematical equations that describe the system are usually ordinary differential equations and nonlinear algebraic constraints. Therefore seemingly simple systems can show a nonintuitive, unpredictable behavior over time. Controlling a dynamical system means to specify potential interventions from outside that should keep the system on the desired track, and to define an evaluation schema to compare different controls among each other, so that a "best" control can be defined in a meaningful way. The central question is how to compute such globally optimal control for a given SD model, that allows the transition of the system into a desired state with minimum effort. We propose a mixed-integer nonlinear programming (MINLP) reformulation of the System Dynamics Optimization (SDO) problem. MINLP problems can be solved by linear programming based branch-and-bound approach. We demonstrate that standard MINLP solvers are not able to solve SDO problem. To overcome this obstacle, we introduce a special-tailored bound propagation method. We apply our new method to a predator-prey model with additional hunting activity as control, and to a mini-world model with the consumption level as control. Numerical results for these test cases are presented.
The Scenario Technique is a strategic planning method that aims to describe and analyze potential developments of a considered system in the future. Its application consists of several steps, from an initial problem analysis over an influence analysis to projections of key factors and a definition of the scenarios to a final interpretation of the results. The technique itself combines qualitative and quantitative methods and is an enhancement of the standard Scenario Technique. We use the numerical values gathered during the influence analysis, and embed them in a System Dynamics framework. This yields a mathematically rigorous way to achieve predictions of the system‘s future behavior from an initial impulse and the feedback structure of the factors. The outcome of our new method is a further way of projecting the present into the future, which enables the user of the Scenario Technique to obtain a validation of the results achieved by the standard method.
The System Dynamics (SD) methodology is a framework for modeling and simulating
the dynamic behavior of socioeconomic systems. Characteristic for the
description of such systems is the occurrence of feedback loops together with
stocks and flows. The mathematical equations that describe the system are
usually nonlinear. Therefore seemingly simple systems can show a nonintuitive,
nonpredictable behavior over time. Controlling a dynamical system means to
define a desired final state in which the system should be, and to specify
potential interventions from outside that should keep the system on the right
track. The central question is how to compute such globally optimal control for
a given SD model. We propose a branch-and-bound approach that is based on a
bound propagation method, primal heuristics, and spatial branching. We apply our
new SD-control method to a small System Dynamics model, that describes the
evolution of a social-economic system over time. We examine the problem of
steering this system on a sustainable consumption path.
Sports rankings are obtained by applying a system of rules to evaluate the
performance of the participants in a competition.
We consider rankings that result from assigning an ordinal rank to each
competitor according to their performance.
We develop an integer programming model for rankings that allows us
to calculate the number of points needed to guarantee
a team the ith position, as well as the minimum number of points
that could yield the ith place.
The model is very general and can thus be applied to many types of sports.
We discuss examples coming from football (soccer), ice hockey, and
Formula~1. We answer various questions and debunk a few myths along the way.
Are 40 points enough to avoid relegation in the Bundesliga?
Do 95 points guarantee the participation of a team in the NHL playoffs?
Moreover, in the season restructuration currently under consideration in the NHL,
will it be easier or harder to access the playoffs?
Is it possible to win the Formula~1 World Championship without winning at least one race
or without even climbing once on the podium?
Finally, we observe that the optimal solutions of the aforementioned model
are associated to extreme situations which are unlikely to happen. Thus,
to get closer to realistic scenarios, we enhance the model by adding some
constraints inferred from the results of the previous years.
Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, HGF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and HGF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall.
We consider reoptimization (i.e. the solution of a problem based on information available from solving a similar problem) for branch-and-bound algorithms and propose a generic framework to construct a reoptimizing branch-and-bound algorithm.
We apply this to an elevator scheduling algorithm solving similar subproblems to generate columns using branch-and-bound. Our results indicate that reoptimization techniques can substantially reduce the running times of the overall algorithm.
We consider a nonlinear nonconvex network design problem that arises in the extension of natural gas transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. Assume that there does not exist a feasible flow that fulfills all physical constraints and meets the desired entry and exit amounts. Then a natural question is where to extend the network by adding pipes in the most economic way such that this flow becomes feasible. Answering this question is computationally demanding because of the difficult problem structure. We use mixed-integer nonlinear programming techniques that rely on an outer approximation of the overall problem, and a branching on decision variables. We formulate a new class of valid inequalities (or cutting planes) which reduce the overall solution time when added to the formulation. We demonstrate the computational merits of our approach on test instances.
Strong branching is an important component of most variable selection rules in branch-and-bound based mixed-integer linear programming solvers.
It predicts the dual bounds of potential child nodes by solving auxiliary LPs and thereby helps to keep the branch-and-bound tree small.
In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching.
Computational experiments on standard MIP instances indicate that this is beneficial in three aspects: It helps to reduce the average number of LP iterations per strong branching call, the number of branch-and-bound nodes, and the overall solving time.
We present a new semidefinite representation for the trace of
a real function f applied to symmetric matrices, when a
semidefinite representation of the convex function f is known. Our construction
is intuitive, and yields a representation that is more compact than the previously known one.
We also show with the help of matrix geometric means and the Riemannian metric of the set of positive definite matrices
that for a rational number p in the interval (0,1],
the matrix X raised to the exponent p is the largest element
of a set represented by linear matrix inequalities.
We give numerical results for a problem inspired from the theory
of experimental designs, which show that the new semidefinite programming formulation
yields a speed-up factor in the order of 10.
PICOS is a user friendly interface
to several conic and integer programming solvers,
very much like YALMIP
under MATLAB.
The main motivation for PICOS is to have the possibility to
enter an optimization problem as a high level model,
and to be able to solve it with several different solvers.
Multidimensional and matrix variables are handled in a natural fashion,
which makes it painless to formulate a SDP or a SOCP.
This is very useful for educational purposes,
and to quickly implement some models and
test their validity on simple examples.
Furthermore, with PICOS you can take advantage of the
python programming language to read and write data,
construct a list of constraints by using python list comprehensions,
take slices of multidimensional variables, etc.
The industrial treatment of waste paper in order to regain valuable
fibers from which recovered paper can be produced, involves several
steps of preparation. One important step is the separation of stickies
that are normally attached to the paper. If not properly separated,
remaining stickies reduce the quality of the recovered paper or even
disrupt the production process. For the mechanical separation process
of fibers from stickies a separator screen is used. This machine has
one input feed and two output streams, called the accept and the
reject. In the accept the fibers are concentrated, whereas the reject
has a higher concentration of stickies. The machine can be controlled
by setting its reject rate. But even when the reject rate is set
properly, after just a single screening step, the accept still has too
many stickies, or the reject too many fibers. To get a proper
separation, several separators have to be assembled into a
network. From a mathematical point of view this problem can be seen as
a multi-commodity network flow design problem with a nonlinear,
controllable distribution function at each node. We present a
nonlinear mixed-integer programming model for the simultaneous
selection of a subset of separators, the network's topology, and the
optimal setting of each separator.
Numerical results are obtained via
different types of linearization of the nonlinearities and the use of
mixed-integer linear solvers, and compared with state-of-the-art
global optimization software.
The task of an elevator control is to schedule the elevators of a group such
that small waiting and travel times for the passengers are obtained. We present an exact
reoptimization algorithm for this problem. A reoptimization algorithm computes a
new schedule for the elevator group each time a new passenger arrives. Our algorithm
uses column generation techniques and is, to the best of our knowledge, the first exact
reoptimization algorithms for a group of passenger elevators. To solve the column
generation problem, we propose a Branch & Bound method.
This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for
the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic
comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic
picture than competitive analysis and explains the behavior observed in simulations.
This paper provides a highly integrated solution approach for rolling stock
planning problems in the context of intercity passenger traffic. The main
contributions are a generic hypergraph based mixed integer programming
model and an integrated algorithm for the considered rolling stock rotation
planning problem. The new developed approach is able to handle a very large
set of industrial railway requirements, such as vehicle composition,
maintenance constraints, infrastructure capacity, and regularity aspects.
By the integration of this large bundle of technical railway aspects, we show
that our approach has the power to produce implementable rolling stock
rotations for our industrial cooperation partner DB Fernverkehr.
This is the first time that the rolling stock rotations at DB Fernverkehr
could be optimized by an automated system utilizing advanced mathematical
programming techniques.
Railway Track Allocation
(2012)
This article gives an overview of the results of the author's PhD thesis. The thesis deals with the
mathematical optimization for the efficient use of
railway infrastructure. We address the optimal allocation of the available
railway track capacity - the track allocation problem. This track allocation
problem is a major challenge for a railway company, independent of whether
a free market, a private monopoly, or a public monopoly is given. Planning
and operating railway transportation systems is extremely hard due to the
combinatorial complexity of the underlying discrete optimization problems,
the technical intricacies, and the immense sizes of the problem instances.
Mathematical models and optimization techniques can result in huge gains
for both railway customers and operators, e.g., in terms of cost reductions or
service quality improvements. We tackle this challenge by developing novel
mathematical models and associated innovative algorithmic solution methods
for large scale instances. We made considerable progress on solving track
allocation problems by two main features - a novel modeling approach for the
macroscopic track allocation problem and algorithmic improvements based on the
utilization of the bundle method. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland.
In this paper we give an analytical description on the structure of
solutions to the gas nomination validation problem in gas
transportation networks. These networks are assumed to contain no
active devices, only certain hypothetical pipelines, where the flow
of gas is modeled by a generalized version of the quadratic
Weymouth's equation. The purpose of considering generalized flow
formulas is to be able to adapt our results to various gas network
optimization problems involving gas flow formulas beyond Weymouth's
equation. Such formulas can appear in leaves of branch and bound
trees, or they can stem from discretization and linearization
carried out at active devices. We call a balanced supply-demand
vector a nomination, and the passive nomination validation problem
is to decide whether there exist pressures at the nodes generating a
given nomination. We prove that in our setup the pressure square
vectors generating a given nomination form a one-dimensional
connected and continuous curve in the pressure square space, and
this curve is a line for the classical Weymouth's equation. We also
present a visual approach for the easy comprehension of how this
solution curve arises; we give a short investigation of the set of
feasible nominations; and finally we give a proof that the
nomination validation problem in gas networks with active devices is
NP-complete.
In the last 20 years competitive analysis has become the main tool for
analyzing the quality of online algorithms. Despite of this,
competitive analysis has also been criticized: It sometimes cannot
discriminate between algorithms that exhibit significantly different
empirical behavior, or it even favors an algorithm that is worse from
an empirical point of view. Therefore, there have been several
approaches to circumvent these drawbacks. In this survey, we discuss
probabilistic alternatives for competitive analysis.
Die mittel- und längerfristige Planung für den Gastransport hat sich durch
Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert.
Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel
diskutiert die hieraus resultierenden mathematischen Planungsprobleme,
welche als Validierung von Nominierungen und Buchungen, Bestimmung der
technischen Kapazität und Topologieplanung bezeichnet werden. Diese
mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze
skizziert.
We propose a game theoretic model for the spatial distribution of inspectors on a
transportation network.
The problem is to spread out the controls so as to enforce the payment of a transit
toll. We formulate a linear program to find
the control distribution which maximizes the expected toll revenue,
and a mixed integer program for the problem of minimizing
the number of evaders. Furthermore, we show that the problem of finding an optimal
mixed strategy for a coalition of $N$ inspectors can be solved
efficiently by a column generation procedure. Finally, we give experimental results
from an application to the truck toll on German motorways.
We study a family of combinatorial optimization problems
defined by a parameter $p\in[0,1]$, which involves spectral
functions applied to positive semidefinite matrices, and has
some application in the theory of optimal experimental design.
This family of problems tends to a generalization of the classical
maximum coverage problem as $p$ goes to $0$, and to a trivial instance
of the knapsack problem as $p$ goes to $1$.
In this article, we establish a matrix inequality which shows that the objective function is submodular for all $p\in[0,1]$, from which it follows
that the greedy approach, which has often been used for this problem, always gives a design within $1-1/e$ of the optimum.
We next study the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors.
We prove an inequality which generalizes a classical result from the theory
of optimal designs, and allows us to give a rounding procedure with an approximation
factor which tends to $1$ as $p$ goes to $1$.
In the past few years several applications of optimal
experimental designs have emerged to optimize the measurements
in communication networks. The optimal design problems arising from
this kind of applications share three interesting properties:
(i) measurements are only available at a small number of locations of the network;
(ii) each monitor can simultaneously measure several quantities, which
can be modeled by ``multiresponse experiments";
(iii) the observation matrices depend on the topology of the network.
In this paper, we give an overview of these experimental design
problems and recall recent results for the computation of optimal
designs by Second Order Cone Programming (SOCP). New results for the
network-monitoring of a discrete time process are presented. In particular, we show
that the optimal design problem for the monitoring of an AR1 process can be reduced
to the standard form and we give experimental results.
We show that a class of semidefinite programs (SDP) admits a solution that is a positive semidefinite
matrix of rank at most $r$, where $r$ is the rank of the matrix involved in the objective function of the SDP.
The optimization problems of this class are semidefinite packing problems,
which are the SDP analogs to vector packing problems.
Of particular interest is the case in which our result guarantees the existence of a solution
of rank one: we show that the computation of this solution actually reduces to a
Second Order Cone Program (SOCP).
We point out an application in statistics, in the optimal design of experiments.
In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result into characterizations of all facet defining {0,+1,-1}-inequalities for the hop constrained chain polytope and all facet defining {0,1}-inequalities
for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper of Dahl and Gouveia in 2004.
This thesis is about mathematical optimization for the efficient use of railway infrastructure. We address the
optimal allocation of the available railway track capacity - the track allocation problem.
This track allocation problem is a major challenge for a railway company, independent of
whether a free market, a private monopoly, or a public monopoly is given.
Planning and operating railway transportation systems is extremely hard due
to the combinatorial complexity of the underlying discrete optimization problems,
the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization
techniques can result in huge gains for both railway customers and operators, e.g.,
in terms of cost reductions or service quality improvements.
We tackle this challenge by developing novel mathematical models and associated innovative algorithmic
solution methods for large scale instances. This allows us to produce for the first time reliable
solutions for a real world instance, i.e., the Simplon corridor in Switzerland.
The opening chapter gives a comprehensive overview on railway planning problems.
This provides insights into the regulatory and technical framework,
it discusses the interaction of several planning steps, and identifies optimization potentials in
railway transportation. The remainder of the thesis is comprised of two major parts.
The first part is concerned with modeling railway systems to allow for resource and capacity analysis.
Railway capacity has basically two dimensions, a space dimension which are the physical
infrastructure elements as well as a time dimension that refers to the train movements, i.e.,
occupation or blocking times, on the physical infrastructure. Railway safety systems operate
on the same principle all over the world. A train has to reserve infrastructure blocks for some time to pass through.
Two trains reserving the same block of the infrastructure within the same point in time is called block conflict.
Therefore, models for railway capacity involve the definition
and calculation of reasonable running and associated reservation and
blocking times to allow for a conflict free allocation.
In the second and main part of the thesis, the optimal track
allocation problem for macroscopic models of the railway system is considered.
The literature for related problems is surveyed.
A graph-theoretic model for the track allocation problem is
developed. In that model optimal track allocations correspond to
conflict-free paths in special time-expanded graphs.
Furthermore, we made considerable progress on solving track allocation problems by two
main features - a novel modeling approach for the macroscopic track
allocation problem and algorithmic improvements based on the
utilization of the bundle method.
Finally, we go back to practice and present in the last chapter several case
studies using the tools netcast and tsopt.
We provide a computational comparison of
our new models and standard packing models used in the literature.
Our computational experience indicates that our approach, i.e.,
``configuration models'', outperforms other models. Moreover, the rapid branching
heuristic and the bundle method enable us to produce high quality solutions for very large scale
instances, which has not been possible before.
In addition, we present results for a theoretical and rather visionary auction framework
for track allocation. We discuss several auction design questions and analyze experiments of
various auction simulations.
The highlights are results for the Simplon corridor in Switzerland.
We optimized the train traffic through this tunnel using our models and
software tools.
To the best knowledge of the author and confirmed by several railway
practitioners this was the first time that fully automatically produced
track allocations on a macroscopic scale fulfill the requirements
of the originating microscopic model, withstand the evaluation in the
microscopic simulation tool OpenTrack, and exploit the infrastructure capacity.
This documents the success of our approach in practice and the usefulness
and applicability of mathematical optimization to railway track allocation.
In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ".
Das vom BMBF geförderte Projekt FTTX-PLAN entwickelt mathematische Modelle und Optimierungsverfahren, um automatisiert kostenoptimierte FTTx-Netze berechnen zu können. Wir zeigen anhand einer Praxisstudie in Zusammenarbeit mit der Regensburger R-KOM, wie ein Planer von diesen Verfahren profitieren kann, um die Auswirkungen bestimmter Entscheidungen auf die Netzstruktur und -kosten zu untersuchen. Wir illustrieren dies am Beispiel eines FTTB/FTTH-Vergleichs, der Variation von Kundenanbindungsraten und der gezielten Ausnutzung existierender Leerrohre, um Tiefbau zu vermeiden.