Refine
Year of publication
Document Type
- ZIB-Report (36)
- Article (12)
- In Proceedings (1)
- Doctoral Thesis (1)
Is part of the Bibliography
- no (50) (remove)
Keywords
- Steiner tree (2)
- Cutting Planes (1)
- Facets (1)
- Hilbert basis (1)
- Integer Programming (1)
- Integral pointed cones (1)
- Mixed Integer Programming (1)
- Packing (1)
- Polyhedral Combinatorics (1)
- Separation Algorithm (1)
Institute
This paper presents some connections between test sets and valid inequalities of integer programs. The reason for establishing such relationships is the hope that information (even partial) on one of these objects can be used to get information on the other and vice versa. We approach this study from two directions: On the one hand we examine the geometric process by which the secondary polytope associated with a matrix $A$ transforms to the state polytope as we pass from linear programs that have $A$ as coefficient matrix to the associated integer programs. The second direction establishes the notion of classes of augmentation vectors parallel to the well known concept of classes of facet defining inequalities for integer programs. We show how certain inequalities for integer programs can be derived from test sets for these programs.
Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming: extended abstract
(1995)
We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.
This paper investigates properties of the minimal integral solutions of a linear diophantine equation. We present best possible inequalities that must be satisfied by these elements which improves on former results. We also show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. Relations between these cones are applied to the knapsack problem.
This paper is about {\em set packing relaxations\/} of combinatorial optimization problems associated with acyclic digraphs and linear orderings, cuts and multicuts, and vertex packings themselves. Families of inequalities that are valid for such a relaxation as well as the associated separation routines carry over to the problems under investigation.
We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.
For a polyhedral cone $C=$ pos $\{a^1,\dots,a^m\}\subset R^d$, $a^i\in Z^d$, a subset of integral vectors $H(C)\subset C \cap Z^d$ is called a Hilbert basis of $C$ iff (i) each element of $C\cap Z^d$ can be written as a non-negative integer combination of elements of $H(C)$ and (ii) $H(C)$ has minimal cardinality with respect to all subsets of $C \cap Z^d$ for which (i) holds. We show that various problems related to Hilbert bases are hard in terms of computational complexity. However, if the dimension and the number of elements of the Hilbert basis are fixed, a Hilbert basis can always be computed in polynomial time. Furthermore we introduce a (practical) algorithm for computing the Hilbert basis of a polyhedral cone. The finiteness of this method is deduced from a result about the height of a Hilbert basis which, in particular, improves on former estimates.
This paper investigates {\em relations\/} among combinatorial optimization problems. To establish such relations we introduce a transformation technique \mbox{---{\em aggregation}---} that allows to relax an integer program by means of another integer program. We prove that various families of prominent inequalities for the acyclic subdigraph problem, the multiple knapsack problem, the max cut, graph, and the clique partitioning problem, the set covering problem, and the set packing problem can be derived and separated in polynomial time in this way. Our technique is algorithmic. It has been implemented and used in a set partitioning code.
This paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvatal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported.
Die vorliegende Arbeit beschäftigt sich mit dem Plazierungsproblem, welches beim Entwurf elektronischer Schaltungen auftritt. Das Plazierungsproblem modellieren wir als ein quadratisches 0/1 Optimierungsproblem unter linearen Nebenbedingungen und untersuchen das Modell komplexitätstheoretisch. Der zweite Aspekt der Arbeit bezieht sich auf die Lösung praktischer Problembeispiele im sogenannten Sea of cells"-Entwurfsstil. Zur Lösung dieser Beispiele wurde ein Prototyp implementiert und mit state of the art"-Plazierungsverfahren verglichen. Schlie\ss lich werden wir uns mit dem Clusteringproblem, das eine Variante des Mehrfachschnitt-Problems darstellt, beschäftigen. Dabei steht einerseits im Vordergrund, wie diese Probleme heuristisch gelöst werden können und wie die Integration des Ansatzes in das Plazierungsprogramm erfolgt. Andererseits soll das Clusteringproblem polyedrisch untersucht werden.