<h2>Computer search</h2>
<p>
-FIXME: describe our two search strategies.
-</p>
-
-<p>
-FIXME: stress that one is exhaustive but the other depends on a
-conjectured denominator bound.
-</p>
-
-<p>
-FIXME: the two strategies are good at different cases.
+We've done some computer searching to find the answers, or the
+probable answers, to small cases. We've got two different search
+strategies:
+</p>
+
+<p>
+<b>Iterate over adjacency matrices</b>. This strategy relies on the
+idea that we can assume, without loss of generality, that each input
+stick contributes at most one piece to each output stick. (This is the
+reverse of the assumption made in the proof of writinghawk's upper
+bound above! But fortunately they don't have to both be true at the
+same time.) So you could draw up an <i>n</i> × <i>m</i>
+matrix indicating which input sticks contributed to which output
+sticks. Given such a matrix, the problem of finding an optimal
+dissection <em>with that matrix</em> can be written as a linear
+programming problem. (One variable per dissection fragment is the
+obvious way, but then the objective function ‘take the minimum’ isn't
+linear. But if you add an extra variable showing the minimum size
+itself, and then make the other variables say by how much each other
+piece <em>exceeds</em> the minimum fragment, then it is linear.) So,
+in principle, we can just iterate over all the possible
+2<sup><i>nm</i></sup> adjacency matrices, and solve a linear
+programming problem for each one! Of course this takes exponential
+time, but it turns out reasonably practicable in small cases as long
+as you prune branches of the search tree early and often if you can
+easily show they can't give a result as good as the best one you
+already have.
+</p>
+
+<p>
+<b>ILP over possible stick partitions</b>. A completely different
+approach is to enumerate the various ways in which a stick can be
+partitioned into smaller pieces. (There are infinitely many, of
+course, but if you pick a denominator <i>d</i> and constrain to
+multiples of 1/<i>d</i> then that's not too bad.) This approach
+requires us to make a guess at the minimum fragment, so that we can
+enumerate partitions which use pieces no smaller than that. Once we
+have a list of the partition types for the input and output sticks, we
+express them as vectors showing how many pieces of what lengths they
+use, and then solve an integer-linear-programming problem to find
+combinations of them for which all the piece counts add up. Again, ILP
+is a computationally hard problem, but this algorithm seems to work OK
+in small cases because if you start your minimum fragment <em>too
+big</em> and lower it until you get a solution, you never
+have <em>too</em> many possible partitions to worry about.
+</p>
+
+<p>
+The first of these strategies is genuinely exhaustive: assuming no
+bugs in the search program, the algorithm must find the best possible
+dissection. The second, however, leaves open the possibility that a
+better dissection might exist using a denominator larger than any we
+had considered. Examination of the data we have so far strongly
+suggests the conjecture that no denominator larger than <i>n</i> is
+ever needed in an optimal dissection (though denominators larger
+than <i>m</i> can certainly occur), but we have no proof of that, and
+so results generated by the second search program cannot be considered
+reliable unless an upper bound proof confirms that they can't be
+beaten.
+</p>
+
+<p>
+Disregarding that weakness of the ILP approach, the two search
+algorithms complement each other well, because once <i>n</i> gets a
+bit larger we find that the matrix iteration algorithm works best for
+small <i>m</i>, while the ILP approach works best for large <i>m</i>
+(i.e. not much smaller than <i>n</i>). So running both has allowed us
+to collect a reasonable amount of data.
</p>
<p>
~ianmdlvl / matchsticks-search.git / blobdiff