Refine
Year of publication
Document Type
- ZIB-Report (32)
- Doctoral Thesis (3)
- Habilitation (1)
Language
- English (36)
Is part of the Bibliography
- no (36)
Keywords
- integer programming (36) (remove)
Institute
In this article, we introduce parallel mixed integer linear programming (MILP) solvers. MILP solving algorithms have been improved tremendously in the last two decades. Currently, commercial MILP solvers are known as a strong optimization tool. Parallel MILP solver development has started in 1990s. However, since the improvements of solving algorithms have much impact to solve MILP problems than application of parallel computing, there were not many visible successes. With the spread of multi-core CPUs, current state-of-the-art MILP solvers have parallel implementations and researches to apply parallelism in the solving algorithm also getting popular. We summarize current existing parallel MILP solver architectures.
Mixed integer programming has become a very powerful tool for modeling and
solving real-world planning and scheduling problems, with the breadth of
applications appearing to be almost unlimited. A critical component in
the solution of these mixed-integer programs is a set of routines commonly
referred to as presolve. Presolve can be viewed as a collection of
preprocessing techniques that reduce the size of and, more importantly,
improve the ``strength'' of the given model formulation, that is, the degree
to which the constraints of the formulation accurately describe the
underlying polyhedron of integer-feasible solutions. As our computational
results will show, presolve is a key factor in the speed with which we can
solve mixed-integer programs, and is often the difference between a model
being intractable and solvable, in some cases easily solvable. In this
paper we describe the presolve functionality in the Gurobi commercial
mixed-integer programming code.
This includes an overview, or taxonomy of the different methods that are
employed, as well as more-detailed descriptions of several of the techniques,
with some of them appearing, to our knowledge, for the first time in the
literature.
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.
We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows.
The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.
We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method.
In this thesis, we develop methods in mathematical optimization to dimension networks at minimal cost. Given hardware and cost models, the challenge is to provide network topologies and efficient capacity plans that meet the demand for network traffic (data, passengers, freight). We incorporate crucial aspects of practical interest such as the discrete structure of available capacities as well as the uncertainty of demand forecasts. The considered planning problems typically arise in the strategic design of telecommunication or public transport networks and also in logistics. One of the essential aspects studied in this work is the use of cutting planes to enhance solution approaches based on multi-commodity flow formulations. Providing theoretical and computational evidence for the efficacy of inequalities based on network cuts, we extend existing theory and algorithmic work in different directions. First, we prove that special-purpose techniques, originally designed to solve capacitated network design problems, can be successfully integrated into general-purpose mixed integer programming (MIP) solvers. Our approach relies on an automatic detection of network structure within the constraint matrix of general mixed in teger programs. More precisely, we identify multi-commodity (MCF) network sub-matrices and resolve the isomorphisms of the commodity blocks as well as the original graph structure. In the subsequent separation framework, we guide the constraint aggregation of available cutting plane procedures (e. g. based on mixed integer rounding) to produce strong cutting planes that reflect the structure of the constructed network. The new MCF-separator integrates network design specific methodology into general optimization tools which is of particular importance for practitioners that tend to use MIP solvers as black boxes. Extensive computational tests show that our network detection procedure operates accurately and reliably. Moreover, due to the generated cutting planes, we achieve an average speed-up of a factor of two for pure network design problems with general MIP solvers. Many of these instances can only be solved to optimality in reasonable time if the new MCF-separator is active. In 9 % of the instances of general MIP test sets we find consistent embedded networks and generate violated inequalities. In this case the computation time decreases by 18 % on average with almost no degradation for unaffected instances. Second, we generalize concepts, models, and cutting planes from deterministic network design to robust network design, incorporating the uncertainty of traffic demands. We enhance and compare strategies that are able to handle a polyhedral set of different traffic scenarios. In particular, we consider two correlated solution methods, based on separating extreme demand scenarios and dualizing the linear description of the demand polytope, respectively. We consider robust network design as two-stage robust optimization with recourse. First stage capacity decisions are fixed for all scenarios while the second stage flow depends on the realized demands. In order to reroute the traffic as a function of the demand dynamics, we consider three alternative recourse actions, namely, static, affine, and dynamic routing. We analyze properties of the new affine routing and show that it combines advantages of the well-known static and dynamic models. Using the concept of robust cut-set polyhedra and the corresponding lifting theorems, we develop several classes of facet-defining inequalities based on network cuts that can be used to further accelerate solution strategies for robust network design. Among them are the well-known (flow) cut-set inequalities, which we generalize to general demand polytopes, but also new classes of potential cutting planes, so-called envelope inequalities. The practical importance of the developed cutting planes is revealed by a series of computational tests. Similar to the results for the MCF-separator we achieve speed-ups of two and more using the generalized classes of strong inequalities. To evaluate the robustness of solutions that are computed with our framework we use real-life measurements of traffic dynamics from different existing telecommunication networks, among them data from the German and the European research network. Our results indicate that traffic peaks do not necessarily occur all simultaneously with respect to different source-destination pairs, which is of practical importance for the design of uncertainty sets. It is, in particular, not necessary to dimension networks for a scenario that assumes all source-destination traffic is at its peak simultaneously. With our solutions we save up to 20 % of the corresponding solution cost compared to this artificial scenario and achieve comparable levels of robustness.
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.
The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of
extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.
The steel mill slab design problem from the CSPLIB is a combinatorial
optimization problem motivated by an application of the steel industry. It
has been widely studied in the constraint programming community. Several
methods were proposed to solve this problem. A steel mill slab library was
created which contains 380 instances. A closely related binpacking problem
called the multiple knapsack problem with color constraints, originated
from the same industrial problem, was discussed in the integer programming
community. In particular, a simple integer program for this problem has
been given by Forrest et al. The aim of this paper is to bring these
different studies together. Moreover, we adapt the model of Forrest et
al. for the steel mill slab design problem. Using this model and a
state-of-the-art integer program solver all instances of the steel mill
slab library can be solved efficiently to optimality. We improved,
thereby, the solution values of 76 instances compared to previous results.
Finally, we consider a recently introduced variant of the steel mill slab
design problem, where within all solutions which minimize the leftover one
is interested in a solution which requires a minimum number of slabs. For
that variant we introduce two approaches and solve all instances of the
steel mill slab library with this slightly changed objective function to
optimality.
We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by “connection capacities” into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results.