Re: [Help-glpk] (no subject) : Fractional Programming for Data Envelopment Analysis among others

[Ivo van Baren]

Hi Dan and Andrew,

This problem is an instance of what is called "fractional programming" and 
is applied in Data Envelopment Analysis among others.

The general form of the problem is:
Max  z = [c0 + (c1*x1) + (c2*x2) + ... + (cn * xn)]  /  [d0 + (d1*x1) + 
(d2*x2) + ... + (dn * xn)]

s.t.   (ai1*x1) + (ai2*x2) + ... + (ain * xn) = bi        for i = 1,2,...,m

Under certain assumptions, the problem above can be nicely transformed to a 
standard linear model without the complications of  a piecewise linear 
approximation.

To this purpose, define r = 1 / [d0 + (d1*x1) + (d2*x2) + ... + (dn*xn)].and 
assume r  > 0 for all feasible values of xj.
There are tricks to fulfil this assumption: if xj .>= 0, take a (not too) 
small positive value for d0.

The objective function z cab then be rewritten as follows:

z = c0*r + (c1*x1*r) + (c2*x2*r) + ... + (cn * xn*r)]

Next define yj = r*xj. The maximization problem becomes now:

max z = c0*r + (c1*y1) + (c2*y2) + ... + (cn * yn)].

s.t.  (ai1*y1) + (ai2*y2) + ... + (ain * yn) = r*bi        for i = 1,2,...,m

and d0*r + (d1*y1) + (d2*y2) + ... + (dn*yn) = 1.

Success!

Best regards,

Ivo van Baren



----- Original Message ----- 
From: "Andrew Makhorin" <address@hidden>
To: "Dan Tulk" <address@hidden>
Cc: <address@hidden>
Sent: Thursday, November 15, 2007 10:37 AM
Subject: Re: [Help-glpk] (no subject)


> > I've been using GLPK to solve an optimisation with objective function of 
> > the
> > form
>
> >         (c1*x1) + (c2*x2) + ... + (cn * xn)
>
> > Is there any way to use GLPK to solve an objective function of the form?
>
> >         [(c1*x1) + (c2*x2) + ... + (cn * xn)] / [(d1*x1) + (d2*x2) + ... 
> > + (dn * xn)]
>
> You cannot use the latter objective directly, because it is non-linear
> while glpk allows only linear objectives and constraints. Besides, that
> objective is non-convex, so there may be multiple local optima.
>
> Nevertheless, you can reformulate your problem using piecewise linear
> approximation of the objective. For example, introducing variables
>
>   p = (c1*x1) + (c2*x2) + ... + (cn * xn)
>
>   q = (d1*x1) + (d2*x2) + ... + (dn * xn)
>
> you can write the objective as follows:
>
>   z = p / q
>
> Let p and q be positive, and you need to minimize z. Instead that you
> can minimize the following separable function:
>
>   ln z = ln p - ln q
>
> replacing ln p and ln q by a piecewise linear approximation.
>
> For more details see
> http://lists.gnu.org/archive/html/help-glpk/2007-06/msg00005.html .
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk