Re: [Help-glpk] (no subject)

[Andrew Makhorin]

> 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 .