RE: [Help-glpk] (no subject)

[Dan Tulk]

Thanks for your help

-----Original Message-----
From: Michael Hennebry
[mailto:address@hidden 
Sent: 15 November 2007 17:24
To: Andrew Makhorin
Cc: Dan Tulk; address@hidden
Subject: Re: [Help-glpk] (no subject)

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




      
____________________________________________________________________________________
Never miss a thing.  Make Yahoo your home page. 
http://www.yahoo.com/r/hs