On Jan 15, 2009, at 4:17 PM, victor miller wrote:
I've calcuated U(4,13) = 11/6 (using Veit's notation) using CPLEX (industrial strength MIP) with the MIP that Veit suggested.
It seems to be implicit in the above discussion that the optimal values of U(m,n) are all rational. Perhaps this seems obvious, but here's a proof (courtesy of David Moulton):
For each of the 2^mn settings of the y[i,j] variables (i.e. y[i,j] = 1, if and only if x[i,j] > 0) we can find the optimal value by means of a linear program:
maximize u subject to
x[i,j] >= u for all i,j such that y[i,j] = 1, plus the column and row sums being the right value. All the coefficients of the resulting matrix are integers, so the vertices of the resulting polytope are rational. Can one put a good bound on the possible denominators? They all appear to be small.
Victor
I'm sure you realize these "baker's dozen" instances are particularly important for the people who perpetrated this puzzle! That's the smallest denominator I've seen. Maybe you can test the following. It's trivial to show that U(k m, k n) >= k U(m, n) but for all the cases I've looked at >= can be replaced by = . Can you find a counterexample? I use "divide and concur" to find the binary y's and then plug the result into this Mma function: muffinLP[m_, n_, y_] := LinearProgramming[-IdentityMatrix[m n + 1][[m n + 1]], Join[Map[Total[IdentityMatrix[m n + 1][[#]]] &, Join[Transpose[#], #] &[Partition[Range[m n], n]]], Table[If[y[[i]] == 0, IdentityMatrix[m n + 1][[i]], IdentityMatrix[m n + 1][[i]] - IdentityMatrix[m n + 1][[m n + 1]]], {i, m n}]], Join[Table[{m, 0}, {n}], Table[{n, 0}, {m}], Map[If[# == 0, {0, 0}, {0, 1}] &, y]] , Method -> Simplex] y = {0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0}; Last[muffinLP[4, 13, y]] 11/6 "Method -> Simplex" option returns rational values. Veit