The CLP Procedure
-
Overview
-
Getting Started
-
Syntax
-
Details
-
ExamplesLogic-Based PuzzlesAlphabet Blocks ProblemWork-Shift Scheduling ProblemA Nonlinear Optimization ProblemCar Painting ProblemScene Allocation ProblemCar Sequencing ProblemRound-Robin ProblemResource-Constrained Scheduling with Nonstandard Temporal ConstraintsScheduling with Alternate Resources10×10 Job Shop Scheduling ProblemScheduling a Major Basketball ConferenceBalanced Incomplete Block DesignProgressive Party ProblemStatement and Option Cross-Reference Table
- References
- 3.1 Logic-Based Puzzles
- 3.2 Alphabet Blocks Problem
- 3.3 Work-Shift Scheduling Problem
- 3.4 A Nonlinear Optimization Problem
- 3.5 Car Painting Problem
- 3.6 Scene Allocation Problem
- 3.7 Car Sequencing Problem
- 3.8 Round-Robin Problem
- 3.9 Resource-Constrained Scheduling with Nonstandard Temporal Constraints
- 3.10 Scheduling with Alternate Resources
- 3.11 10×10 Job Shop Scheduling Problem
- 3.12 Scheduling a Major Basketball Conference
- 3.13 Balanced Incomplete Block Design
- 3.14 Progressive Party Problem
- Statement and Option Cross-Reference Table
This section contains several examples that illustrate the capabilities of the different logical constraints and showcase a variety of problems that the CLP procedure can solve. The following examples feature a standard constraint satisfaction problem (CSP):
-
Logic-Based Puzzles illustrates the capabilities of the ALLDIFFERENT constraint in solving a popular logical puzzle, the Sudoku. This example also contains a variant of Sudoku that illustrates the capabilities of the GCC constraint. Finally, a Magic Square puzzle demonstrates the use of the EVALVARSEL= option.
-
Alphabet Blocks Problem illustrates how to use the GCC constraint to solve 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 to use the ELEMENT constraint to represent nonlinear functions and nonstandard variable domains, including noncontiguous domains. This example also demonstrates how to specify an objective function in the Constraint data set.
-
Car Painting Problem involves limited sequencing of cars in an assembly process in order to minimize the number of paint purgings; it features the REIFY constraint.
-
Scene Allocation Problem illustrates how to schedule the shooting of different movie scenes 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.
-
Balanced Incomplete Block Design illustrates how to use the LEXICO constraint to break symmetries in generating balanced incomplete block designs (BIBDs), a standard combinatorial problem from design theory.
-
Progressive Party Problem illustrates how to use the PACK constraint to solve the progressive party problem, a well-known constraint programming problem in which crews of various sizes must be assigned to boats of various capacities for several rounds of parties.
The following 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.