Examples: CLP Procedure

This section contains several examples that illustrate the capabilities of the different logical constraints and showcase a variety of problems that can be solved by the CLP procedure. The first seven examples feature a standard constraint satisfaction problem (CSP):

• Logic-Based Puzzles illustrates the capabilities of the ALLDIFFERENT constraint in solving the popular logical puzzle, Sudoku. This example also contains a variant of Sudoku which illustrates the capabilities of the GCC constraint.

• Alphabet Blocks Problem illustrates the use of the GCC constraint in solving the alphabet blocks problem, a popular combinatorial problem.

• Work-Shift Scheduling Problem illustrates the capabilities of the ELEMENT constraint in modeling the cost information in a work-shift scheduling problem in order to find a minimum cost schedule.

• A Nonlinear Optimization Problem illustrates how you can use the ELEMENT constraint to represent nonlinear functions and nonstandard variable domains, including noncontiguous domains.

• Car Painting Problem involves limited sequencing of the cars in an assembly process in order to minimize the number of paint purgings and features the REIFY constraint.

• Scene Allocation Problem schedules the shooting of different scenes of a movie in order to minimize production costs. This problem uses the GCC and LINEAR constraints.

• Car Sequencing Problem relates to sequencing the cars on an assembly line with workstations for installing specific options subject to the demand constraints for each set of options and the capacity constraints of each workstation.

The next four examples feature scheduling CSPs and use the scheduling constraints in the CLP procedure:

• Round-Robin Problem illustrates solving a single round robin tournament.

• Resource-Constrained Scheduling with Nonstandard Temporal Constraints illustrates nonstandard precedence constraints in scheduling the construction of a bridge.

• Scheduling with Alternate Resources illustrates a job scheduling problem with alternate resources. An optimal solution is determined by activating the edge-finding consistency techniques for this example.

• 10×10 Job Shop Scheduling Problem illustrates a well-known 10×10 job shop scheduling problem and features edge-finding along with the edge-finding extensions 'not first' and 'not last' in order to determine optimality.

It is often possible to formulate a problem both as a standard CSP and also as a scheduling CSP. Depending on the nature of the constraints, it might even be more advantageous to formulate a scheduling problem as a standard CSP and vice versa:

• Scheduling a Major Basketball Conference illustrates this concept by modeling the problem of scheduling a major basketball conference as a standard CSP. The ELEMENT constraint plays a key role in this particular example.