Branching rules revisited

DOI10.1016/j.orl.2004.04.002zbMath1076.90037OpenAlexW2060514920WikidataQ29545104 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 selection Branch-and-bound Mixed-integer-programming Pseudocost-branching Reliability-branching Strong-branching

Mathematics Subject Classification ID

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

Related Items

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, A Penalty Branch-and-Bound Method for Mixed Binary Linear Complementarity Problems, Optimization in Designing Complex Communication Networks, Multivariable Branching: A 0-1 Knapsack Problem Case Study, A Branch-and-Bound Algorithm for Building Optimal Data Gathering Tree in Wireless Sensor Networks, Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded, Exact Branch-Price-and-Cut for a Hospital Therapist Scheduling Problem with Flexible Service Locations and Time-Dependent Location Capacity, Decomposition Branching for Mixed Integer Programming, Branch-and-bound solves random binary IPs in poly\((n)\)-time, A study of lattice reformulations for integer programming, A nearly optimal randomized algorithm for explorable heap selection, Compressing branch-and-bound trees, Computing with Multi-row Gomory Cuts, Improving energy aware nanosatellite task scheduling by a branch-cut-and-price algorithm, Integer programming models for round Robin tournaments, Benders-type branch-and-cut algorithms for capacitated facility location with single-sourcing, A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints, A theoretical and computational analysis of full strong-branching, Mixed-integer programming techniques for the minimum sum-of-squares clustering problem, Mitigating anomalies in parallel branch-and-bound based algorithms for mixed-integer nonlinear optimization, A branch and bound algorithm for robust binary optimization with budget uncertainty, Tailored presolve techniques in branch‐and‐bound method for fast mixed‐integer optimal control applications, Polyhedral approaches to learning Bayesian networks, Constraint Integer Programming: A New Approach to Integrate CP and MIP, Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets, Optimization Bounds from the Branching Dual, Spectral Relaxations and Branching Strategies for Global Optimization of Mixed-Integer Quadratic Programs, From feasibility to improvement to proof: three phases of solving mixed-integer programs, Exploiting integrality in the global optimization of mixed-integer nonlinear programming problems with BARON, A framework for solving mixed-integer semidefinite programs, A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem, Measuring the Impact of Branching Rules for Mixed-Integer Programming, Unnamed Item, A computational status update for exact rational mixed integer programming, A computational status update for exact rational mixed integer programming, A Branch-Price-and-Cut Procedure for the Discrete Ordered Median Problem, One-dimensional relaxations and LP bounds for orthogonal packing, Conflict-Driven Heuristics for Mixed Integer Programming, The vehicle routing problem with time windows and temporal dependencies, Exact Solution of Two Location Problems via Branch-and-Bound, A Bilevel Approach for Identifying the Worst Contingencies for Nonconvex Alternating Current Power Systems, An Active-Set Method for Quadratic Programming Based On Sequential Hot-Starts

Uses Software

Cites Work