A branch-and-bound algorithm for maximizing the sum of several linear ratios

In this paper, we develop a branch-and-bound algorithm for maximizing a sum of p (≥slant2) linear ratios on a polytope. The problem is embedded into a 2p-dimensional space, in which a concave polyhedral function overestimating the optimal value is constructed for the bounding operation. The branchin...

Full description

Saved in:
Bibliographic Details
Published in:Journal of global optimization 2002-01, Vol.22 (1-4), p.155
Main Author: Kuno, Takahito
Format: Article
Language:English
Subjects:
Algorithms
Bond portfolios
Linear programming
Optimization
Ratios
Citations: 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 branch-and-bound algorithm for maximizing a sum of p (≥slant2) linear ratios on a polytope. The problem is embedded into a 2p-dimensional space, in which a concave polyhedral function overestimating the optimal value is constructed for the bounding operation. The branching operation is carried out in a p-dimensional space, in a way similar to the usual rectangular branch-and-bound method. We discuss the convergence properties and report some computational results.
ISSN:0925-5001
1573-2916
DOI:10.1023/A:1013807129844