A combined algorithm for fractional programming

DOI10.1023/A:1012998904482MaRDI QIDQ5959292zbMATH OpenOpenAlexFDO

Authors Jianming Shi

Publication date 26 March 2002

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1012998904482

zbMATH Keywords

band-and-bound algorithmcutting planed.c. functions. global optimizationfractional programming

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Fractional programming (90C32) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Review text

The problem considered is that of mazimizing the quotient of two d.c. (difference of convex) functions over a convex, compact subset of \(\mathbb{R}^{n}\); the numerator and the denominator are assumed to be nonegative and strictly positive, respectively. The solution method proposed starts with transforming the problem into another constrained optimization problem, in which both the objective functions and the constraints are d.c.. The new problem is then solved by a branch-and-bound algorithm, which generates cutting planes to approximate the feasible region as well as conical partitions. The algorithm is shown to converge, and its behavior is illustrated by a numerical example, from the results of which the author draws the conclusion that the algorithm is likely to solve small problems efficiently. He also discusses about the possibility of extending the method for solving the sum-of-ratios problem.

Recommendations

• Conical partition algorithm for maximizing the sum of dc ratios
• An efficient algorithm for solving convex-convex quadratic fractional programs
• An algorithm for generalized fractional programs
• Fractional programming with convex quadratic forms and functions
• Branch-and-bound outer approximation algorithm for sum-of-ratios fractional programs

Cited in

(15)

• Conical partition algorithm for maximizing the sum of dc ratios
• Optimality conditions and DC-Dinkelbach-type algorithm for generalized fractional programs with ratios of difference of convex functions
• On fractional programming problem with bounded decision variables
• A Branch and Bound Algorithm for a Fractional 0-1 Programming Problem
• An approach to fractional programming via d.c. constraints problem: local search
• scientific article; zbMATH DE number 4143800 (Why is no real title available?)
• An Exact Method for a Discrete Quadratic Fractional Maximum Problem
• Approximation algorithms for combinatorial fractional programming problems
• scientific article; zbMATH DE number 1864569 (Why is no real title available?)
• Dinkelbach Type Approximation Algorithms for Nonlinear Fractional Optimization Problems
• Componentwise Dinkelbach algorithm for nonlinear fractional optimization problems
• An extension of branch-and-bound algorithm for solving sum-of-nonlinear-ratios problem
• A tractable discrete fractional programming: application to constrained assortment optimization
• Modified Dinkelbach-Type algorithm for generalized fractional programs with infinitely many ratios
• An efficient algorithm for solving convex-convex quadratic fractional programs

This page was built for publication: A combined algorithm for fractional programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5959292)