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" <[EMAIL PROTECTED]>
To: "Dan Tulk" <[EMAIL PROTECTED]>
Cc: <[email protected]>
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
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
