Finding feasible schedules for a column generation algorithm

For a complex scheduling application, I need to generate a large number of feasible schedules for a class. Basically:

find x[1]…x[n] in {1..n}
under some precedence constraints x[i] < x[j]
all-different(x[1]…x[n])

MIP models are not very good for this (see http://yetanothermathprogrammingconsultant.blogspot.com/2011/10/sorting-by-mip.html). But a constraint programming model should be very easy to formulate and may perform quite good.

With Microsoft Solver Foundation I had to use some nondefault settings (VariableSelection=ConfictDriven) to get good performance. Genererating multiple solutions is easily performed with Solution.GetNext(). I don’t think it is easy to generate a subset of solutions that has a certain spread. The only thing that comes to mind is doing many calls to Solution.GetNext() and just using each K-th solution. As I don’t know in advance how many solutions there are, I am thinking about increasing K as we go.

For some classes I have simply a very large number of possible schedules (or differently put: not enough precedence constraints to reduce this number). To find a reasonable subset we could augment the above system of equations with a random objective. Now we need to restate the objective each cycle, so we no longer can use Solution.GetNext().

From what I see most modeling systems have available constraint programming support (e.g. Ilog OPL, MS Solver Foundation) or have something announced (AMPL, AIMMS).

Update: link from comment below: www.nicta.com.au/pub?doc=4759.