Minimizing sums and products of linear fractional functions over a polytope

✍ Scribed by Hiroshi Konno; Hajime Yamashita

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 108 KB
• Volume: 46
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/(sici)1520-6750(199908)46:5<583::aid-nav8>3.0.co;2-5

✦ Synopsis

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes-Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems.