The SubDP.lng Model

Enumerate all feasible nonempty subsets of a partially ordered set

View the model
Download the model

A subset is feasible if for every task j in the subset, all predecessors of j are also in the subset;
This implements the algorithm on page 445 of:
Schrage, L. and K. Baker(1978),"Dynamic Programming Solution of Sequencing Problems with Precedence Constraints", Operations Research, vol. 26, no. 3, pp. 444-449;

Keywords:

Enumeration | Dynamic Programming | Partial Ordered Set | Subset Enumeration |