The theoretical and empirical rate of convergence for geometric branch-and-bound methods

DOI10.1007/s10898-009-9502-3zbMath1236.90148OpenAlexW2011687300MaRDI QIDQ609566

Daniel Scholz, Anita Schöbel

Publication date: 1 December 2010

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-009-9502-3

zbMATH Keywords

global optimizationapproximation algorithmsfacility location problemsgeometric branch-and-bound methodsbig cube small cube prototype algorithmbounding operationstheoretical and empirical rate of convergence

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (17)

Convergence analysis of Taylor models and McCormick-Taylor models ⋮ Convergence-order analysis of branch-and-bound algorithms for constrained problems ⋮ The cluster problem in constrained global optimization ⋮ A new deterministic global computing algorithm for solving a kind of linear fractional programming ⋮ A global optimization procedure for the location of a median line in the three-dimensional space ⋮ Domain reduction techniques for global NLP and MINLP optimization ⋮ Geometric branch-and-bound methods for constrained global optimization problems ⋮ A maximum trip covering location problem with an alternative mode of transportation on tree networks and segments ⋮ Geometric fit of a point set by generalized circles ⋮ Convergence rate of McCormick relaxations ⋮ Convergence-order analysis for differential-inequalities-based bounds and relaxations of the solutions of ODEs ⋮ Up- and downgrading the Euclidean 1-median problem and knapsack Voronoi diagrams ⋮ Convergence analysis of multivariate McCormick relaxations ⋮ A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables ⋮ Theoretical rate of convergence for interval inclusion functions ⋮ On tightness and anchoring of McCormick and other relaxations ⋮ The cluster problem revisited

Cites Work

• The big cube small cube solution method for multidimensional facility location problems
• Empirical convergence speed of inclusion functions for facility location problems
• Solving a huff-like competitive location and design model for profit maximization in the plane
• Sequential versus simultaneous approach in the location and design of two new facilities using planar Huff-like models
• A general global optimization approach for solving location problems in the plane
• Continuous location problems and big triangle small triangle: Constructing better bounds
• Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and d.c. optimization problems
• GBSSS: The generalized big square small square method for planar single- facility location
• The convergence speed of interval methods for global optimization
• A d.c. optimization method for single facility location problems
• DC programming: overview.
• Finding the optimal solution to the Huff based competitive location model
• Empirical investigation of the convergence speed of inclusion functions in a global otimization context
• The Big Triangle Small Triangle Method for the Solution of Nonconvex Facility Location Problems
• The Minisum and Minimax Location Problems Revisited
• Convex Analysis
• Introduction to global optimization.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The theoretical and empirical rate of convergence for geometric branch-and-bound methods