Wow, nice job! I was expecting f(5) to be 10. Your 9-part solution beats a simple union of divisions into equal parts! And your 11-part solution for f(6) also beats a simple union of divisions into equal parts! Have you tried f(7), or is that past what it can handle? Tom Victor Miller writes:
Whoops, in f(6) threre should have been 2 parts of size 7/60: 1/30, 1/30, 1/20, 1/20, 1/12, 1/12, 1/10, 7/60, 7/60, 1/6, 1/6
On Mon, Dec 18, 2017 at 2:22 PM, Victor Miller <victorsmiller@gmail.com> wrote:
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. >