1
$\begingroup$

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.

Improve this question
$\endgroup$
21
  • $\begingroup$ Is your $s$ an integer? $\endgroup$
    – Will Jagy
    Commented Jun 10, 2010 at 3:57
  • $\begingroup$ No s does not have to be an integer. Also, contrary to what I wrote previously, C1...Cn do not all have to be greater than M. t1...tn do all have to be less than or equal to M. $\endgroup$
    – Mark
    Commented Jun 10, 2010 at 4:17
  • $\begingroup$ This may not be what you think. Experiment with $n=2$ and the continued fraction approximation $$ \frac{p}{q} \sim \frac{C_2}{C_1} $$ then take $t_1 = q$ and $t_2 = p .$ Then pick your best $s.$ The result will be good because $$ \frac{C_2}{p} \sim \frac{C_1}{q} .$$ Requires further thought for $n \geq 3.$ I was looking for the PSLQ method but I think your problem goes in another direction. Anyway, read en.wikipedia.org/wiki/Integer_relation_algorithm for now. Also, what is this for? $\endgroup$
    – Will Jagy
    Commented Jun 10, 2010 at 4:50
  • $\begingroup$ I have a page with various graphical elements on it. THese graphical elements have varying nonintenger "sizes". This is the (C1...Cn). The entire page needs to be converted to another format in which the size of graphical elements can only be expressed as integers less than or equal to 127, but all the elements on the new page can be scaled up by a single scaling factor s. So I want the graphical elements in the new format to be as close in size as possible to their size on the old page. I know I 'm being vague about the specific platform, but the above accurately characterizes the problem. $\endgroup$
    – Mark
    Commented Jun 10, 2010 at 5:00
  • $\begingroup$ Just a quick persual of that integer algorithm leads me to the following observation. Their scenario has multiple specific real numbers as given, that you then determine an integer relation for. In my case there is only one real number, s, but it is one of the unknowns, (along with the integers t1...tn) and not a given. So it seems like a significant difference to me, but I'll keep reading. $\endgroup$
    – Mark
    Commented Jun 10, 2010 at 5:08

3 Answers 3

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I predict, with a precision run of .00005, you will get an s with a value at or near 2.97255 with an error value less than 2.69 on the same input. Gerhard "Ask Me About System Design" Paseman, 2010.06.11 $\endgroup$
    – Gerhard Paseman
    Commented Jun 11, 2010 at 15:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .