Jack:

This 'Gold Standard' was calculated using a Monte-Carlo-Method followed by a Limited Search. However, as Richard already proved, there might be better solutions that actually fill the CD completely.

OTOH, there might not be a combination of songs for a given CD that actually fill the complete CD without gap. Thus, the rules specify that the gap has to be minimized without exceeding the media length.

I think that those two statements in the rules are pretty clear. It does not matter what the actual song indices are. As some of the song lists contain songs with the same length, one algorithm might choose song 17, whereas the other algorithm chooses song 18, if both songs have the same length. This is not a deciding factor.

Now, if you would like to go the LP way, yes, that is entirely possible. I think that both the MC and LS methods, however, might speed up the execution time compared to LP as you are seeding potential solutions. There are definitely different ways to solve the problem.

The solution should work in general, though the provided CD sets are a good cross-section.

Also, there cannot be two 'optimal' solutions with different gaps, as in that case one solution did not minimize the gap. Thus, you end up with just one 'optimal' solution.
_________________________
There are two types of vessels, submarines and targets.