# Library

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
• 1
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
Others were also interested in ...
• 2
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
Others were also interested in ...
• 3
Electronic Resource
Springer
Computational optimization and applications 17 (2000), S. 61-84
ISSN: 1573-2894
Keywords: asymmetric traveling salesman problem ; precedence constraints ; branch&cut
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science
Notes: Abstract In this article we consider a variant of the classical asymmetric traveling salesman problem (ATSP), namely the ATSP in which precedence constraints require that certain nodes must precede certain other nodes in any feasible directed tour. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing (Timlin, Master's Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1989), sequencing in flexible manufacturing (Ascheuer et al., Integer Programming and Combinatorial Optimization, University of Waterloo, Waterloo, 1990, pp. 19–28; Idem., SIAM Journal on Optimization, vol. 3, pp. 25–42, 1993), to stacker crane routing in an automatic storage system (Ascheuer, Ph.D. Thesis, Tech. Univ. Berlin, 1995). We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&cut-algorithm and give computational results on real-world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances with more than 200 nodes can be solved to optimality within a few minutes of CPU-time. As a side product we obtain a branch&cut-algorithm for the ATSP. All instances in TSPLIB can be solved to optimality in a reasonable amount of computation time.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 4
Electronic Resource
Springer
Mathematical methods of operations research 40 (1994), S. 183-217
ISSN: 1432-5217
Source: Springer Online Journal Archives 1860-2000
Topics: Mathematics , Economics
Notes: Abstract The determination of true optimum solutions of combinatorial optimization problems is seldomly required in practical applications. The majority of users of optimization software would be satisfied with solutions of guaranteed quality in the sense that it can be proven that the given solution is at most a few percent off an optimum solution. This paper presents a general framework for practical problem solving with emphasis on this aspect. A detailed discussion along with a report about extensive computational experiments is given for the traveling salesman problem.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 5
Book
Berlin, [u. a.] :Springer,
Title: Facets of combinatorial optimization /
Publisher: Berlin, [u. a.] :Springer,
Year of publication: 2013
Pages: XVII, 506 p. 245 illus., 162 illus. in color
ISBN: 978-3-642-38189-8 , 978-3-642-38188-1
Type of Medium: Book
Language: English
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 6
Title: ¬The¬ linear ordering problem: algorithms and applications; Vol. 8
Author: Reinelt, Gerhard
Publisher: Berlin :Heldermann,
Year of publication: 1985
Pages: 158 S.
Series Statement: Research and exposition in mathematics Vol. 8
Type of Medium: Book
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 7
Title: ¬The¬ traveling salesman: computational solutions for TSP applications; 840
Author: Reinelt, Gerhard
Publisher: Berlin u.a. :Springer,
Year of publication: 1994
Pages: 223 S.
Series Statement: Lecture notes in computer science 840
Type of Medium: Book
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 8
Book
Title: ¬A¬ Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints (rev.Vers.JAN99) /; Preprint SC 97-70
Author: Ascheuer, Norbert
Year of publication: 1997
Pages: 28 S.
Series Statement: Preprint / Konrad-Zuse-Zentrum für Informationstechnik Berlin Preprint SC 97-70
ISSN: 0933-7911
Type of Medium: Book
Language: English
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 9
Unknown
Publication Date: 2020-10-05
Description: The placement in the layout design of electronic circiuts consists of finding a non- overlapping assignment of rectangular cells to positions on the chip so what wireability is guaranteed and certain technical constraints are met.This problem can be modelled as a quadratic 0/1- program subject to linear constraints. We will present a decomposition approach to the placement problem and give results about $NP$-hardness and the existence of $\varepsilon$-approximative algorithms for the involved optimization problems. A graphtheoretic formulation of these problems will enable us to develop approximative algorithms. Finally we will present details of the implementation of our approach and compare it to industrial state of the art placement routines. {\bf Keywords:} Quadratic 0/1 optimization, Computational Complexity, VLSI-Design.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 10
Unknown
Publication Date: 2020-08-05
Description: In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&-cut algorithm and give computational results on real world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
Close ⊗