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 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
  • 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
    Partial linear characterizations of the asymmetric travelling salesman polytope (1975)
    Springer
    Mathematical programming 8 (1975), S. 378-381 
    Details
    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
    URL: http://dx.doi.org/10.1007/BF01580454
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    A property of continuous unbounded algorithms (1978)
    Springer
    Mathematical programming 14 (1978), S. 373-377 
    Details
    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
    URL: http://dx.doi.org/10.1007/BF01588977
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    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
  • 6
    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
  • 7
    Book
    Book
    Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme; 36 (1977)
    Frankfurt/Main :Hain,
    Details
    Title: Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme; 36
    Author: Grötschel, Martin
    Publisher: Frankfurt/Main :Hain,
    Year of publication: 1977
    Pages: 305 S.
    Series Statement: Mathematical Systems in Economics 36
    Dissertation note: Zugl.: Bonn, Univ., Diss., 1977
    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
    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
  • 9
    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
  • 10
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...