Management Science · 1969 · 402 citations · 3 references
Natural SciencesComputer ScienceAlgorithmic DesignAlgorithmsOptimizationBranch And BoundCombinatorial OptimizationConstrained OptimizationConvex OptimizationMathematical ProgrammingOptimization TheoryConvex Feasibility ProblemsMathematical Programming ModelsNonconvex OptimizationObjective Function FormulationPartitioning Problems
These problems correspond to successive partitions of the feasible set. The paper proposes an algorithm to minimize separable, possibly nonconvex functions over a closed set with box constraints. The algorithm is a branch‑and‑bound method that iteratively solves convex subproblems and refines partitions using two rules that guarantee convergence under different function assumptions. The method is illustrated with examples and its computational performance is analyzed.
In this paper we present an algorithm for solving mathematical programming problems of the form: Find x = (x 1 ,…, x n ) to minimize ∑φ i (x i ) subject to x ∈ G and l ≤ x ≤ L. Each φ i is assumed to be lower semicontinuous, possibly nonconvex, and G is assumed to be closed. The algorithm is of the branch and bound type and solves a sequence of problems in each of which the objective function is convex. These problems correspond to successive partitions of the feasible set. Two different rules for refining the partitions are considered; these lead to convergence of the algorithm under different requirements on the problem functions. Examples are given, and computational considerations are discussed.
3
Branch-and-Bound Methods: A Survey
Eugene L. Lawler, Derek Wood · Operations Research · 1966 · 2K citations
Optimum Seeking with Branch and Bound
Norman Agin · Management Science · 1966 · 110 citations