Theoretical comparisons of search strategies in branch-and-bound algorithms

DOI10.1007/BF00998631zbMath0406.68031OpenAlexW2081821176MaRDI QIDQ4192964

Toshihide Ibaraki

Publication date: 1976

Published in: International Journal of Computer & Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00998631

zbMATH Keywords

Mathematical ProgrammingComputational ComplexityBranch-And-Bound AlgorithmHeuristic Search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Mathematical programming (90C99) Algorithms in computer science (68W99)

Related Items (19)

A new node selection strategy in the branch-and-bound procedure ⋮ A note on anomalies in parallel branch-and-bound algorithms with one-to- one bounding functions ⋮ Performances of parallel branch and bound algorithms with best-first search ⋮ An effective structured approach to finding optimal partitions of networks ⋮ Pareto optimality and robustness in bi-blending problems ⋮ Infeasibility spheres for finding robust solutions of blending problems with quadratic constraints ⋮ The semi-continuous quadratic mixture design problem: description and branch-and-bound approach ⋮ Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning ⋮ Discrete optimization methods for multiprocessor computer systems ⋮ Using branch-and-bound algorithms to obtain suboptimal solutions ⋮ The stochastic transportation problem with single sourcing ⋮ Some new perspectives for solving 0--1 integer programming problems using balas method ⋮ Depth-m search in branch-and-bound algorithms ⋮ On a branch-and-bound approach for a Huff-like Stackelberg location problem ⋮ Optimization of template-driven scheduling mechanisms: Regularity measures and computational techniques ⋮ An extremal problem on random trees ⋮ Strategies of node selection in search procedures for solving combinatorial optimization problems: A survey and a general formalization ⋮ Probability modeling of branch-and-bound method ⋮ An upper bound for the speedup of parallel best-bound branch-and-bound algorithms

Cites Work

• Unnamed Item
• Practical Solution of Large Mixed Integer Programming Problems with Umpire
• Algorithms for Scheduling Independent Tasks
• Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation Problems
• Backtrack Programming
• Branch-and-Bound Methods: A Survey
• Discrete Programming by the Filter Method
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• Letter to the Editor—A Note on the Branch-and-Bound Principle
• Integer Programming by Implicit Enumeration and Balas’ Method
• Branch-and-Bound Methods: General Formulation and Properties
• Experiments in mixed-integer linear programming

This page was built for publication: Theoretical comparisons of search strategies in branch-and-bound algorithms