Probabilistic subproblem selection in branch-and-bound algorithms

DOI10.1016/J.CAM.2004.10.019MaRDI QIDQ557739zbMATH OpenOpenAlexFDO

Authors Mirjam Dür, Volker Stix

Publication date 30 June 2005

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cam.2004.10.019

zbMATH Keywords

ConvergenceNonconvex programmingnumerical experimentsSubset selection in branch-and-bound algorithms

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Review text

The authors propose to include a probabilistic element into the selection process of the subproblem in branch-and-bound algorithms. The proposed method is a generalization of the best-bound selection rule. Also, they give conditions which guarantee that the branch-and-bound algorithm converges with probability \(1\), using the probabilistic selection rule proposed by the authors. Numerical experiments on the maximum clique problem are given.

Recommendations

• scientific article; zbMATH DE number 3892936
• Target-oriented branch and bound method for global optimization
• On the selection of subdivision directions in interval branch-and-bound methods for global optimization
• Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds
• A new node selection strategy in the branch-and-bound procedure

Cites work

• A branch and bound method for stochastic global optimization
• A branch-and-bound algorithm for the location of facilities causing atmospheric pollution
• A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method
• A Nested Decomposition Approach to a Three-Stage, Two-Dimensional Cutting-Stock Problem
• An Algorithm for the Traveling Salesman Problem
• An optimization model for the simultaneous operational flight and pilot scheduling problem
• Dual bounding procedures lead to convergent branch-and-bound algorithms
• Genetic engineering via negative fitness: Evolutionary dynamics for global optimization
• scientific article; zbMATH DE number 914364 (Why is no real title available?)
• scientific article; zbMATH DE number 956839 (Why is no real title available?)
• New subinterval selection criteria for interval global optimization
• Probability theory. Translated from the German by Robert B. Burckel
• Solving sum-of-ratios fractional programs using efficient points
• Target-oriented branch and bound method for global optimization
• Theoretical justification of a heuristic subbox selection criterion for interval global optimization

Cited in

(3)

• Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning
• P-algorithm based on a simplicial statistical model of multimodal functions
• Investigation of selection strategies in branch and bound algorithm with simplicial partitions and combination of Lipschitz bounds

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Probabilistic subproblem selection in branch-and-bound algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557739)