solving an equation where some unknowns must be integers

Question

Solve for s, and t₁…t_n that minimizes the following summation:

Σⁿ_{k = 1} (1 - min(s·t_k,C_k)/max(s·t_k,C_k)),

where

C₁…C_n > 1, s > 0, t₁…t_n ∈ ℤ⁺

---

edit to clarify to problem description:

"how fast of an algorithm you require." Not super fast (But not multiple seconds). n will be around 5-10 or so.

As far as the actual problem, I have a number of "elements" of different sizes on a "page" and this page needs to be translated to a format in which there is a maximum base size for an element of X, and the base size of an element has to be an integer. However in the new format any element can be scaled up by a single scaling factor set for the page.

So C₁...C_n were the sizes of the elements on the original page. t₁...t_n are the new integer sizes in the new page format. (And t₁...t_n need to be less than X.) The scaling factor for the new page format is s.

---

More:

As far as what I've done previously, I find the largest element on the original page, and if its smaller than X, I just use the existing element sizes on the new page, but rounding each one to an integer. However, If the largest element on the original page is greater than X, I divide its size by X to get the scaling factor s for the new page, and divide C₁...C_n by s to get t₁...t_n. But this results in size discrepancies of something like 1-3% on average for every element on the new page but the largest. Not really all that noticeable, but I'm a perfectionist.

Answer 1

You should read on linear programming with integer unknowns as well. Even though this is not linear programming it might give you an idea on what to look for.

Also you might head over to https://mathoverflow.net/ to get some help remodelling the problem (you have an optimization problem on an integer domain with discontinuities in goal function and my math is a bit rusty to place it properly; check combinatorial optimization as well)

(for the right solution jump to EDIT4 below)
EDIT: Regarding linearity

Looking for maximum of

Σⁿ_{k = 1} (1 - min(s·t_k,C_k)/max(s·t_k,C_k))

might be the same as looking at the maximum for

Σⁿ_{k = 1} (max(s·t_k,C_k) - min(s·t_k,C_k))

providing that

Σⁿ_{k = 1} max(s·t_k,C_k) > 0

(which is always ?true? given your conditions)

And term

Σⁿ_{k = 1} (max(s·t_k,C_k) - min(s·t_k,C_k))

can be written as

Σⁿ_{k = 1} Abs(s·t_k - C_k)

which, if the question mark above hold gives the following

• maximize s and all t_k
• minimize all C_k

So all C = 1, and all t and s → ∞ for which your original expression approaches n.

Ok, so originally I was wrong with my suggestion, because I assumed a question would not degenerate into trivial case, which actually it quite obviously does.

EDIT2: My math is rusty, the procedure above is not correct (first step), but the conclusion/solution seems to validate so I will not correct (it gets a bit complicated)

EDIT3 (C_k are constants and other corrections):

Maybe I should clean up the answer, I believe the following reasoning is enough as a solution:

The fact that C_k are constant and not equal 1 does not matter. To maximize original expression

Σⁿ_{k = 1} (1 - min(s·t_k,C_k)/max(s·t_k,C_k))

you should minimize

Σⁿ_{k = 1} min(s·t_k,C_k)/max(s·t_k,C_k)

since domain of everything is positive to make this ratio minimal you have to make numerator as small as possible and denominator as big as possible.

The ratio is zero if

• t_k is 0 for all k ⇒ min(0, C_k)/max(0, C_k) = 0/C_k = 0

It also approaches zero if

• s approaches zero (similarly as above, only it is the limit that is equal 0)
• s approaches infinity ⇒ min(∞, C_k)/max(∞, C_k) = C_k/∞ = 0
  (the above equalities should have used limit notation...)
• t_k approaches infinity for all k

(each condition is enough on its own and represents the solution, when combining them don't let s approach 0 while t_k approach infinity or vice versa; in such case it matters which one approaches it faster)

EDIT4: (actual solution)
Well basically all of the above is giving answer to a wrong question, because I was looking for maximum of the original goal function, not the minimum.

As for minimum it is a bit more interesting, the minimum is reached if each term

min(s·t_k,C_k)/max(s·t_k,C_k) = 1

This is the maximum of this term given the domain of the parameters. If we assume (for now) that C_k is integer then the solution can be found for

s = 1
t_k=C_k

However C_k is not integer in general case, so we need to find s for which C_k/s is integer.

If we can write C_k as

N_k/D_k where N, D ∈ ℤ⁺ (in another words if C_k is rational)

then a solution can be

s = 1/∏ⁿ_{k = 1}D_k
t_k = N_k/D_k · ∏ⁿ_{k = 1}D_k (which is ∈ ℤ⁺)

Note: Instead of choosing s to be a product of all denominators it could be set to biggest common denominator, and then t_k can be calculated appropriately.

Note2: Plotting diagrams of the functions in question helped me catch my error of misreading the question (realizing that minimum is much more interesting). Also I realized that the functions are continuous (but not smooth, so derivations are discontinuous).

Note3: The above solution works for rational numbers, but I imagine that irrational numbers would not make the solution useless as decimal or other rational representations of irrational numbers would give an approximate solution proportionally close to real solution as the representation is close to actual value of irrational number.

Answer 2

I think that unreason gave the correct answer. You need to read a book about "Nonlinear Integer Programming". I don't have a good book to recommend you, but you can probably find something by going to the library.

I don't think that lp_solve is not good enough for you, because you cannot rewrite your problem in to a mixed integer Integer linear Programming problem (MILP). Maple and Mathcad is not a good idea, because you are not looking for symbolic algebra package.

My guess us that the book will tell you to do branch and bound. Here is a schematic description:

1) Start out solving a generalized problem where t_k are all real prsitime numbers

minimize Σnk = 1 (1 - min(s·tk,Ck)/max(s·tk,Ck)), under the constrain that s > 0, t1…tn ∈ R+

.You can use a generalized Newtons method to do this. Matlab and scipy provide generalized solvers this out of the box, but be careful because your function may have several local minima.

2) Once you have found this solution, you can do a branch ing step. Choose a variables t_k and an integer number a_k, and solve the following two problems independently

Problem 1 minimize Σnk = 1 (1 - min(s·tk,Ck)/max(s·tk,Ck)), under the constrain that s > 0, t1…tn ∈ R+and t_k <= a_k

Problem 2 minimize Σnk = 1 (1 - min(s·tk,Ck)/max(s·tk,Ck)), under the constrain that s > 0, t1…tn ∈ R+ and t_k >= a_k

3) Keep doing branching steps until you have split your problem in to a set of sub-problems that each have an integer solution. Then you can compare these integer solutions and choose the best one.

As you probably have guessed this description is somewhat schematic. You need good branching rules to branch the correct way, and you need good bounding rules to avoid following branches that arent promising.

Answer 3

Please use Maple, Mathcad or Sage for that. Here is a list of software, that can help you with it: http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems