A simplicial branch and duality bound algorithm for the sum of convex–convex ratios problem

✍ Scribed by Pei-Ping Shen; Yun-Peng Duan; Yong-Gang Pei

• Publisher: Elsevier Science
• Year: 2009
• Tongue: English
• Weight: 601 KB
• Volume: 223
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/j.cam.2008.01.003

✦ Synopsis

This article presents a simplicial branch and duality bound algorithm for globally solving the sum of convex-convex ratios problem with nonconvex feasible region. To our knowledge, little progress has been made for globally solving this problem so far. The algorithm uses a branch and bound scheme where the Lagrange duality theory is used to obtain the lower bounds. As a result, the lower-bounding subproblems during the algorithm search are all ordinary linear programs that can be solved very efficiently. It has been proved that the algorithm possesses global convergence. Finally, the numerical experiments are given to show the feasibility of the proposed algorithm.