ZIB-Report
Refine
Year of publication
Document Type
- ZIB-Report (71)
Language
- English (71)
Has Fulltext
- yes (71)
Keywords
- mixed integer programming (10)
- mixed-integer programming (6)
- branch-and-bound (5)
- domain propagation (5)
- linear programming (4)
- parallelization (4)
- branching rule (3)
- constraint integer programming (3)
- maximum-weight connected subgraph (3)
- mixed-integer semidefinite programming (3)
- presolving (3)
- primal heuristics (3)
- MINLP (2)
- Mixed Integer Programming (2)
- Mixed-Integer Programming (2)
- Steiner tree optimization (2)
- Steiner tree problems (2)
- branch-and-cut (2)
- branch-and-price (2)
- column generation framework (2)
- energy system models (2)
- global optimization (2)
- integer programming (2)
- large neighborhood search (2)
- maximum-weight connected subgraph problem (2)
- mixed-integer linear programming (2)
- mixed-integer nonlinear programming (2)
- optimization solver (2)
- preprocessing (2)
- primal heuristic (2)
- prize-collecting Steiner tree problem (2)
- propagation (2)
- strong branching (2)
- Algorithm Analysis (1)
- Branch and bound method (1)
- Branch-and-Bound, Mixed-Integer Programming (1)
- Branch-and-Cut (1)
- Column generation (1)
- DIMACS Challenge (1)
- Energy supply systems (1)
- Gurobi (1)
- Hierarchical approach (1)
- Iterative algorithm (1)
- LP solver (1)
- Linear Programming (1)
- MINLP solver (1)
- MIP (1)
- MIP solver (1)
- MIPLIB (1)
- Markov State Models (1)
- Mixed-Integer Programming solvers (1)
- Mixed-integer linear programming (1)
- NESS (1)
- Newton barrier method (1)
- Node merging (1)
- Non-reversible Markov Processes (1)
- OBBT (1)
- Optimal design (1)
- Optimal operation (1)
- PIPS-SBB, UG, Parallel Branch and Bound (1)
- Parallel processing (1)
- Progress measures (1)
- Racing ParaSCIP (1)
- Restart (1)
- SCIP (1)
- SCIP, Mathematical optimization, Python, Modeling (1)
- SCIP-Jack (1)
- Steiner Tree Problem (1)
- Steiner tree (1)
- Steiner tree problem (1)
- Steiner tree solver (1)
- Steiner tree variants (1)
- Tail assignment (1)
- Ubiquity Generator Framework (1)
- adaptive search behavior (1)
- algorithm selection (1)
- analytic center (1)
- bilinear terms (1)
- bivariate functions (1)
- block structure (1)
- bound tightening (1)
- branch-cut-and-price framework (1)
- conflict analysis (1)
- convex envelope (1)
- correctness, verification, proof, certificate, optimality, infeasibility, mixed-integer linear programming (1)
- deterministic parallelism (1)
- dual degeneracy (1)
- dual proof analysis (1)
- exact rational integer programming (1)
- extremal combinatorics (1)
- extremal combinatorics, extremal set theory, cutting plane, exact integer programming (1)
- fix-and-propagate (1)
- generic column generation (1)
- graph transformation (1)
- high performance computing (1)
- high-performance computing (1)
- interior point algorithm (1)
- interior-point method (1)
- interior-point methods (1)
- linear underestimator (1)
- mixed integer nonlinear programming (1)
- mixed integer programming; primal heuristics; conflict analysis; branch-and-bound (1)
- mixed-integer linear and nonlinear programming (1)
- mixed-integer programming, branch-and-bound, branching rule, strong branching (1)
- mixed-integer programming, large neighborhood search, primal heuristics, domain propagation (1)
- mixed-integer quadratically constrained programs (1)
- modeling (1)
- multi armed bandit (1)
- multi armed bandit problem (1)
- multi-criteria optimization (1)
- no-good learning (1)
- nonconvex (1)
- optimality prediction (1)
- optimality-based bound tightening (1)
- optimization software (1)
- optimization-based bound tightening (1)
- parallel (1)
- parallel branch-and-bound (1)
- parallel computing (1)
- portfolio solvers (1)
- prize-collecting Steiner tree (1)
- projection (1)
- reduction techniques (1)
- reliability branching (1)
- rounding (1)
- search strategy (1)
- separation (1)
- simplex method (1)
- solution learning (1)
- supercomputing (1)
- supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization (1)
- tree-size estimates (1)
- variable selection (1)
Institute
- Mathematical Optimization Methods (71) (remove)
13-47
One of the essential components of a branch-and-bound based mixed-integer linear programming (MIP) solver is the branching rule. Strong branching is a method used by many state-of-the-art branching rules to select the variable to branch on. It precomputes the dual bounds of potential child nodes by solving auxiliary linear programs (LPs) and thereby helps to take good branching decisions that lead to a small search tree. In this paper, we describe how these dual bound predictions can be improved by including domain propagation into strong branching. Domain propagation is a technique usually used at every node of the branch-and-bound tree to tighten the local domains of variables. Computational experiments on standard MIP instances indicate that our improved strong branching method significantly improves the quality of the predictions and causes almost no additional effort. For a full strong branching rule, we are able to obtain substantial reductions of the branch-and-bound tree size as well as the solving time. Moreover, also the state-of-the-art hybrid branching rule can be improved this way.
This paper extends previous work by the author published in the proceedings of the CPAIOR 2013.