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
  • 1
    Electronic Resource
    Electronic Resource
    On the acyclic subgraph polytope (1985)
    Springer
    Mathematical programming 33 (1985), S. 28-42 
    Details
    ISSN: 1436-4646
    Keywords: Acyclic Subgraph Problem ; Feedback Arc Set Problem ; Facets of Polyhedra ; Polynomial Time Algorithms ; Weakly Acyclic Digraphs
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The acyclic subgraph problem can be formulated as follows. Given a digraph with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. We investigate this problem from a polyhedral point of view and determine several classes of facets for the associated acyclic subgraph polytope. We also show that the separation problem for the facet defining dicycle inequalities can be solved in polynomial time. This implies that the acyclic subgraph problem can be solved in polynomial time for weakly acyclic digraphs. This generalizes a result of Lucchesi for planar digraphs.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582009
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Solution of large-scale symmetric travelling salesman problems (1991)
    Springer
    Mathematical programming 51 (1991), S. 141-202 
    Details
    ISSN: 1436-4646
    Keywords: 05C04 ; 05C45 ; 90C10 ; Travelling salesman problem ; cutting plane algorithms ; polyhedral combinatorics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we report on a cutting plane procedure with which we solved symmetric travelling salesman problems of up to 1000 cities to optimality. Our implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope. We describe the important ingredients of our code and give an extensive documentation of its computational performance.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586932
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A cutting plane algorithm for minimum perfect 2-matchings (1987)
    Springer
    Computing 39 (1987), S. 327-344 
    Details
    ISSN: 1436-5057
    Keywords: 05-04 ; 05C45 ; 90C10 ; Matching ; cutting plane algorithm ; polyhedral combinatorics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Description / Table of Contents: Zusammenfassung Wir beschreiben die Implementierung eines Schnittebenenverfahrens zur Bestimmung minimaler gewichteter perfekter 2-Matchings. Der Algorithmus baut auf der vollständigen Beschreibung des perfekten 2-Matching-Polytops, die Edmonds angegeben hat, auf und verwendet die Simplexmethode zur Lösung der im Verfahren auftretenden LP-Relaxierungen. Schnittebenen werden entweder mit schnellen Heuristiken bestimmt, oder, falls diese nicht erfolgreich sind, mit einer effizienten und auf 2-matching-Ungleichungen abgestimmten Implementierung des Padberg-Rao-Verfahrens. Mit diesem Algorithmus konnten 2-Matching-Probleme in vollständigen Graphen mit bis zu 1000 Knoten, d. h. mit bis zu 499.500 Variablen, in weniger als einer Stunde CPU-Zeit auf einem Rechner mittlerer Leistung gelöst werden.
    Notes: Abstract We describe an implementation of a cutting plane algorithm for the minimum weight perfect 2-matching problem. This algorithm is based on Edmonds' complete description of the perfect 2-matching polytope and uses the simplex algorithm for solving the LP-relaxations coming up. Cutting planes are determined by fast heuristics, or, if these fail, by an efficient implementation of the Padberg-Rao procedure, specialized for 2-matching constraints. With this algorithm 2-matching problems on complete graphs with up to 1000 nodes (i.e., 499,500 variables) have been solved in less than 1 hour CPU time on a medium speed computer.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02239975
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Facets of the linear ordering polytope (1985)
    Springer
    Mathematical programming 33 (1985), S. 43-60 
    Details
    ISSN: 1436-4646
    Keywords: Facets of Polyhedra ; Linear Ordering Problem ; Triangulation Problem ; Permutation Problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetD n be the complete digraph onn nodes, and letP LO n denote the convex hull of all incidence vectors of arc sets of linear orderings of the nodes ofD n (i.e. these are exactly the acyclic tournaments ofD n ). We show that various classes of inequalities define facets ofP LO n , e.g. the 3-dicycle inequalities, the simplek-fence inequalities and various Möbius ladder inequalities, and we discuss the use of these inequalities in cutting plane approaches to the triangulation problem of input-output matrices, i.e. the solution of permutation resp. linear ordering problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582010
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Some integer programs arising in the design of main frame computers (1993)
    Springer
    Mathematical methods of operations research 38 (1993), S. 77-100 
    Details
    ISSN: 1432-5217
    Keywords: clustering problem ; design of main frame computers ; graph partitioning problem ; hypergraph partitioning problem ; integer programming ; mathematical modelling ; multiple knapsack problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper we describe and discuss a problem that arises in the (global) design of a main frame computer. The task is to assign certain functional units to a given number of so called multi chip modules or printed circuit boards taking into account many technical constraints and minimizing a complex objective function. We describe the real world problem. A thorough mathematical modelling of all aspects of this problem results in a rather complicated integer program that seems to be hopelessly difficult — at least for the present state of integer programming technology. We introduce several relaxations of the general model, which are alsoNP-hard, but seem to be more easily accessible. The mathematical relations between the relaxations and the exact formulation of the problem are discussed as well.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01416008
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Book
    Book
    Geometric algorithms and combinatorial optimization; 2 (1993)
    Berlin u.a. :Springer,
    Details
    Title: Geometric algorithms and combinatorial optimization; 2
    Author: Grötschel, Martin
    Contributer: Lovász, László , Schrijver, Alexander
    Edition: 2nd corr. ed.
    Publisher: Berlin u.a. :Springer,
    Year of publication: 1993
    Pages: 362 S.
    Series Statement: Algorithms and combinatorics 2
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 7
    Book
    Book
    Geometric algorithms and combinatorial optimization; 2 (1988)
    Berlin u.a. :Springer,
    Details
    Title: Geometric algorithms and combinatorial optimization; 2
    Author: Grötschel, Martin
    Contributer: Lovász, László , Schrijver, Alexander
    Publisher: Berlin u.a. :Springer,
    Year of publication: 1988
    Pages: 362 S.
    Series Statement: Algorithms and combinatorics 2
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 8
    Book
    Book
    Order Picking in an Automatic Warehouse: Solving On-Line Asymmetric TSP's. (Appeared as 〈a href="http://opus.kobv.de/zib/volltexte/1998/352/"〉 SC 98-08〈/a〉) /; Preprint SC 94-18 (1994)
    Berlin :Konrad-Zuse-Zentrum für Informationstechnik,
    Details
    Title: Order Picking in an Automatic Warehouse: Solving On-Line Asymmetric TSP's. (Appeared as 〈a href="http://opus.kobv.de/zib/volltexte/1998/352/"〉 SC 98-08〈/a〉) /; Preprint SC 94-18
    Author: Abdel-Hamid, Atef Abdel-Aziz
    Contributer: Ascheuer, Norbert , Grötschel, Martin
    Publisher: Berlin :Konrad-Zuse-Zentrum für Informationstechnik,
    Year of publication: 1994
    Series Statement: Preprint / Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 94-18
    ISSN: 0933-7911
    Type of Medium: Book
    Language: English
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    ZIB Catalog
    Zuse Institute Berlin get availability status
  • 9
    facet.materialart.
    Unknown
    Discrete Mathematics in Manufacturing. (1992)
    Details
    Publication Date: 2014-02-26
    Description: Manufacturing is a topic that provides rich opportunities for important mathematical contributions to real-world problems. The purpose of this paper is to show, by means of several examples, where and how mathematical problems of a discrete nature arise in manufacturing and to demonstrate the savings and improvements that can be achieved by employing the techniques of combinatorial optimization. The topics covered range from the design phase of a product (e. g.,routing, placement and via minimization in VLSI design), the control of CNC machines (e. g., drilling and plotting), to the management of assembly lines, storage systems and whole factories. We also point out difficulties in the modelling of complex situations and outline the algorithmic methods that are used for the solution of the mathematical problems arising in manufacturing. {\bf Key words:} discrete mathematics , combinatorial optimization, applications to manufacturing.
    Keywords: ddc:000
    Language: English
    Type: reportzib , doc-type:preprint
    Format: application/pdf
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    OPUS
  • 10
    facet.materialart.
    Unknown
    Packing Steiners Trees: A Cutting Plane Algorithm and Computational Results. (1992)
    Details
    Publication Date: 2014-02-26
    Description: In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper SC 92-8 and meant to turn this theory into an algorithmic tool for the solution of practical problems.
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...