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
Filter
  • Facets of Polyhedra  (2)
  • Travelling Salesman Problem  (2)
  • polyhedral combinatorics  (2)
  • Feedback Arc Set Problem  (1)
Source
Material
Years
Keywords
  • 1
    Electronic Resource
    Electronic Resource
    On the symmetric travelling salesman problem II: Lifting theorems and facets (1979)
    Springer
    Mathematical programming 16 (1979), S. 281-302 
    Details
    ISSN: 1436-4646
    Keywords: Linear Inequalities ; Convex Polytopes ; Facets ; Lifting Theorems ; Travelling Salesman Problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Four lifting theorems are derived for the symmetric travelling salesman polytope. They provide constructions and state conditions under which a linear inequality which defines a facet of then-city travelling salesman polytope retains its facetial property for the (n + m)-city travelling salesman polytope, wherem ≥ 1 is an arbitrary integer. In particular, they permit a proof that all subtour-elimination as well as comb inequalities define facets of the convex hull of tours of then-city travelling salesman problem, wheren is an arbitrary integer.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582117
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On the symmetric travelling salesman problem I: Inequalities (1979)
    Springer
    Mathematical programming 16 (1979), S. 265-280 
    Details
    ISSN: 1436-4646
    Keywords: Linear Inequalities ; Convex Polytopes ; Facets ; Travelling Salesman Problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We investigate several classes of inequalities for the symmetric travelling salesman problem with respect to their facet-defining properties for the associated polytope. A new class of inequalities called comb inequalities is derived and their number shown to grow much faster with the number of cities than the exponentially growing number of subtour-elimination constraints. The dimension of the travelling salesman polytope is calculated and several inequalities are shown to define facets of the polytope. In part II (“On the travelling salesman problem II: Lifting theorems and facets”) we prove that all subtour-elimination and all comb inequalities define facets of the symmetric travelling salesman polytope.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582116
    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
    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
  • 5
    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
  • 6
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...