Solving the sum-of-ratios problem by a stochastic search algorithm

Wei Ying Wu, Ruey-Lin Sheu, Ş Ilker Birbil

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

In spite of the recent progress in fractional programming, the sum-of-ratios problem remains untoward. Freund and Jarre proved that this is an NP-complete problem. Most methods overcome the difficulty using the deterministic type of algorithms, particularly, the branch-and-bound method. In this paper, we propose a new approach by applying the stochastic search algorithm introduced by Birbil, Fang and Sheu to a transformed image space. The algorithm then computes and moves sample particles in the q - 1 dimensional image space according to randomly controlled interacting electromagnetic forces. Numerical experiments on problems up to sum of eight linear ratios with a thousand variables are reported. The results also show that solving the sum-of-ratios problem in the image space as proposed is, in general, preferable to solving it directly in the primal domain.

Original languageEnglish
Pages (from-to)91-109
Number of pages19
JournalJournal of Global Optimization
Volume42
Issue number1
DOIs
Publication statusPublished - 2008 Sep 1

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Solving the sum-of-ratios problem by a stochastic search algorithm'. Together they form a unique fingerprint.

Cite this