Refine
Year of publication
Document Type
- ZIB-Report (14)
- Article (11)
- Book chapter (4)
- In Proceedings (4)
- In Collection (1)
Is part of the Bibliography
- no (34)
Keywords
- Branch-and-Bound (2)
- Mixed Integer Programming (2)
- Optimization (2)
- UMTS (2)
- Branching Rules (1)
- Buchungsvalidierung (1)
- Entry-Exit Model (1)
- Gas Market Liberalization (1)
- Gas Network Access Regulation (1)
- Gasnetzplanung (1)
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.
Branching Rules Revisited
(2005)
Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.