Solving an equation where some unknowns must be integers

Question

Decide for s and t ₁ & hellip; t _n , which minimizes the following summation:

& Sigma; ⁿ _{k = 1} (1 - min (s · t _k , C _k )) / max (s & Midot; t <sub> ksub>, C <sub> ksub>)),

Where

C ₁ ? C _n > 1, s> 0, t ₁ ? t _n & isin; ℤ ⁺

---

to clarify the description of the problem:

"how fast is the algorithm you need." Not super fast (but not a few seconds). n will be around 5-10 or so.

As for the real problem, I have a number of “elements” of different sizes on the “page”, and this page should be converted to a format in which there is a maximum base size for the element X, and the base size of the element must be an integer. However, in the new format, any element can be scaled with a single scaling factor set for the page.

So, C ₁ ... C _n were the size of the elements on the original page. t ₁ ... t _n are the new integer sizes in the new page format. (And t ₁ ... t _n must be less than X.) The scaling factor for the new page format is s.

---

More details:

As far as I did, I find the largest element on the original page, and if it's smaller than X, I just use the existing element sizes on the new page, but rounding each to an integer. However, if the largest element on the original page is larger 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 leads to discrepancies of about 1-3% on average for each element on a new page, but the largest. Not all of this is noticeable, but I'm a perfectionist.

Answer 1

You should read linear programming with whole unknowns . Although this is not linear programming, it can give you an idea of ​​what to look for.

Alternatively, you can go to https://mathoverflow.net/ to get some help in remodeling the problem (you have the problem of optimizing the integer domain with gaps in the function of the target and my math will rust a little to correctly place it, also check the combinatorial optimization

(for the correct solution, go to EDIT4 below)
EDIT: Regarding linearity

Look for the maximum

& Sigma; ⁿ _{k = 1} (1 - min (s · t _k , C _k )) / max (s & Midot; t <sub> ksub>, C <sub> ksub>))

may be the same as viewing maximum for

& Sigma; ⁿ _{k = 1} (max (s · t _k , C _k )) - min (s & Midot; t <sub> ksub>, C <sub> ksub>))

provided that

& Sigma; ⁿ _{k = 1} max (s · t _k , C _k )> 0 Strike>

(which is always true, given your conditions)

And the term

& Sigma; ⁿ _{k = 1} (max (s · t _k , C _k )) - min (s & Midot; t <sub> ksub>, C <sub> ksub>))

can be written as

& Sigma; ⁿ _{k = 1} Abs (s? t _k - C _k )

which, if the question mark above, 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.

Well, that’s why I initially made a mistake with my proposal, because I decided that the question is degenerate in trivial , which is actually quite obvious.

EDIT2: My math is rusty, the procedure described above is incorrect (first step), but the output / solution seems to be confirmed, so I will not fix it (it gets a little more complicated)

EDIT3 (C _k are constants and other fixes):

Perhaps I should remove the answer, I believe that the following reasoning is sufficient as a solution:

The fact that C _{k are} constant and not equal to 1 does not matter. To maximize the original expression

& Sigma; ⁿ _{k = 1} (1 - min (s · t _k , C _k )) / max (s & Midot; t <sub> ksub>, C <sub> ksub>))

you have to collapse

& Sigma; ⁿ _{k = 1} min (s · t _k , C _k ) / max (s & Midot; t <sub> ksub>, C <sub> ksub>)

since the domain of everything is positive, to make this ratio minimal, you must make the numerator as small as possible and the denominator as large 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 above, only this limit is 0)
• s approaches infinity ⇒ min (∞, C _k ) / max (∞, C _k ) = C _k / ∞ = 0
  (the above equalities should use limit notation ...)
• t _k approaches infinity for all k

(each condition is sufficient in itself and represents a solution when their combination does not allow s to approach 0, and t _k approaches infinity or vice versa, in this case it is important, it’s faster)

EDIT4: (actual solution)
Well, basically all of the above gives an answer to the wrong question, because I was looking for the maximum source objective function, not the minimum.

At a minimum, this is a little more interesting, a minimum is achieved if each member

min (s & Midot; t <sub> xub>, C <sub> xub>) / max (s & Midot; t <sub> xub>, C <sub> xsub>) = 1

This is the maximum of this term given by the parameter area. If we assume (at the moment) that C _k is an integer, then a solution can be found for

s = 1
t <sub> xsub> = C <sub> xsub>

However, C _{k is} not an integer in the general case, so we need to find s for which C _k / s is an integer.

If we can write C _k as

N _k / D _k , where N, D ∈ ℤ ⁺ (in other words, if C _k rational )

then the solution may be

s = 1 / & prod; ⁿ _{k = 1} D _k
t _k = N _k / D _k ? & prod; ⁿ _{k = 1} D _k (which is ∈ ℤ ⁺ )

Note: Instead of choosing s for the product of all denominators, it can be set to the largest common denominator, and then t _k can be calculated accordingly.

Note 2: The graphs of the function diagrams in question helped me catch my mistake in misunderstanding the issue (realizing that the minimum is much more interesting). I also realized that the functions are continuous (but not smooth, so the differentiations are discontinuous).

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

Answer 2

To do this, use Maple, Mathcad or Sage. Here is a list of programs that can help you: http://en.wikipedia.org/wiki/Comparison_of_computer_algebra_systems

Answer 3

I think the foolishness gave the correct answer. You need to read the book 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 do not think lp_solve is not enough for you because you cannot rewrite your problem into the Integer linear Programming (MILP) mixed integer task. Maple and Mathcad are not a good idea because you are not looking for a symbolic algebra package.

My guess is that the book will tell you how to make a branch and link it. Here is a schematic description:

1) Start solving the generalized problem, where t_k are all real seaside numbers

minimize Σnk = 1 (1 - min (s · tk, Ck) / max (s · tk, Ck)), with the restriction s> 0, t1 ... tn ∈ R +

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

2) Once you have found this solution, you can take the transition step. Select t_k and integer a_k and solve the following two problems independently

Minimize problem 1 Σnk = 1 (1 - min (s · tk, Ck) / max (s · tk, Ck)), provided that s> 0, t1 ... tn ∈ R + and t_k <= a_k

Minimize problem 2 Σnk = 1 (1 - min (s · tk, Ck) / max (s · tk, Ck)) under the restriction s> 0, t1 ... tn ∈ R + and t_k> = a_k

3) Continue to follow the branching steps until you divide your problem into a set of subtasks, each of which has an integer solution. Then you can compare these integer solutions and choose the best one.

As you probably guessed, this description is somewhat schematic. You need good branching rules to fork the correct path, and you need good bounding rules to avoid the following branches, which are promising.