Refine
Year of publication
Document Type
- ZIB-Report (41) (remove)
Has Fulltext
- yes (41)
Is part of the Bibliography
- no (41)
Keywords
- Integer Programming (3)
- Mixed Integer Programming (3)
- Steiner tree (3)
- Branch-and-Bound (2)
- Optimization (2)
- Polyhedral Combinatorics (2)
- Steiner tree packing (2)
- UMTS (2)
- Branching Rules (1)
- Buchungsvalidierung (1)
Institute
For $n\geq 6$ we provide a counterexample to the conjecture that every integral vector of a $n$-dimensional integral polyhedral pointed cone $C$ can be written as a nonnegative integral combination of at most $n$ elements of the Hilbert basis of $C$. In fact, we show that in general at least $\lfloor 7/6 \cdot n \rfloor$ elements of the Hilbert basis are needed.
In this paper we describe a cutting plane based algorithm for the multiple knapsack problem. We use our algorithm to solve some practical problem instances arising in the layout of electronic circuits and in the design of main frame computers, and we report on our computational experience. This includes a discussion and evaluation of separation algorithms, an LP-based primal heuristic and some implementation details. The paper is based on the polyhedral theory for the multiple knapsack polytope developed in our companion paper SC 93-04 and meant to turn this theory into an algorithmic tool for the solution of practical problems.
Mixed integer programs ($MIPs$) are commonly solved with branch and bound algorithms based on linear programming. The success and the speed of the algorithm strongly depends on the strategy used to select the branching variables. Today's state-of-the-art strategy is called \emph{pseudocost branching} and uses information of previous branchings to determine the current branching. We propose a modification of \emph{pseudocost branching} which we call \emph{history branching}. This strategy has been implemented in $SIP$, a state-of-the-art $MIP$ solver. We give computational results that show the superiority of the new strategy.
Branching rules revisited
(2004)
Mixed integer programs are commonly solved with linear programming based branch-and-bound algorithms. The success of the algorithm strongly depends on the strategy used to select the variable to branch on. We present a new generalization called {\sl reliability branching} of today's state-of-the-art {\sl strong branching} and {\sl pseudocost branching} strategies for linear programming based branch-and-bound algorithms. After reviewing commonly used branching strategies and performing extensive computational studies we compare different parameter settings and show the superiority of our proposed newstrategy.
This paper deals with a family of conjunctive inequalities. Such inequalities are needed to describe the polyhedron associated with all the integer points that satisfy several knapsack constraints simultaneously. Here we demonstrate the strength and potential of conjunctive inequalities in connection with lifting from a computational point of view.
This survey presents cutting planes that are useful or potentially useful in solving mixed integer programs. Valid inequalities for i) general integer programs, ii) problems with local structure such as knapsack constraints, and iii) problems with 0-1 coefficient matrices, such as set packing, are examined in turn. Finally the use of valid inequalities for classes of problems with structure, such as network design, is explored.
In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix $A$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.
In this paper we consider the multiple knapsack problem which is defined as follows: given a set $N$ of items with weights $f_i$, $i \in N$, a set $M$ of knapsacks with capacities $F_k$, $k \in M$, and a profit function $c_{ik}, i \in N, k \in M$; find an assignment of a subset of the set of items to the set of knapsacks that yields maximum profit (or minimum cost). With every instance of this problem we associate a polyhedron whose vertices are in one to one correspondence to the feasible solutions of the instance. This polytope is the subject of our investigations. In particular, we present several new classes of inequalities and work out necessary and sufficient conditions under which the corresponding inequality defines a facet. Some of these conditions involve only properties of certain knapsack constraints, and hence, apply to the generalized assignment polytope as well. The results presented here serve as the theoretical basis for solving practical problems. The algorithmic side of our study, i.e., separation algorithms, implementation details and computational experience with a branch and cut algorithm are discussed in the companion paper SC 93-07.
We investigate the problem of partitioning the nodes of a graph under capacity restriction on the sum of the node weights in each subset of the partition. The objective is to minimize the sum of the costs of the edges between the subsets of the partition. This problem has a variety of applications, for instance in the design of electronic circuits and devices. We present alternative integer programming formulations for this problem and discuss the links between these formulations. Having chosen to work in the space of edges of the multicut, we investigate the convex hull of incidence vectors of feasible multicuts. In particular, several classes of inequalities are introduced, and their strength and robustness are analyzed as various problem parameters change.