
Vietnam Journal of Mathematics 35:4(2007)
333414

Comparison of Search Strategies of Branch
and Bound Algorithm for Concave Minimization Problems Under Linear
Constraints

Hiroshi Konno,
Kazuo Izumi, and Rei Yamamoto

Abstract. Solving large scale concave
minimization problems is attracting more attention in recent years. A
number of large scale practical problems have been solved to optimality by
a branch and bound algorithm based on hyperrectangular subdivision/linear
underestimating function and by a 01 mixed linear integer programming
algorithm.We will report the result of a systematic comparison of search
strategies of branch and bound algorithm. Also,we compare them with 01
integer programming approach.We will show that a depth first search
strategy is useful for solving a very large scale meanabsolute deviation
portfolio optimization problem under concave transaction cost.


Keywords: Global optimization, concave
minimization, branch and bound algorithm, mixed 01 programming, portfolio
optimization, meanabsolute deviation model.


Established
by Vietnam Academy of Science and Technology & Vietnam Mathematical
Society
Published
by Springer since January 2013

