Re: [Help-glpk] (no subject)

[Michael Hennebry]

On Thu, 15 Nov 2007, Andrew Makhorin wrote:

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

Also, if v is a tentative objective value, then minimizing
p-vq will tell you if a better value is available.
In exact arithmetic, iterating will produce
an exact solution in a finite number of steps.
Binary search can guarantee polynomiality.
Zero can be your initial lower bound.
Any feasible solution will give you an upper bound.
Usually, v=(lo+hi)/2 will be a good choice.
If min p-vq==0, you have the optimum.
If         < 0, the new uppper bound< v.
If         > 0, v is the new lower bound and the new upper bound< hi.
If the upper bound does not change, use it for the next v.

-- 
Mike   address@hidden
"Horse guts never lie."  -- Cherek Bear-Shoulders