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
{\def\N{{\mbox{{\rm I\kern-0.22emN}}}}In this paper we introduce a multivariate grading of the toric ideal associated with the integer program $min \{ cx : Ax = b, x \in \N^n \}$, and a truncated Buchberger algorithm to solve the program. In the case of $max \{ cx : Ax \leq b, x \leq u, x \in \N^n \}$ in which all data are non-negative, this algebraic method gives rise to a combinatorial algorithm presented in UWZ94}.
In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.
In this paper we consider the problem of $k$-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 so-called cycle, cycle with ears, knapsack tree and path-block-cycle inequalities. The separation heuristics, plus primal heuristics, have been implemented in a branch-and-cut routine using a formulation including the edges with nonzero costs and node 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.
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.
This paper deals with the study of test sets of the knapsack problem and simultaneous diophantine approximation. The Graver test set of the knapsack problem can be derived from minimal integral solutions of linear diophantine equations. We present best possible inequalities that must be satisfied by all minimal integral solutions of a linear diophantine equation and prove that for the corresponding cone the integer analogue of Caratheodory's theorem applies when the numbers are divisible. We 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''. A recursive algorithm for computing this Hilbert basis is discussed. We also outline an algorithm for determining a Hilbert basis of a family of cones associated with the knapsack problem.
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.
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 also $NP$-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.