Branching rules revisited

DOI10.1016/J.ORL.2004.04.002zbMath1076.90037DBLPjournals/orl/AchterbergKM05OpenAlexW2060514920WikidataQ29545104 ScholiaQ29545104MaRDI QIDQ1886796

Tobias Achterberg, Thorsten Koch, Alexander Martin

Publication date: 19 November 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.9887

zbMATH Keywords

Variable selectionBranch-and-boundMixed-integer-programmingPseudocost-branchingReliability-branchingStrong-branching

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (only showing first 100 items - show all)

A bi-objective approach to discrete cost-bottleneck location problems ⋮ The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design ⋮ A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen ⋮ Minotaur: a mixed-integer nonlinear optimization toolkit ⋮ Extended reverse-convex programming: an approximate enumeration approach to global optimization ⋮ A branch-and-bound algorithm for a class of mixed integer linear maximum multiplicative programs: a bi-objective optimization approach ⋮ Algorithms and Software for Convex Mixed Integer Nonlinear Programs ⋮ Disjunctive Cuts for Nonconvex MINLP ⋮ Learning generalized strong branching for set covering, set packing, and 0-1 knapsack problems ⋮ Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations ⋮ A branch-price-and-cut method for the vegetable crop rotation scheduling problem with minimal plot sizes ⋮ DASH: dynamic approach for switching heuristics ⋮ Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO ⋮ Branch-and-cut for linear programs with overlapping SOS1 constraints ⋮ Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm ⋮ Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem ⋮ An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen ⋮ Redundancy system design for an aircraft door management system ⋮ Lower bounds and exact algorithms for the quadratic minimum spanning tree problem ⋮ LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison ⋮ Local cuts for mixed-integer programming ⋮ A branch-and-price algorithm for the capacitated facility location problem ⋮ Tighter MIP formulations for the discretised unit commitment problem with MIN-stop ramping constraints ⋮ On the complexity of finding shortest variable disjunction branch-and-bound proofs ⋮ Exact makespan minimization of unrelated parallel machines ⋮ A new branch-and-price algorithm for the traveling tournament problem ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Transferring information across restarts in MIP ⋮ GLOMIQO: global mixed-integer quadratic optimizer ⋮ On learning and branching: a survey ⋮ A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables ⋮ Global optima for the Zhou-Rozvany problem ⋮ Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ Multistage robust discrete optimization via quantified integer programming ⋮ A branch-and-cut algorithm for the Steiner tree problem with delays ⋮ A new exact discrete linear reformulation of the quadratic assignment problem ⋮ A mixed integer linear programming support vector machine for cost-effective group feature selection: branch-cut-and-price approach ⋮ Computational study of a branching algorithm for the maximum \(k\)-cut problem ⋮ A framework for globally optimizing mixed-integer signomial programs ⋮ Parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs ⋮ A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support ⋮ Could we use a million cores to solve an integer program? ⋮ Orbital branching ⋮ Global optimization of mixed-integer nonlinear (polynomial) programming problems: The Bernstein polynomial approach ⋮ A new branch and bound method for a discrete truss topology design problem ⋮ Computational advances in polynomial optimization: RAPOSa, a freely available global solver ⋮ Faster integer-feasibility in mixed-integer linear programs by branching to force change ⋮ Information-theoretic approaches to branching in search ⋮ Branching on nonchimerical fractionalities ⋮ Learning Bayesian network structure: towards the essential graph by integer linear programming tools ⋮ A specialized branch \& bound \& cut for single-allocation ordered median hub location problems ⋮ Bike sharing systems: solving the static rebalancing problem ⋮ An exploratory computational analysis of dual degeneracy in mixed-integer programming ⋮ Branch-and-lift algorithm for deterministic global optimization in nonlinear optimal control ⋮ Importance measures in reliability and mathematical programming ⋮ A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation ⋮ Thinner is not always better: cascade knapsack problems ⋮ An improved Bernstein global optimization algorithm for MINLP problems with application in process industry ⋮ Computational protein design as an optimization problem ⋮ The sport teams grouping problem ⋮ Strong-branching inequalities for convex mixed integer nonlinear programs ⋮ Nurse rostering at a Danish ward ⋮ Further results on an abstract model for branching and its application to mixed integer programming ⋮ Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming ⋮ A branch-and-price algorithm for the scheduling of customer visits in the context of multi-period service territory design ⋮ A novel solution approach with ML-based pseudo-cuts for the flight and maintenance planning problem ⋮ An algorithmic framework for convex mixed integer nonlinear programs ⋮ Exact methods for solving the elementary shortest and longest path problems ⋮ Multiple depot ring star problem: a polyhedral study and an exact algorithm ⋮ Solving the optimum communication spanning tree problem ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports ⋮ ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations ⋮ The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach ⋮ Algorithmic expedients for the \(S\)-labeling problem ⋮ Tolerance-based branch and bound algorithms for the ATSP ⋮ Lower tolerance-based branch and bound algorithms for the ATSP ⋮ Branching on general disjunctions ⋮ Information-based branching schemes for binary linear mixed integer problems ⋮ A computational study of parametric tabu search for 0-1 mixed integer programs ⋮ Faster MIP solutions via new node selection rules ⋮ Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem ⋮ A scalable global optimization algorithm for stochastic nonlinear programs ⋮ How important are branching decisions: fooling MIP solvers ⋮ Exact solution approaches for the multi-period degree constrained minimum spanning tree problem ⋮ Solving linear programs with complementarity constraints using branch-and-cut ⋮ Branch-and-price-and-cut for large-scale multicommodity capacitated fixed-charge network design ⋮ Improving strong branching by domain propagation ⋮ SCIP: solving constraint integer programs ⋮ Branch-and-cut-and-price for the cardinality-constrained multi-cycle problem in kidney exchange ⋮ Efficient semidefinite branch-and-cut for MAP-MRF inference ⋮ On pathological disjunctions and redundant disjunctive conic cuts ⋮ A branching scheme for finding cost-minimal round robin tournaments ⋮ Solving Chance-Constrained Optimization Problems with Stochastic Quadratic Inequalities ⋮ A combinatorial branch-and-bound algorithm for box search ⋮ Sparse regression at scale: branch-and-bound rooted in first-order optimization ⋮ Linearization and parallelization schemes for convex mixed-integer nonlinear optimization ⋮ Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem

Uses Software

• MIPLIB
• CPLEX
• LINDO
• Benchmarks for Optimization Software
• MIPLIB2003
• Decision tree for optimization software
• VBCTOOL

Cites Work

• Unnamed Item
• Unnamed Item
• Computer Codes for Problems of Integer Programming
• Decomposing Matrices into Blocks
• A Computational Study of Search Strategies for Mixed Integer Programming
• Experiments in mixed-integer linear programming
• Investigation of some branch and bound strategies for the solution of mixed integer linear programs

This page was built for publication: Branching rules revisited