A Simplicial Branch-and-Bound Algorithm Conscious of Special Structures in Concave Minimization Problems

摘要

In this paper, we develop a simplicial branch-and-bound algorithm for generatingglobally optimal solutions to concave minimization problems with low ranknonconvex structures. We propose to remove all additional constraints imposedon the usual linear programming relaxed problem. Therefore, in each boundingoperation, we solve a linear programming problem whose constraints are exactlythe same as the target problem. Although the lower bound worsens as a naturalconsequence, we o set this weakness by using an inexpensive bound tighteningprocedure based on Lagrangian relaxation. After giving a proof of the convergence,we report a numerical comparison with existing algorithms.