On 7/1/11 2:12 PM, "m...@apollinemike.com" <m...@apollinemike.com> wrote: > > I am a proponent of using mixed integer linear programming to solve these > issues. I believe that 100% of LilyPond's spacing could be rewritten as > constraints in a linear program, in which case the vertical and horizontal > spacing would all happen at the same time, and contingencies like this could > be built into the linear program.
I think I agree with you, in theory, that the music layout problem could be written as a mixed integer linear programming problem. But mixed integer linear programming problems are generally NP-hard, so I don't think that would buy us much. I also believe there is a practical problem as well -- when all the elements in a score are connected for purposes of spacing calculations, the space required grows quadratically, and I don't think it would be solvable on real computers, even if I'm wrong in my previous paragraph. But I haven't studied these things carefully enough to say that my beliefs are correct. I do think, however, that they are plausible. > That'd take a lot of time, but if people > were interested, I would love to work on this. It would also make LilyPond > more modular because cyclical dependencies could be simply sorted out in the > linear program instead of avoid through the nightmare to which Han-Wen alludes > when he correctly warns against source code fraught with exceptions. I believe the cyclical dependencies are actually an important characteristic of the problem, rather than an undesired result of the solution technique. But I'd be very happy to be shown wrong in this belief . Thanks, Carl _______________________________________________ lilypond-devel mailing list lilypond-devel@gnu.org https://lists.gnu.org/mailman/listinfo/lilypond-devel
