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 [EMAIL PROTECTED] "Horse guts never lie." -- Cherek Bear-Shoulders _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
