Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
  • 21
    facet.materialart.
    Unknown
    Decomposing Matrices into Blocks (1997)
    Details
    Publication Date: 2020-08-05
    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 MITLIB 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. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 22
    facet.materialart.
    Unknown
    Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System (1997)
    Details
    Publication Date: 2020-08-05
    Description: {\em Telebus\/} is Berlin's dial-a-ride system for handicapped people that cannot use the public transportation system. The service is provided by a fleet of about 100 mini-busses and includes aid to get in and out of the vehicle. Telebus has between 1,000 and 1,500 transportation requests per day. The problem arises to schedule these requests into the vehicles such that punctual service is provided while operation costs should be minimum. Additional constraints include pre-rented vehicles, fixed bus driver shift lengths, obligatory breaks, and different vehicle capacities. We use a {\em set partitioning\/} approach for the solution of the bus scheduling problem that consists of two steps. The first {\em clustering\/} step identifies segments of possible bus tours (``orders'') such that more than one person is transported at a time; the aim in this step is to reduce the size of the problem and to make use of larger vehicle capacities. The problem to select a set of orders such that the traveling distance of the vehicles within the orders is minimal is a set partitioning problem that we can solve to optimality. In the second step the selected orders are {\em chained\/} to yield possible bus tours respecting all side constraints. The problem to select a set of such bus tours such that each order is serviced once and the total traveling distance of the vehicles is minimum is again a set partitioning problem that we solve approximately. We have developed a computer system for the solution of the bus scheduling problem that includes a branch-and-cut algorithm for the solution of the set partitioning problems. A version of this system is in operation at Telebus since July 1995. Its use made it possible that Telebus can service today about 30\% more requests per day for the same amount of money than before.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 23
    facet.materialart.
    Unknown
    Optimierung des Berliner Behindertenfahrdienstes (1997)
    Details
    Publication Date: 2020-08-05
    Description: In diesem Artikel geben wir einen Überblick über das Telebus-Projekt am Konrad-Zuse-Zentrum, Berlin, durch das der Behindertenfahrdienst in Berlin reorganisiert und optimiert wurde. Wir berichten kurz über die mathematischen Probleme und, etwas ausführlicher, über die nicht-mathematischen Schwierigkeiten, die bei der Durchführung dieses Projektes auftraten.
    Keywords: ddc:000
    Language: German
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 24
    facet.materialart.
    Unknown
    Frequency Assignment in Cellular Phone Networks (1997)
    Details
    Publication Date: 2020-03-09
    Description: We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 25
    facet.materialart.
    Unknown
    Discrete Relaxations of Combinatorial Programs (1997)
    Details
    Publication Date: 2020-08-05
    Description: This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 26
    facet.materialart.
    Unknown
    The Orientation Model for Frequency Assignment Problems (1998)
    Details
    Publication Date: 2020-03-09
    Description: Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow 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
    BibTip Others were also interested in ...
    OPUS
  • 27
    facet.materialart.
    Unknown
    Solving Railway Track Allocation Problems (2007)
    Details
    Publication Date: 2020-08-05
    Description: The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Format: application/postscript
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 28
    facet.materialart.
    Unknown
    Models for Line Planning in Public Transport (2004)
    Details
    Publication Date: 2020-12-15
    Description: The \emph{line planning problem} is one of the fundamental problems in strategic planning of public and rail transport. It consists of finding lines and corresponding frequencies in a public transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize its operating cost; the passengers request short travel times. We propose two new multi-commodity flow models for line planning. Their main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 29
    facet.materialart.
    Unknown
    A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit (2004)
    Details
    Publication Date: 2020-03-09
    Description: This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 30
    facet.materialart.
    Unknown
    An Auctioning Approach to Railway Slot Allocation (2005)
    Details
    Publication Date: 2020-08-05
    Description: We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Format: application/postscript
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...