Manuel Mall wrote:
What is still unclear to me is if it is worthwhile to implement this two pass approach, i.e. use INFINITE penalties first and relax later, or if it is good enough for 99.99% of cases just to start with INFINITE-1 penalties for mandatory keeps?
I think the second pass is necessary, in order to be sure that we are breaking a keep because there really isn't any other alternative. Otherwise, I'm sure that for each value < INFINITE we use, we could create a (contrived) example where the algorithm prefers breaking the keep instead of using a different, legal (but somewhat uglier) break, such behaving in a non-conformant way.
Reading again the specs, I even start wondering whether it would really be right to allow a break between objects tied by a keep constraint:
"Each keep condition must also be satisfied, except when this would cause a break condition or a stronger keep condition to fail to be satisfied. If not all of a set of keep conditions of equal strength can be satisfied, then some maximal satisfiable subset of conditions of that strength must be satisfied (together with all break conditions and maximal subsets of stronger keep conditions, if any)."
It seems to me that the prescribed behaviour requires a keep constraint with force = "always" to be satisfied *always* :-), even if this would mean having some overflowing content. More than this, even a keep with force = N could be broken only in order to satisfy a keep with greater force, and not to avoid an overflow.
I seem to recall that in Knuth's paper the author talks about a symbol he introduced in tex to represent a space that could be used as a line break in dire straits, having a penalty value = inf-1 (where inf was the special finite value representing infinity). Maybe we could similarly add some "soft-keep" extensions?