non-linear mixed integer programming question - MathOverflow

non-linear mixed integer programming question

2010-06-10T02:59:44Z

I tried this question over in the algorithms section of stackoverflow and never really got a handle on the problem. I know it concerns non-linear mixed integer programming.

[In the following, 1...n and k are subscripts. n will be relatively small - like say 5-20, or something like that. No more than a second or two to solve computationally, but I can cut it off after some time limit.]

Say you have C1...Cn, and some some positive integer M. (C1...Cn are positive constants and need not be integers. M will incidentally always be 127.) Can you find a postive scaling factor s and a group of integers t1...tn each less than or equal to M (and greater than 0) such that the following objective function is minimized:

summation[for k=1 to n] of (abs(tk*s - Ck)).

Sort of akin to some variant of the knapsack problem or something else maybe? I don't know. Haven't really done non-linear programming before.

Answer by Mark for non-linear mixed integer programming question

2010-06-11T06:11:09Z

FWIW, I ended up just brute-forcing it, but using the solution provided in the first comment by Jules in the OP for finding optimal t1...tn when s is given. I just iterate through s .0001 at at a time from 0 to 20 (s will never be higher than that) and it takes about a second and well worth it. Its far preferable to the results obtained by just using s = max(C)/M.

Answer by Gerhard Paseman for non-linear mixed integer programming question

2010-06-11T12:06:00Z

To support Mark's and Jules' observation that max(Ci)/M is a good starting point, I mention the following. Suppose an initial value r was chosen in an attempt to find s. If the Ci were all less than (M+1)r, the total error would be at most n*r, since one could find positive integers ui with (ui-1)r <= Ci <= ui*r, and one of ui, ui-1 would be in the range 1 to M. So smaller r means smaller worst case error.

Also, if one has a trial r and computes ui based on r, then looking at sum ui*ei, where ei is the sign of the error ui*r - Ci, one has an indication of which direction to tweak r to reduce the amount of sum abs(ui*r - Ci), while keeping the same values ui.

Gerhard "Ask Me About System Design" Paseman, 2010.06.11

Answer by Mark for non-linear mixed integer programming question

2010-06-11T13:46:04Z

(This is in response to Gerhard Paseman's answer.)

                 .0001            .001 
maxC/M           2.528183          2.528183 
calculated s     4.459300          8.917000 
total error      2.703720          2.718460

The above represents two runs - one incrementing by .0001 and the other .001 (from 0 to 20 in both cases). One trend is that the difference in total error between .001 and .0001 is absolutely consistent with the above, regardless of the data. The total error is in this case divided between 6 elements, each element averaging about 200 in size. If maxC/M were used as s, the total error would have been something like 7 or higher.)

But as to your observation regarding maxC/M being a good starting point for finding s, you can see above what s turned out to be. When using .001 as the increment, s was often much higher than with .0001, (with a consistent reduction in the size of the values for t). So maybe with increasing precision in the search, s converges towards the vicinity of maxC/m, but the example above has thus far seemed to be fairly typical. Haven't completely digested your remarks above yet. Thanks for letting a non-mathematician like me crash the party here.