# Library

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
• English  (260)
Source
Keywords
Language
• 1
Unknown
Publication Date: 2020-03-09
Description: In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the %LP- and MIP-libraries \Netlib{} and MIPLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 2
Unknown
Publication Date: 2020-08-05
Description: This paper is about {\em set packing relaxations\/} of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and vertex packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 3
Publication Date: 2020-08-05
Description: This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 4
Unknown
Publication Date: 2020-08-05
Description: We propose an efficient column generation method to minimize the probability of delay propagations along aircraft rotations. In this way, delay resistant schedules can be constructed. Computational results for large-scale real-world problems demonstrate substantial punctuality improvements. The method can be generalized to crew and integrated scheduling problems.
Keywords: ddc:510
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 5
Unknown
Publication Date: 2020-08-05
Description: 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.
Keywords: ddc:510
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 6
Unknown
Publication Date: 2020-12-15
Description: 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.
Keywords: ddc:510
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 7
Unknown
Publication Date: 2020-08-05
Description: We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 8
Publication Date: 2020-08-05
Description: Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional $\epsilon$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/pdf
Format: application/postscript
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 9
Unknown
Publication Date: 2020-12-15
Description: 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 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 directed formulation, which is stronger than the natural undirected one, plays a central role.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 10
Unknown
Publication Date: 2020-08-05