I've been doing some calculations using MIP (mixed integer programming) related to the muffin problem. I've made a few observations that have apparently sped up some of the calculations by factors of over 1000. Here they are: 0) As Veit Elser suggested (below uses his scaling), if one has a putative lower bound u of the best minimum piece size, then one can determine if u really is a lower bound by checking feasibility of the MIP: sum_i x[i,j] = m for all j sum_j x[i,j] = n for all i y[i,j] = 0 or 1, and u*y[i,j] <= x[i,j] <= b*y[i,j] for all i,j and b is an upper bound for x[i,j] (we can take b = min(m,n)). One can then search for the true value of u by a binary search (at least within a given epsilon), for example. 1) There is a lot of symmetry in this MIP -- we can make arbitrary permutations of the rows and columns. It turns out (and it isn't immediately obvious -- see the paper "Double Orderings of (0,1) matrices" by Adolf Mader and Otto Mutzbauer in Ars Combinatorica, v 61 (2001), pp 81-95 -- that one can assume that the rows and columns of the y matrix are lexicographically sorted -- to ensure that one just interprets them as binary numbers (so that's a linear form). This observation alone sped things up (usually the infeasible case at the boundary) by factors of 1000. 2) As I mentioned before, if you are given a value of the y matrix you can determine the best u for that matrix by solving the linear program: maximize u, subject to sum_i x[i,j] = m sum_j x[i,j] = n if y[i,j] = 0, then x[i,j] = 0 if y[i,j] = 1 then u <= x[i,j] Using this observation one can quickly find the optimal value (but see below) as follows: fix an epsilon > 0 start with u=1, repeat the following: 1) Test feasibility of the MIP above. If it's feasible, let y be the y matrix that the MIP program gives you. Then solve the above LP for the maximum u given that y -- it will always be >= the old value of u. If it's not feasible output the previous value of u. 2) Set u = u + epsilon, and go back to (1). Note that doing this will cut off the previous y solution. This procedure always climbs very quickly to what turns out to be the best value of u. Virtually all the time spent is in showing the infeasibility of optimal(u) + epsilon. Victor