Library

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
    Springer
    Mathematical programming 16 (1979), S. 265-280 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 8 (1975), S. 378-381 
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours. In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 5 (1973), S. 199-215 
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we address ourselves to identifying facets of the set packing polyhedron, i.e., of the convex hull of integer solutions to the set covering problem with equality constraints and/or constraints of the form “⩽”. This is done by using the equivalent node-packing problem derived from the intersection graph associated with the problem under consideration. First, we show that the cliques of the intersection graph provide a first set of facets for the polyhedron in question. Second, it is shown that the cycles without chords of odd length of the intersection graph give rise to a further set of facets. A rather strong geometric property of this set of facets is exhibited.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 7 (1974), S. 32-45 
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A class of polytopes is defined which includes the polytopes related to the assignment problem, the edge-matching problem on complete graphs, the multi-dimensional assignment problem, and many other set partitioning problems. Modifying some results due to Balas and Padberg, we give a constructive proof that the diameter of these polytopes is less than or equal to two. This result generalizes a result obtained by Balinski and Rusakoff in connection with the assignment problem. Furthermore, it is shown that the polytope associated with the travelling salesman problem has a diameter less than or equal to two. A weaker form of the Hirsch conjecture is also shown to be true for this polytope.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 16 (1979), S. 281-302 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 18 (1980), S. 94-99 
    ISSN: 1436-4646
    Keywords: Integer Programming ; Integral Polyhedra ; Linear Inequalities ; Facets
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A new class of facets for knapsack polytopes is obtained. This class of inequalities is shown to define a polytope with zero–one vertices only. A combinatorial inequality is obtained from Fulkerson's max—max inequality.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 6 (1974), S. 180-196 
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A zero–one matrix is called perfect if the polytope of the associated set packing problem has integral vertices only. By this definition, all totally unimodular zero–one matrices are perfect. In this paper we give a characterization of perfect zero–one matrices in terms offorbidden submatrices. Perfect zero–one matrices are closely related to perfect graphs and constitute a generalization of balanced matrices as introduced by C. Berge. Furthermore, the results obtained here bear on an unsolved problem in graph theory, the strong perfect graph conjecture, also due to C. Berge.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 8
    Title: Linear optimization and extensions : problems and solutions
    Author: Alevras, Dimitris
    Contributer: Padberg, Manfred W.
    Publisher: Berlin u.a. :Springer,
    Year of publication: 2001
    Pages: 449 S.
    Series Statement: Universitext
    Type of Medium: Book
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 9
    Title: Combinatorial optimization /; 12
    Contributer: Padberg, Manfred W.
    Year of publication: 1980
    Pages: VII, 221 S.
    Series Statement: Mathematical programming 12
    ISBN: 0-444-854-894
    Type of Medium: Book
    Language: English
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...