Refine
Year of publication
- 2014 (22) (remove)
Document Type
- ZIB-Report (18)
- Master's Thesis (4)
Has Fulltext
- yes (22) (remove)
Keywords
Institute
- Mathematical Optimization (22) (remove)
Modern solving software for mixed-integer programming (MIP)
incorporates numerous algorithmic components whose behavior is
controlled by user parameter choices,
and whose usefulness dramatically varies depending on the progress of the solving process.
In this thesis, our aim is to
construct a phase-based solver that dynamically reacts
on phase transitions with an appropriate change of its component behavior.
Therefore, we decompose the branch-and-bound solving process into three distinct phases:
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 construct a phase-based solver to make use of the phase concept in two steps:
First, we identify promising components for every solving phase individually and show that their
combination is beneficial on a test bed of practical MIP instances.
We then present and evaluate three heuristic criteria to make use of the phase-based solver
in practice, where it is infeasible to distinguish between the last two phases
before the termination of the solving process.
Many optimization problems can be modeled as Mixed Integer Programs (MIPs). In general, MIPs cannot be solved efficiently, since solving MIPs is NP-hard, see, e.g., Schrijver, 2003. Common methods for solving NP-hard problems are branch-and-bound and column generation. In the case of column generation, the original problem
becomes decomposed or re-formulated into one ore more smaller subproblems, which are easier to solve. Each of these subproblems is solved separately and recurrently, which can be interpreted as solving a sequence of optimization problems.
In this thesis, we consider a sequence of MIPs which only differ in the respective objective functions. Furthermore, we assume each of these MIPs get solved with a branch-and-bound algorithm. This thesis aims to figure out whether the solving process of a given sequence of MIPs can be accelerated by reoptimization. As reoptimization we understand starting the solving process
of a MIP of this sequence at a given frontier of a search tree corresponding to another MIP of this sequence.
At the beginning we introduce an LP-based branch-and-bound algorithm. This algorithm is inspired by the reoptimizing algorithm of Hiller, Klug, and the author of this
thesis, 2013. Since most of the state-of-the-art MIP
solvers come to decisions based on dual information, which leads to the loss of feasible solutions after changing the objective function, we present a technique to guarantee optimality despite using these information. A decision is based on a dual information if this decision is valid for at least one feasible solution, whereas a decision is based on a primal information if this decision is valid for all feasible solutions. Afterwards, we consider representing the search frontier of the tree by a set of nodes of a given size. We call this the Tree Compression Problem. Moreover, we present a criterion characterizing the similarity of two objective functions. To evaluate our approach of reoptimization we extend the well-known and well-maintained MIP solver SCIP to an LP-based branch-and-bound framework, introduce two heuristics for solving the Tree Compression Problem, and a primal heuristic which is especially fitted to column generation. Finally, we present computational experiments on several problem classes, e.g., the Vertex Coloring and k-Constrained Shortest Path. Our experiments show, that a straightforward reoptimization, i.e., without additional heuristics, provides no benefit in general. However, in combination with the techniques and methods presented in this thesis, we can accelerate the solving of a given sequence up to the factor 14. For this purpose it is essential to take the differences of the objective functions into account and to restart the reoptimization, i.e., solve the subproblem from scratch, if the objective functions are not similar enough. Finally, we discuss the possibility to parallelize the solving process of the search frontier at the beginning of each solving process.
We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.
The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity.
In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem.
We consider a stationary discrete-time linear process that can be observed by a finite number of sensors.
The experimental design for the observations consists of an allocation of available resources to these sensors.
We formalize the problem of selecting a design that maximizes the information matrix of the steady-state of the Kalman filter,
with respect to a standard optimality criterion, such as $D-$ or $A-$optimality.
This problem generalizes the optimal experimental design problem for a linear regression model with a finite design space and uncorrelated errors.
Finally, we show that under natural assumptions, a steady-state optimal design can be computed by semidefinite programming.
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 introduce the class of spot-checking games (SC games). These games model
problems where the goal is to distribute fare inspectors over a toll network.
Although SC games are not zero-sum, we show that a Nash equilibrium
can be computed by linear programming.
The computation of a strong Stackelberg equilibrium is
more relevant for this problem, but we show that this is NP-hard.
However, we give some bounds on the \emph{price of spite},
which measures how the
payoff of the inspector
degrades when committing to a Nash equilibrium.
Finally, we demonstrate the quality of these bounds for a real-world application,
namely the enforcement of a truck toll on German motorways.
As a basis for meaningful simulation and optimization efforts with regard to traffic engineering or energy consumption in telecommunication networks, suitable models are indispensable. This concerns not only realistic network topologies, but also models for the geographical distribution and the temporal dynamics of traffic, as well as the assumptions on network components and technology. This paper derives such a model from the practice of a large national carrier.
Applying the network and traffic model, we demonstrate its use by presenting various optimization cases related to energy-efficient telecommunication. Here, we focus on load-adaptivity by employing sleep modes to the network hardware, where several constraints on the reconfigurability of the network over time are considered.
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.
In this article we describe the impact from embedding a 15 year old model for solving the Steiner tree problem in graphs in a state-of-the-art MIP-Framework, making the result run in a massively parallel environment and extending the model to solve as many variants as possible. We end up with a high-perfomance solver that is capable of solving previously unsolved instances and, in contrast to its predecessor, is freely available for academic research.