Refine
Year of publication
Document Type
- Article (49)
- ZIB-Report (41)
- In Proceedings (22)
- Book chapter (6)
- Book (2)
- Doctoral Thesis (1)
- Habilitation (1)
- In Collection (1)
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)
- cutting planes (2)
- Branching Rules (1)
Institute
- Mathematical Optimization (57)
- ZIB Allgemein (36)
- Visual Data Analysis (6)
- Visual and Data-centric Computing (6)
- Mathematical Optimization Methods (4)
- Distributed Algorithms and Supercomputing (3)
- Mathematical Algorithmic Intelligence (3)
- Modeling and Simulation of Complex Processes (3)
- Applied Algorithmic Intelligence Methods (2)
- Numerical Mathematics (2)
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.
Algorithmenbasierte Produktentwicklung für integrale Blechbauweisen höherer Verzweigungsordnung
(2007)
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.