Linear-fractional programming: Difference between revisions

Revision as of 17:25, 26 March 2011

Latest revision as of 11:52, 20 August 2025

(109 intermediate revisions by 48 users not shown)

Line 1:

{{Short description|Concept in mathematical optimization}}

In [[mathematical optimization]], '''linear-fractional programming''' ('''LFP)''') is a generalization of [[linear programming]] (LP). WhereWhereas the objective function ofin a linear programsprogram areis a [[linear functional|linear functionsfunction]], the objective function ofin a linear-fractional program is a ratio of two linear functions. InA otherlinear words,program can be regarded as a linearspecial programcase isof a fractional-linear-fractional program in which the denominator is the constant function having the value one everywhere1.

Formally, a linear-fractional program is defined as the problem of maximizing (or minimizing) a ratio of [[affine function]]s over a [[polyhedron]],

Informally, if linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model and given some list of requirements represented as linear equations, in linear-fractional programming model we can achieve the best (highest) ratio of outcome to cost, i.e. highest efficiency.

:<math>

\begin{align}

\text{maximize} \quad & \frac{\mathbf{c}^T \mathbf{x} + \alpha}{\mathbf{d}^T \mathbf{x} + \beta} \\

\text{subject to} \quad & A\mathbf{x} \leq \mathbf{b},

\end{align}

</math>

where <math>\mathbf{x} \in \mathbb{R}^n</math> represents the vector of variables to be determined, <math>\mathbf{c}, \mathbf{d} \in \mathbb{R}^n</math> and <math>\mathbf{b} \in \mathbb{R}^m</math> are vectors of (known) coefficients, <math>A \in \mathbb{R}^{m \times n}</math> is a (known) matrix of coefficients and <math>\alpha, \beta \in \mathbb{R}</math> are constants. The constraints have to restrict the [[feasible region]] to <math>\{\mathbf{x} | \mathbf{d}^T\mathbf{x} + \beta > 0\}</math>, i.e. the region on which the denominator is positive.<ref name="CC">{{cite journal |last1=Charnes |first1=A. |last2=Cooper |first2=W. W. |author2-link=William W. Cooper |year=1962 |title=Programming with Linear Fractional Functionals |journal=Naval Research Logistics Quarterly |volume=9 |issue=3–4 |pages=181–186 |doi=10.1002/nav.3800090303 |mr=152370}}</ref><ref name="BV">{{cite book |last1=Boyd |first1=Stephen P. |url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf |title=Convex Optimization |last2=Vandenberghe |first2=Lieven |publisher=Cambridge University Press |year=2004 |isbn=978-0-521-83378-3 |page=151 |access-date=October 15, 2011}}</ref> Alternatively, the denominator of the objective function has to be strictly negative in the entire feasible region.

==Motivation by comparison to linear programming==

For example, if in the frame of LP we maximize '''profit&nbsp;=&nbsp;income&nbsp;&minus;&nbsp;cost''' and obtain maximal profit of 100 units (=&nbsp;$1100&nbsp;of&nbsp;income&nbsp;&minus;&nbsp;1000$ of cost), then using LFP we can obtain only $10 of profit which requires only $50 of investment. Thus, in LP we have efficiency $100/$1000&nbsp;=&nbsp;0.1, at the same time LFP provides efficiency equal to $10/$50&nbsp;=&nbsp;0.2.

Both linear programming and linear-fractional programming represent optimization problems using linear equations and linear inequalities, which for each problem-instance define a [[feasible set]]. Fractional linear programs have a richer set of objective functions. Informally, linear programming computes a policy delivering the best outcome, such as maximum profit or lowest cost. In contrast, a linear-fractional programming is used to achieve the highest ''ratio'' of outcome to cost, the ratio representing the highest efficiency. For example, in the context of LP we maximize the objective function '''profit&nbsp;=&nbsp;income&nbsp;&minus;&nbsp;cost''' and might obtain maximum profit of $100 (=&nbsp;$1100&nbsp;of&nbsp;income&nbsp;&minus;&nbsp;$1000 of cost). Thus, in LP we have an efficiency of $100/$1000&nbsp;=&nbsp;0.1. Using LFP we might obtain an efficiency of $10/$50&nbsp;=&nbsp;0.2 with a profit of only $10, but only requiring $50 of investment.

==Transformation to a linear program==

Fractional-linear programs are [[quasiconvex function|quasiconvex]] [[convex minimization|minimization]] problems with a [[monotonicity|monotone]] property, "[[pseudoconvex function|pseudoconvexity]]" which is a stronger property than [[quasiconvex function|quasiconvexity]]. A fractional-linear objective function has both "pseudoconvexity" and "pseudoconcavity", these properties allowing FLP problems to be solved by a variant of the [[simplex algorithm]] (of [[George B. Dantzig]]).<ref>

Any linear-fractional program can be transformed into a linear program, assuming that the feasible region is non-empty and bounded, using the '''Charnes–Cooper transformation'''.<ref name="CC" /> The main idea is to introduce a new non-negative variable <math>t </math> to the program which will be used to rescale the constants involved in the program (<math>\alpha, \beta, \mathbf{b}</math>). This allows us to require that the denominator of the objective function (<math>\mathbf{d}^T \mathbf{x} + \beta</math>) equals 1. (To understand the transformation, it is instructive to consider the simpler special case with <math>\alpha = \beta = 0</math>.)

Chapter five: {{cite book| last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=145|isbn=3-88538-404-3 |id={{MR|949209}}| }}</ref><ref> {{cite article | last1=Kruk | first1=Serge|last2=Wolkowicz|first2=Henry|title=Pseudolinear programming | url=http://www.jstor.org/stable/2653207 |journal=[[SIAM Review]]|volume=41 |year=1999 |number=4 |pages=795-805 |id={{MR|1723002}}.{{jstor|2653207}}.{{doi|DOI:10.1137/S0036144598335259}}| }}

</ref><ref> {{cite article | last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management |url=http://www.jstor.org/stable/2132826|journal=[[SIAM Review]]|volume=37 |year=1995 |number=2 |pages=230-234|id={{MR|1343214}}.{{jstor|2132826}}.{{doi|DOI:10.1137/1037046}}|}}

</ref><ref>{{harvtxt|Murty|1983|loc=Chapter&nbsp;3.20 (pp.&nbsp;160–164) and pp.&nbsp;168 and&nbsp;179}}</ref> FLP problems can also be solved by the [[criss-cross algorithm]], which is a "purely combinatorial" [[exchange algorithm|basis-exchange algorithm]].<ref>{{cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|number=1|

pages=198–214|year=1999|issn=0377-2217|doi=10.1016/S0377-2217(98)00049-6|url=http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|ref=harv}}</ref>

Formally, the linear program obtained via the Charnes–Cooper transformation uses the transformed variables <math>\mathbf{y} \in \mathbb{R}^n</math> and <math>t \ge 0 </math>:

== References ==

:<math>

<references/>

\begin{align}

\text{maximize} \quad & \mathbf{c}^T \mathbf{y} + \alpha t \\

\text{subject to} \quad & A\mathbf{y} \leq \mathbf{b} t \\

& \mathbf{d}^T \mathbf{y} + \beta t = 1 \\

& t \geq 0.

\end{align}

</math>

A solution <math>\mathbf{x}</math> to the original linear-fractional program can be translated to a solution of the transformed linear program via the equalities

* {{cite book|first=E. B.|last=Bajalinov|title=Linear-Fractional Programming: Theory, Methods, Applications and Software| publisher=Kluwer Academic Publishers|___location=Boston|year=2003}}

:<math>\mathbf{y} = \frac{1}{\mathbf{d}^T \mathbf{x} + \beta} \cdot \mathbf{x}\quad \text{and} \quad t = \frac{1}{\mathbf{d}^T \mathbf{x} + \beta}.</math>

Conversely, a solution for <math>\mathbf{y}</math> and <math>t </math> of the transformed linear program can be translated to a solution of the original linear-fractional program via

* {{cite book|last=Barros|first=Ana Isabel|title=Discrete and fractional programming techniques for ___location models|series=Combinatorial Optimization|volume=3|publisher=Kluwer Academic Publishers|___location=Dordrecht|year=1998|pages=xviii+178|isbn=0-7923-5002-2|id={{MR|1626973}}|}}

:<math>\mathbf{x}=\frac{1}{t}\mathbf{y}.</math>

*{{cite book| last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=145|isbn=3-88538-404-3 |id={{MR|949209}}| }}

==Duality==

* {{cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|number=1|

Let the [[duality (optimization)|dual variables]] associated with the constraints <math>A\mathbf{y} - \mathbf{b} t \leq \mathbf{0}</math> and <math>\mathbf{d}^T \mathbf{y} + \beta t - 1 = 0</math> be denoted by <math>\mathbf{u}</math> and <math>\lambda</math>, respectively. Then the dual of the LFP above is <ref>{{cite journal|last1=Schaible |first1=Siegfried |title=Parameter-free Convex Equivalent and Dual Programs|journal=Zeitschrift für Operations Research |volume=18 |year=1974 |issue=5 |pages=187–196|doi=10.1007/BF02026600|mr=351464|s2cid=28885670 }}</ref><ref>{{cite journal|title=Fractional programming&nbsp;I: Duality |last1=Schaible |first1=Siegfried | journal=Management Science |volume=22 |issue=8 |pages=858–867 |year=1976|jstor=2630017|mr=421679|doi=10.1287/mnsc.22.8.858}}</ref>

pages=198–214|year=1999|issn=0377-2217|doi=10.1016/S0377-2217(98)00049-6|url=http://www.sciencedirect.com/science/article/B6VCT-3W3DFHB-M/2/4b0e2fcfc2a71e8c14c61640b32e805a|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|ref=harv}}

:<math>

\begin{align}

\text{minimize} \quad & \lambda \\

\text{subject to} \quad & A^T\mathbf{u} + \lambda \mathbf{d} = \mathbf{c} \\

& -\mathbf{b}^T \mathbf{u} + \lambda \beta \geq \alpha \\

& \mathbf{u} \in \mathbb{R}_+^m, \lambda \in \mathbb{R},

\end{align}

</math>

which is an LP and which coincides with the dual of the equivalent linear program resulting from the Charnes–Cooper transformation.

==Properties and algorithms==

* {{cite article|last1=Kruk|first1=Serge|last2=Wolkowicz|first2=Henry|title=Pseudolinear programming|url=http://www.jstor.org/stable/2653207|journal=[[SIAM Review]]|volume=41 |year=1999 |number=4|pages=795-805|id={{MR|1723002}}.{{jstor|2653207}}.{{doi|DOI:10.1137/S0036144598335259}}|}}

Fractional-The objective function in a linear-fractional programsproblem areis both quasiconcave and [[quasiconvex function|quasiconvex]] [[convex(hence minimization|minimization]] problemsquasilinear) with a [[monotonicity|monotone]] property, "[[pseudoconvex function|pseudoconvexity]]", which is a stronger property than [[quasiconvex function|quasiconvexity]]. A fractional-linear-fractional objective function hasis both "pseudoconvexity"pseudoconvex and "pseudoconcavity"pseudoconcave, thesehence properties[[pseudolinear allowingfunction|pseudolinear]]. FLPSince problemsan LFP can be transformed to an LP, it can be solved byusing aany variantLP ofsolution method, such as the [[simplex algorithm]] (of [[George B. Dantzig]]).,<ref>

Chapter five: {{cite book| last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=145|isbn=978-3-88538-404-35 |idmr={{MR|949209}}| }}</ref><ref> {{cite article journal| last1=Kruk | first1=Serge|last2=Wolkowicz|first2=Henry|title=Pseudolinear programming | url=http://www.jstor.org/stable/2653207 |journal=[[SIAM Review]]|volume=41 |year=1999 |numberissue=4 |pages=795-805795–805 |idmr={{MR1723002|1723002}}.{{jstor=2653207|2653207}}.{{doi|DOI:=10.1137/S0036144598335259}}| bibcode=1999SIAMR..41..795K|citeseerx=10.1.1.53.7355}}

</ref><ref> {{cite articlejournal | last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management |url=http://www.jstor.org/stable/2132826|journal=[[SIAM Review]]|volume=37 |year=1995 |numberissue=2 |pages=230-234230–234|idmr={{MR1343214|1343214}}.{{jstor=2132826|2132826}}.{{doi|DOI:=10.1137/1037046}}|s2cid=120626738 }}

</ref><ref>{{harvtxt|Murty|1983|loc=Chapter&nbsp;3.20 (pp.&nbsp;160–164) and pp.&nbsp;168 and&nbsp;179}}</ref> FLP problems can also be solved by the [[criss-cross algorithm]], which is a "purely combinatorial" [[exchange algorithm|basis-exchange algorithm]].<ref>{{cite journal|title=The finite criss-cross method for hyperbolic programming|journal=European Journal of Operational Research|volume=114|numberissue=1|

pages=198–214|year=1999 <!-- issn=0377-2217 -->|doi=10.1016/S0377-2217(98)00049-6|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|zbl=0953.90055|id=[http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz Postscript preprint]|citeseerx=10.1.1.36.7090}}</ref> or [[interior-point method]]s.

==Notes==

* {{cite book|last=Martos|first=Béla|title=Nonlinear programming: Theory and methods|publisher=North-Holland Publishing Co.|___location=Amsterdam-Oxford|year=1975|pages=279|isbn=0-7204-2817-3|id={{MR|496692}}|}}

<references />

==Sources==

* {{cite article | last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=A nonlinear programming algorithm for hospital management|url=http://www.jstor.org/stable/2132826|journal=[[SIAM Review]]|volume=37 |year=1995 || number=2|pages=230-234|id={{MR|1343214}}.{{jstor|2132826}}.{{doi|DOI:10.1137/1037046}}||}}

* {{cite book|last=Schaible|first=S.|chapter=Fractional programming|pages=495–608|id={{MR|1377091}}|title=Handbook of global optimization|editor=Reiner Horst and Panos M. Pardalos|

series=Nonconvex optimization and its applications|volume=2|publisher=Kluwer Academic Publishers|___location=Dordrecht|year=1995|isbn=0-7923-3120-6}}

* {{cite book | last=Stancu-Minasian Murty| first=IKatta&nbsp;G.|author-link=Katta MG.| titleMurty|chapter=3.10 Fractional programming: Theory, methods and applications(pp. 160–164)| Translated by Victor Giurgiutiu from the 1992 Romanian | seriestitle=MathematicsLinear and its applications|volume=409programming|publisher=KluwerJohn AcademicWiley Publishers& GroupSons, Inc.| ___location=DordrechtNew York| year=1997 1983| pages=viiixix+418 482| isbn=978-0-7923471-458009725-0 9| idmr={{MR|1472981}} | 720547}}

==Further Software reading==

* {{cite book|first=E. B.|last=Bajalinov|title=Linear-Fractional Programming: Theory, Methods, Applications and Software| publisher=Kluwer Academic Publishers|___location=Boston|year=2003}}

* [http://zeus.nyf.hu/~bajalinov/WinGulf/wingulf.html WinGULF] &ndash; educational interactive linear and linear-fractional programming solver with a lot of special options (pivoting, pricing, branching variables etc.).

* {{cite book|last=Barros|first=Ana Isabel|title=Discrete and fractional programming techniques for ___location models|series=Combinatorial Optimization|volume=3|publisher=Kluwer Academic Publishers|___location=Dordrecht|year=1998|pages=xviii+178|isbn=978-0-7923-5002-26|idmr={{MR|1626973}}|}}

* {{cite book|last=Martos|first=Béla|title=Nonlinear programming: Theory and methods|publisher=North-Holland Publishing Co.|___location=Amsterdam-Oxford|year=1975|pages=279|isbn=978-0-7204-2817-39|idmr={{MR|496692}}|}}

* {{cite book|last=Schaible|first=S.|chapter=Fractional programming|pages=495–608|idmr={{MR|1377091}}|title=Handbook of global optimization|editor=Reiner Horst and Panos M. Pardalos|

series=Nonconvex optimization and its applications|volume=2|publisher=Kluwer Academic Publishers|___location=Dordrecht|year=1995|isbn=978-0-7923-3120-69}}

*{{cite book | last=Stancu-Minasian | first=I. M.| title=Fractional programming: Theory, methods and applications | others=Translated by Victor Giurgiutiu from the 1992 Romanian | series=Mathematics and its applications|volume=409|publisher=Kluwer Academic Publishers Group | ___location=Dordrecht | year=1997 | pages=viii+418 | isbn=978-0-7923-4580-0 | mr=1472981 }}

[[Category:Mathematical optimization]]

[[Category:Operations research]]

[[Category:Pseudolinear minimization]]

{{DEFAULTSORT:Linear-Fractional Programming}}

[[ru:Дробно-линейное программирование]]

[[Category:Optimization algorithms and methods]]

[[uk:Задача дробово-лінійного програмування]]

[[Category:Linear programming]]

[[Category:OperationsGeneralized researchconvexity]]