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
    Discrete & computational geometry 29 (NaN), S. 485-504 
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. A beautiful result of Brocker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every d -dimensional polyhedron admits a representation as the set of solutions of at most d(d+1)/2 polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the two- and three-dimensional case we get the expected number d(d+1)/2 .
    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 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 ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 33 (1985), S. 28-42 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 51 (1991), S. 141-202 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    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 ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Computing 39 (1987), S. 327-344 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 33 (1985), S. 43-60 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 14 (1978), S. 373-377 
    ISSN: 1436-4646
    Keywords: Nonlinear Programming ; Algorithms ; Continuous Unbounded Algorithms ; Global Convergence of Algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 9
    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 ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 76 (1998), S. 1-20 
    ISSN: 1572-9338
    Keywords: telecommunication network design, survivable networks, network capacity planning, cutting plane algorithm, heuristics, routing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Given a communication demand between each pair of nodes of a network, we consider the problem of deciding what capacity to install on each edge of the network in order to minimize the building cost of the network and to satisfy a given demand between each pair of nodes. The feasible capacities that can be leased from a network provider are of a particular kind in our case. There are a few so-called basic capacities having the property that every basic capacity is an integral multiple of every smaller basic capacity. An edge can be equipped with a capacity only if it is an integer combination of the basic capacities. In addition, we treat several restrictions on the routings of the demands (length restriction, diversification) and failures of single nodes or single edges. We formulate the problem as a mixed integer linear programming problem and develop a cutting plane algorithm as well as several heuristics to solve it. We report on computational results for real-world data.
    Type of Medium: Electronic Resource
    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...