I coded the model in cplex (I'll give the slightly corrected version subsequently). It calculated f(5) = 9, parts= 1/60, 1/30, 1/20, 1/12, 1/10, 3/20, 1/6, 1/5, 1/5 and f(6) = 11, parts 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 1/6, 1/6 On Sun, Dec 17, 2017 at 5:52 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Slight correction in my last post. Here is the correct version. Tomorrow, when I get into work, I'll give the f(5) problem to cplex and report back.
Victor
Solve the following problem -- given a positive integer n > 1, and a positive integer k decide if there are k reals x[1], ..., x[k] >= 0 such that, for every integer i > 1, there are y[i,r,j], j=1, ..., k, r=1,...,i in {0,1}
1) sum_{j,r} y[i,r,j] = 1 # exactly one of the y[i,r,j] = 1 for each i 2) 1/i = sum_j y[i,r,j] * x[j] for r=1, ..., i 3) x[j] in [0, 1/n] for j=1,..., k
We can linearize (2) by using big-M:
z[i,r,j] = y[i,r,j] * x[j]. Then z[i,r,j] in [0, 1/n]
(1/n) * (1-y[i,r,j]) >= x[j] - z[i,r,j] >= -(1/n) * (1-y[i,r,j])
There's lots of symmetries. We can (partially) break them by insisting that for each i the k vectors (y[i,1,j], ... , y[i,i,j]), j=1,...,k are lexicographically increasing.
Also, as remarked before, we don't need to put any conditions for i, for which a non-trivial multiple is <=n.
On Sun, Dec 17, 2017 at 2:40 PM, Victor Miller <victorsmiller@gmail.com> wrote:
More specifically let x[1], ..., x[k] be non-negative variables <= 1, and for each i=2, ..., n, let y[i,j] be a 0/1 variable whose value of 1 means that x[i] contributes to the j-th 1/i. We then have 1/i = sum(j) y[i,j] * x[j]. We also have sum(i) y[i,j] = 1 (or maybe <= 1 if you want to omit that piece). You might object that sum(j) y[i,j] * x[j] isn't linear. You can fix this by introducting new variables z[i,j] = x[j] if y[i,j] = 1 and 0 otherwise. You can enforce this by z[i,j] <= (1-y[i,j]) + x[j] and z[i,j] >= x[j] - (1-y[i,j]). So giving this to a MIP solver is a finite algorithm for the problem.
On Sun, Dec 17, 2017 at 2:24 PM, Victor Miller <victorsmiller@gmail.com> wrote:
Here's a proof that there are optimal rational solutions: For a putatitve solution to f(n) = k, you can write a mixed integer program which will say whether or not there is such a solution. The only integer variables are 0/1 variables which indicate whether "piece" i contributes to a particular sum producing 1/n. There are only a finite number of settings for these. Once you have done this the remainder is a polytope bounded by half spaces with integer coefficients. So the vertices of the polytope have rational coefficients. An optimal solution must be among these.
On Sun, Dec 17, 2017 at 2:01 PM, Tom Karzes <karzes@sonic.net> wrote:
Can you prove that it's safe to ignore irrational solutions? Here's a (non-optimal) irrational solution for f(3), using 5 component values:
1/3 = sqrt(2)/8 + (8 - 3*sqrt(2))/24 1/3 = (4 - sqrt(2))/8 + (3*sqrt(2) - 4)/24 1/3 = 1/3
1/2 = sqrt(2)/8 + (4 - sqrt(2))/8 1/2 = 1/3 + (8 - 3*sqrt(2))/24 + (3*sqrt(2) - 4)/24
Can we always do as well (or better) using only rational component values? I suspect the answer is yes.
Note that the example above has the general form:
1/3 = a + (1/3 - a) 1/3 = (1/2 - a) + (a - 1/6) 1/3 = 1/3
1/2 = a + (1/2 - a) 1/2 = 1/3 + (1/3 - a) + (a - 1/6)
This works for any value of "a" that doesn't produce zero or negative values. In particular, "a" can be given a rational value. Is it the case that any solution involving irrational values can be decomposed into something like this, which in turn can be converted into a rational solution?
Tom
Allan Wechsler writes:
I was challenging myself to try to think of any finite algorithm, be it ever so expensive and cumbersome, that would settle the question of whether p pieces suffices for a given n. A useful lemma would be that if it can be done in p pieces, then it can be done with pieces whose denominaters divide n!. (LCM(1,...,n) would be even stronger, but for my purposes it doesn't matter how weak this lemma is.)
Then, we could say, "Iterate over all partitions of n! into p parts, and for each such partition, check to see if it works, using the partition as the numerators of fractions whose denominators are all n!." This would be heinously expensive but it would at least provide an upper bound on how much computational work we have to do.
But I can't even prove the lemma.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun