90C27 Combinatorial optimization
Refine
Keywords
- branch-and-cut (5)
- integer programming (4)
- combinatorial optimization (3)
- line planning (3)
- mixed integer programming (3)
- optimization software (3)
- SCIP (2)
- approximation algorithm (2)
- chip verification (2)
- computational complexity (2)
In the connected facility location problem with buy-at-bulk edge costs we are given a set of clients with positive demands and a set of potential facilities with opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity such that the cost per capacity decreases from small to large cables, and a core cable type of innite capacity. The task is to open some facilities and to connect them by a Steiner tree using core cables, and to build a forest network using access cables such that the edge capacities suce to simultaneously route all client demands unsplit to the open facilities. The objective is to minimize the total cost of opening facilities, building the core Steiner tree, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for this problem based on a random sampling technique.
We consider a generalization of the connected facility location problem where the clients must be connected to the open facilities via shared capacitated (tree) networks instead of independent shortest paths. This problem arises in the planning of ber optic telecommunication access networks, for example. Given a set of clients with positive demands, a set of potential facilities with opening costs, a set of capacitated access cable types, and a core cable type of innite capacity, one has to decide which facilities to open, how to interconnect them using a Steiner tree of innite capacity core cables, and which access cable types to install on which potential edges such that these edges form a forest and the installed capacities suce to simultaneously route the client demands to the open facilities via single paths. The objective is to minimize the total cost of opening facilities, building the core Steiner tree among them, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for problem instances where the access cable types obey economies of scale. In the special case where only multiples of a single cable type can be installed on the access edges, a variant of our algorithm achieves a performance guarantee of 6.72.
The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.
Affinely-Adjustable Robust Counterparts provide tractable alternatives to (two-stage) robust programs with arbitrary recourse. We apply them to robust network design with polyhedral demand uncertainty, introducing the affine routing principle. We compare the affine routing to the well-studied static and dynamic routing schemes for robust network design. All three schemes are embedded into the general framework of two-stage network design with recourse. It is shown that affine routing can be seen as a generalization of the widely used static routing still being tractable and providing cheaper solutions. We investigate properties on the demand polytope under which affine routings reduce to static routings and also develop conditions on the uncertainty set leading to dynamic routings being affine. We show however that affine routings suffer from the drawback that (even totally) dominated demand vectors are not necessarily supported by affine solutions. Uncertainty sets have to be designed accordingly. Finally, we present computational results on networks from SNDlib. We conclude that for these instances the optimal solutions based on affine routings tend to be as cheap as optimal network designs for dynamic routings. In this respect the affine routing principle can be used to approximate the cost for two-stage solutions with free recourse which are hard to compute.
The Steiner connectivity problem is a generalization of
the Steiner tree problem. It consists in finding a minimum cost set of
simple paths to connect a subset of nodes in an undirected graph.
We show that important polyhedral and algorithmic results on the
Steiner tree problem carry over to the Steiner connectivity problem,
namely, the Steiner cut and the Steiner partition inequalities, as
well as the associated polynomial time separation algorithms, can be
generalized. Similar to the Steiner tree case, a certain directed
formulation, which is stronger than the natural undirected one,
plays a central role.
We introduce an optimization model for the line planning problem in a public transportation system that aims at minimizing operational costs while ensuring a given level of quality of service in terms of available transport capacity. We discuss the computational complexity of the model for tree network topologies and line structures that arise in a real-world application at the Trolebus Integrated System in Quito. Computational results for this system are reported.
This paper introduces the line connectivity
problem, a generalization of the Steiner tree problem and a
special case of the line planning problem. We study its complexity and
give an IP formulation in terms of an exponential number of
constraints associated with "line cut constraints". These inequalities
can be separated in polynomial time. We also generalize the Steiner
partition inequalities.
Die Angebotsplanung im öffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,
Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und
Preisplanung vor. Wir zeigen anhand von Berechnungen für die Verkehrsbetriebe in Potsdam
(ViP), dass sich damit komplexe Zusammenhänge quantitativ analysieren lassen. Auf diese
Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien
und die Wahl von Reisewegen der Passagiere, Abhängigkeiten zwischen Kosten und Reisezeiten
sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.
Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.
Line planning is an important step in the strategic planning
process of a public transportation system. In this paper, we discuss an
optimization model for this problem in order to minimize operation costs
while guaranteeing a certain level of quality of service, in terms of
available transport capacity. We analyze the problem for path and tree
network topologies as well as several categories of line operation that
are important for the Quito Trolebus system. It turns out that, from a
computational complexity worst case point of view, the problem is hard in
all but the most simple variants. In practice, however, instances based
on real data from the Trolebus System in Quito can be solved quite well,
and significant optimization potentials can be demonstrated.