90C10 Integer programming
Refine
Year of publication
Document Type
- ZIB-Report (83)
- Doctoral Thesis (4)
- Habilitation (2)
Is part of the Bibliography
- no (89)
Keywords
Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They help to reach optimality faster and provide good feasible solutions early in the solving process. In this paper, we present two new primal heuristics which take into account global structures available within MIP solvers to construct feasible solutions at the beginning of the solving process. These heuristics follow a large neighborhood search (LNS) approach and use global structures to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. The definition of the neighborhood is done by iteratively fixing variables and propagating these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. The neighborhood is solved as a sub-MIP and solutions are transferred back to the original problem. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about every third instance and therewith help to improve the average solving time.
The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.
In mixed-integer programming, the branching rule is a key component to a fast convergence of the branch-and-bound algorithm. The most common strategy is to branch on simple disjunctions that split the domain of a single integer variable into two disjoint intervals. Multi-aggregation is a presolving step that replaces variables by an affine linear sum of other variables, thereby reducing the problem size. While this simplification typically improves the performance of MIP solvers, it also restricts the degree of freedom in variable-based branching rules.
We present a novel branching scheme that tries to overcome the above drawback by considering general disjunctions defined by multi-aggregated variables in addition to the standard disjunctions based on single variables. This natural idea results in a hybrid between variable- and constraint-based branching rules. Our implementation within the constraint integer programming framework SCIP incorporates this into a full strong branching rule and reduces the number of branch-and-bound nodes on a general test set of publicly available benchmark instances. For a specific class of problems, we show that the solving time decreases significantly.
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.
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.
The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.
This thesis deals with the hypergraph assignment problem (HAP), a set partitioning problem in a special type of hypergraph. The HAP generalizes the assignment problem from bipartite graphs to what we call bipartite hypergraphs, and is motivated by applications in railway vehicle rotation planning. The main contributions of this thesis concern complexity, polyhedral results, analyses of random instances, and primal methods for the HAP. We prove that the HAP is NP-hard and APX-hard even for small hyperedge sizes and hypergraphs with a special partitioned structure. We also study the complexity of the set packing and covering relaxations of the HAP, and present for certain cases polynomial exact or approximation algorithms. A complete linear description is known for the assignment problem. We therefore also study the HAP polytope. There, we have a huge number of facet-defining inequalities already for a very small problem size. We describe a method for dividing the inequalities into equivalence classes without resorting to a normal form. Within each class, facets are related by certain symmetries and it is sufficient to list one representative of each class to give a complete picture of the structural properties of the polytope. We propose the algorithm "HUHFA" for the classification that is applicable not only to the HAP but combinatorial optimization problems involving symmetries in general. In the largest possible HAP instance for which we could calculate the complete linear description, we have 14049 facets, which can be divided into 30 symmetry classes. We can combinatorially interpret 16 of these classes. This is possible by employing cliques to generalize the odd set inequalities for the matching problem. The resulting inequalities are valid for the polytope associated with the set packing problem in arbitrary hypergraphs and have a clear combinatorial meaning. An analysis of random instances provides a better insight into the structure of hyperassignments. Previous work has extensively analyzed random instances for the assignment problem theoretically and practically. As a generalization of these results for the HAP, we prove bounds on the expected value of a minimum cost hyperassignment that uses half of the maximum possible number of hyperedges that are not edges. In a certain complete partitioned hypergraph G2,2n with i. i. d. exponential random variables with mean 1 as hyperedge costs it lies between 0.3718 and 1.8310 if the vertex number tends to infinity. Finally, we develop an exact combinatorial solution algorithm for the HAP that combines three methods: A very large-scale neighborhood search, the composite columns method for the set partitioning problem, and the network simplex algorithm.
This thesis introduces the Steiner connectivity problem. It is a generalization of the well
known Steiner tree problem. Given a graph G = (V, E) and a subset T ⊆ V of the nodes,
the Steiner tree problem consists in finding a cost minimal set of edges connecting all
nodes in T . The Steiner connectivity problem chooses, instead of edges, from a given set
of paths a subset to connect all nodes in T . We show in the first part of this thesis that
main results about complexity, approximation, integer programming formulations, and
polyhedra can be generalized from the Steiner tree problem to the Steiner connectivity
problem.
An example for a straightforward generalization are the Steiner partition inequalities, a
fundamental class of facet defining inequalities for the Steiner tree problem. They can be
defined for the Steiner connectivity problem in an analogous way as for the Steiner tree
problem. An example for a generalization that needs more effort is the definition of a
directed cut formulation and the proof that this dominates the canonical undirected cut
formulation enriched by all Steiner partition inequalities. For the Steiner connectivity
problem this directed cut formulation leads to extended formulations, a concept that is
not necessary for the Steiner tree problem. There are also major differences between
both problems. For instance, the case T = V for the Steiner connectivity problem is
equivalent to a set covering problem and, hence, not a polynomial solvable case as in the
Steiner tree problem.
The Steiner connectivity problem is not only an interesting generalization of the Steiner
tree problem but also the underlying connectivity problem in line planning with inte-
grated passenger routing. The integrated line planning and passenger routing problem
is an important planning problem in service design of public transport and the topic of
the second part. Given is the infrastructure network of a public transport system where
the edges correspond to streets and tracks and the nodes correspond to stations/stops
of lines. The task is to find paths in the infrastructure network for lines and passengers
such that the capacities of the lines suffice to transport all passengers. Existing models
in the literature that integrate a passenger routing in line planning either treat transfers
in a rudimentary way and, hence, neglect an important aspect for the choice of the pas-
senger routes, or they treat transfers in a too comprehensive way and cannot be solved
for large scale real world problems. We propose a new model that focuses on direct
connections. The attractiveness of transfer free connections is increased by introducing a transfer penalty for each non-direct connection. In this way, a passenger routing is
computed that favors direct connections.
For the computation of this model we also implemented algorithms influenced by the
results for the Steiner connectivity problem. We can compute with our model good
solutions that minimize a weighted sum of line operating costs and passengers travel
times. These solutions improve the solutions of an existing approach, that does not
consider direct connections, by up to 17%. In contrast to a comprehensive approach,
that considers every transfer and for which we could not even solve the root LP within
10 hours for large instances, the solutions of the new model, computed in the same time,
are close to optimality (<1%) or even optimal for real world instances. In a project with
the Verkehr in Potsdam GmbH to compute the line plan for 2010 we showed that our
approach is applicable in practice and can be used to solve real world problems.
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 show that the concept of metric inequalities to characterize capacities that
support a multi-commodity flow can be generalized to deal with direct connections.