Constraint Programming Notes

Constraint Programming: Systematic Search for Constraint Satisfaction Problems

Learning Objectives

• Understand systematic search for constraint satisfaction problems.
• Understand the applications of constraint satisfaction problems in manufacturing.

Constraint Satisfaction Problems (CSPs)

• CSPs are satisfaction problems where the primary task is to find a feasible solution.
• A feasible solution is one that satisfies all given constraints.

Local Search vs. Systematic Search

• Local Search:
  • Advantage: Often finds a feasible solution quickly.
  • Disadvantage: May not detect if no feasible solution exists unless run with restarts for a long time.
  • Dilemma: Difficult to determine when to stop searching if a solution isn't immediately found.
• Systematic Search:
  • Enumerates all possible solutions and checks each one for feasibility.
  • Stops upon finding a feasible solution or after exhausting all possibilities.
  • Can definitively determine if no feasible solution exists (assuming a finite number of solutions).
  • Disadvantage: Can have long run times due to the typically large number of solutions.
• Applies to both satisfaction and optimization problems.

Advantages of Systematic Search

• Clear termination criterion: either finds a solution or proves none exists.

Map Coloring Problem Example

• Given: A country divided into states (e.g., X, Y, Z).
• Goal: Assign a color to each state such that neighboring states (sharing a non-point border) have different colors.

Modeling as a CSP

• Variables: Each state is represented by a variable (e.g., X, Y, Z).
• Domain: The set of possible colors for each variable (e.g., two colors: red and green).
• Constraints: Neighboring states must have different colors (variables representing neighboring states must have different values).
• Example: A map coloring problem may have no feasible solution with only two colors.

Systematic Search Approach

• Enumerate all possible solutions (complete assignments of values to variables).
• Build a tree to systematically generate all solutions.
  • Start with an empty assignment at the root.
  • At each node, select an unassigned variable and enumerate all possible values for it, creating child nodes for each assignment.
  • Continue until all variables are assigned (leaf nodes represent complete solutions).

Tree Traversal and Solution Checking

• Traverse the tree using a depth-first search.
• At each leaf node (complete assignment), check if the solution is feasible (satisfies all constraints).
  • If feasible, output the solution and stop (if only one solution is needed).
  • If no feasible solution is found after traversing the entire tree, declare that no solution exists.

Choices in Tree Generation

• Variable Selection:
  • At each node, choose which unassigned variable to assign a value to next.
  • Different choices can significantly impact the efficiency of the search.
  • Good Rule: Choose the variable with the smallest number of possible values.
  • If multiple variables have the same smallest number of values, choose the one involved in the largest number of constraints with other unassigned variables.
• Value Ordering:
  • Once a variable is chosen, decide the order in which to enumerate its possible values.
  • Good Rule: Choose the value that rules out the fewest values for the variables that the chosen variable has constraints with and that does not make the constraint satisfaction problem unsolvable.
  • Consider the impact on neighboring variables (variables with constraints).
  • Example: If assigning red to X rules out red for both Y and Z, evaluate this choice based on the overall impact.

Applications in Manufacturing

• Design:
  • Constraint satisfaction problems are used in design processes to manage design constraints.
  • Example: Trade-offs in product design (e.g., enhancing a product in only one of two possible ways due to cost constraints).
  • Applications: Eco-design of a hybrid passenger ferry, design of gear wheels.