Ah! Very cool. I'm glad someone wrote a search program :)
I'm flattered you call my comment a conjecture, when it was only really saying I wasn't convinced by your conjecture. But I'm glad we found an answer deciding it :)
Stupid question, if the search program finds a best answer, how does it show that's the best? Is there an obvious limit on something? Previously we seemed to have no way of clearly showing an answer _is_ the best, except by special-case proofs like writing-hawk's.
Stupid question, if the search program finds a best answer, how does it show that's the best?
Not a stupid question at all, since nobody else had thought of an answer to that problem!
Ian's basic idea is to start by (WLOG) assuming each input stick contributes at most one piece to each output stick (clearly if that's not true then you can merge fragments until it is without making your score worse). So now you have an n × m matrix of fragment lengths. Next, we want to treat the problem as a linear-programming optimisation exercise, trying to maximise one variable ("smallest nonzero matrix entry") under a collection of linear constraints (matrix entries all positive, rows and columns sum to the right thing). The trouble with that is that it's not actually a linear problem, since the objective criterion is nonlinear (taking min of all the matrix entries isn't a linear function). But if you knew the adjacency matrix (that is, you knew which input sticks contribute at all to which output sticks) it would be, because you could introduce the minimum frag length itself as an extra variable, so that some matrix elements were constrained to zero and others were of the form (min_frag + some positive extra value). So Ian simply iterates over all possible adjacency matrices and appeals to a linear-programming library to solve that optimisation problem for each one, and once he's gone through all possible matrices then he knows he's considered every answer!
Of course, then you optimise as hard as you can (by e.g. iterating over adjacency matrices in a sensible order that means you see the best ones first, stopping as soon as your matrix gets too dense because then some stick has to be cut into enough pieces that the smallest won't beat your existing best answer, parallelising over all the CPUs you can find, etc). But that's the basic idea.
Ah! Thank you. I couldn't see how the program would find it, I assumed it was obvious in some other way, but that approach makes sense even if it's brute force. It's considerable progress to be able to find optimal solutions at all.
Has any pattern emerged in the results found?
I wonder if it's possible to make any theoretical progress following the same approach? (But I'm just speculating I haven't even had time to start thinking about it yet.)
We're still working on getting the searcher to be both fast and accurate :-/ (I know it's missing at least one optimal solution in its current state.) When I have a large amount of data I more or less trust, I'll post it somewhere.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
I'm flattered you call my comment a conjecture, when it was only really saying I wasn't convinced by your conjecture. But I'm glad we found an answer deciding it :)
Stupid question, if the search program finds a best answer, how does it show that's the best? Is there an obvious limit on something? Previously we seemed to have no way of clearly showing an answer _is_ the best, except by special-case proofs like writing-hawk's.
Not a stupid question at all, since nobody else had thought of an answer to that problem!
Ian's basic idea is to start by (WLOG) assuming each input stick contributes at most one piece to each output stick (clearly if that's not true then you can merge fragments until it is without making your score worse). So now you have an n × m matrix of fragment lengths. Next, we want to treat the problem as a linear-programming optimisation exercise, trying to maximise one variable ("smallest nonzero matrix entry") under a collection of linear constraints (matrix entries all positive, rows and columns sum to the right thing). The trouble with that is that it's not actually a linear problem, since the objective criterion is nonlinear (taking min of all the matrix entries isn't a linear function). But if you knew the adjacency matrix (that is, you knew which input sticks contribute at all to which output sticks) it would be, because you could introduce the minimum frag length itself as an extra variable, so that some matrix elements were constrained to zero and others were of the form (min_frag + some positive extra value). So Ian simply iterates over all possible adjacency matrices and appeals to a linear-programming library to solve that optimisation problem for each one, and once he's gone through all possible matrices then he knows he's considered every answer!
Of course, then you optimise as hard as you can (by e.g. iterating over adjacency matrices in a sensible order that means you see the best ones first, stopping as soon as your matrix gets too dense because then some stick has to be cut into enough pieces that the smallest won't beat your existing best answer, parallelising over all the CPUs you can find, etc). But that's the basic idea.
Has any pattern emerged in the results found?
I wonder if it's possible to make any theoretical progress following the same approach? (But I'm just speculating I haven't even had time to start thinking about it yet.)
Oops! I hope it comes into shape.