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 81 (1998), S. 229-256 
    ISSN: 1436-4646
    Keywords: Branch-and-cut algorithm ; Clustering ; Compiler design ; Equipartitioning ; Finite element method ; Graph partitioning ; Layout of electronic circuits ; Separation heuristics
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider the problem ofk-partitioning the nodes of a graph with capacity restrictions on the sum of the node weights in each subset of the partition, and the objective of minimizing the sum of the costs of the edges between the subsets of the partition. Based on a study of valid inequalities, we present a variety of separation heuristics for cycle, cycle with ears, knapsack tree and path-block cycle inequalities among others. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including variables for the edges with nonzero costs and node partition variables. Results are presented for three classes of problems: equipartitioning problems arising in finite element methods and partitioning problems associated with electronic circuit layout and compiler design. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    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 63 (1994), S. 257-279 
    ISSN: 1436-4646
    Keywords: Quadratic 0/1 optimization ; computational complexity ; VLSI-design
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The placement problem in the layout design of electronic circuits consists of finding a nonoverlapping assignment of rectangular cells to positions on the chip so that 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 above NP-hardness and the existence ofε-approximative algorithms for the involved optimization problems. A graph theoretic 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.
    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
    Applicable algebra in engineering, communication and computing 8 (1997), S. 241-256 
    ISSN: 1432-0622
    Keywords: Keywords: Integer programming ; Toric ideal ; Truncated Gröbner bases ; Truncated Buchberger algorithm ; Multivariate grading.
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics , Technology
    Notes: Abstract.  The toric ideal I A of a matrix A=(a 1, . . . ,  a n )∈ℤd × n is the kernel of the monoid algebra map π^ A  : k[x 1, . . . ,  x n ]→k[t ±1 1, . . . ,  t ±1 d ], defined as x j ?t aj . It was shown in [4] that the reduced Gröbner basis of I A , with respect to the weight vector c, can be used to solve all integer programs minimize {cx : Ax=b, x∈ℕ n }, denoted IP A,b,c,= , as b varies. In this paper we describe the construction of a truncated Gröbner basis of I A with respect to c, that solves IP A,b,c,= for a fixed b. This is achieved by establishing the homogeneity of I A with respect to a multivariate grading induced by A. Depending on b, the truncated Gröbner basis may be considerably smaller than the entire Gröbner basis of I A with respect to c. For programs of the form maximize{cx : Ax≦b, x≦u, x∈ℕ  n } in which all data are non-negative, this algebraic method gives rise to a combinatorial algorithm presented in [17].
    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
    Journal of combinatorial optimization 4 (2000), S. 197-215 
    ISSN: 1573-2886
    Keywords: semidefinite programming ; quadratic knapsack problem ; cutting planes ; 0/1 polytopes ; relaxations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In order to gain insight into the quality of semidefinite relaxations of constrained quadratic 0/1 programming problems we study the quadratic knapsack problem. We investigate several basic semidefinite relaxations of this problem and compare their strength in theory and in practice. Various possibilities to improve these basic relaxations by cutting planes are discussed. The cutting planes either arise from quadratic representations of linear inequalities or from linear inequalities in the quadratic model. In particular, a large family of combinatorial cuts is introduced for the linear formulation of the knapsack problem in quadratic space. Computational results on a small class of practical problems illustrate the quality of these relaxations and cutting planes.
    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...