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 generating globally optimal solutions to concave minimization problems with low rank nonconvex structures. We propose to remove all additional constraints imposed on the usual linear programming relaxed problem. Therefore, in each...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2008-03, Vol.39 (2), p.219-238
Main Authors: Kuno, Takahito, Nagai, Hidetoshi
Format: Article
Language:English
Subjects:
Algorithms
Convex and Discrete Geometry
Lagrange multiplier
Linear programming
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Optimization
Statistics
Studies
Variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we develop a simplicial branch-and-bound algorithm for generating globally optimal solutions to concave minimization problems with low rank nonconvex structures. We propose to remove all additional constraints imposed on the usual linear programming relaxed problem. Therefore, in each bounding operation, we solve a linear programming problem whose constraints are exactly the same as the target problem. Although the lower bound worsens as a natural consequence, we offset this weakness by using an inexpensive bound tightening procedure based on Lagrangian relaxation. After giving a proof of the convergence, we report a numerical comparison with existing algorithms.
ISSN:0926-6003
1573-2894
DOI:10.1007/s10589-007-9068-2