Refine
Document Type
- ZIB-Report (5)
- In Proceedings (4)
- Article (1)
- Doctoral Thesis (1)
- Master's Thesis (1)
Language
- English (12)
Keywords
- assignment (2)
- hyperassignment (2)
- hypergraph (2)
- bipartite (1)
- directed hypergraphs (1)
- facet (1)
- facet classification (1)
- hyperassignments (1)
- inequality (1)
- matching (1)
Institute
Vehicle rotation planning for long distance passenger railways is a fundamental
problem in rail transport. It deals with the allocation of vehicles to trips
in a cyclic weekly schedule. Its result is an assignment of each trip to a follow-on
trip which will be serviced by the same vehicle.
To take so-called regularity, which is an important requirement, into account,
vehicle rotation planning can be modeled as a hyperassignment problem. This is
a generalization of the assignment problem to directed hypergraphs we propose.
We prove that the hyperassignment problem is NP-hard for the practically
relevant cases and that the canonical integer linear programming (ILP)
formulation results in large integrality gaps and arbitrarily high basis matrix
determinants.
Our main contribution is an extended ILP formulation, which provably
implies important classes of inequalities, e. g., all clique inequalities. Clique inequalities
are of great importance, because as calculations with practical data show they highly reduce the LP-IP gap. The extended
formulation can be solved by column generation. We propose fast combinatorial
algorithms for the pricing subproblem.
Vehicle rotation planning is a fundamental problem in
rail transport. It decides how the railcars, locomotives, and
carriages are operated in order to implement the trips of the
timetable. One important planning requirement is operational
regularity, i.e., using the rolling stock in the same way on every
day of operation. We propose to take regularity into account by
modeling the vehicle rotation planning problem as a minimum cost
hyperassignment problem (HAP). Hyperassignments are generalizations
of assignments from directed graphs to directed hypergraphs.
Finding a minimum cost hyperassignment is
NP-hard.
Most instances arising from regular vehicle rotation planning, however, can
be solved well in practice. We show that, in particular, clique
inequalities strengthen the canonical LP relaxation substantially.
Usually complete linear descriptions of polytopes consist of
an enormous number of facet-defining inequalities already
for very small problem sizes. In this paper, 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 a polytope. We propose an algorithm
for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem.
The hypergraph assignment problem (HAP) is the generalization of assignments
from directed graphs to directed hypergraphs. It serves, in particular,
as a universal tool to model several train composition rules in vehicle rotation
planning for long distance passenger railways. We prove that even for problems
with a small hyperarc size and hypergraphs with a special partitioned structure
the HAP is NP-hard and APX-hard. Further, we present an extended integer
linear programming formulation which implies, e. g., all clique inequalities.
Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially.
The analysis of random instances of a combinatorial optimization problem, especially their optimal values, can provide a better insight into its structure. Such an extensive analysis was theoretically and practically done for the assignment problem ("random assignment problem") and several of its generalizations.
For a recent generalization of the assignment problem to bipartite hypergraphs, the hypergraph assignment problem, such results do not exist so far. We consider a random version of the hypergraph assignment problem for the simplest possible complete bipartite hypergraphs. They have only edges and proper hyperedges of size four and follow a special structure, but the hypergraph assignment problem for this type of hypergraphs is, however, already NP-hard. It can be viewed as a combination of two assignment problems.
For random hyperedge costs exponentially i.i.d. with mean 1 we show computational results that suggest that the expected value of minimum cost hyperassignments converges to some value around 1.05 with a small standard deviation. The computational results also suggest that the optimal value is most probably attained with half of the maximum possible number of proper hyperedges.
The main result of this paper is the proof that the expected value of a minimum cost hyperassignment which uses exactly half the possible maximum number of proper hyperedges if the vertex number tends to infinity lies between 0.3718 and 1.8310 when hyperedge costs are exponentially i.i.d. with mean 1.
The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled a tour
is evaluated by taking also preferences into account which
address the sequence in which the targets are visited. The
problem thus is a combination of two well-known combinato-
rial optimization problems: the traveling salesman and the
linear ordering problem. In this paper we present several
possible IP-Models for this problem and compared them to
their usability for branch-and-cut approaches.
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.
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.