Constraint Satisfaction Problems and Encoding Techniques

Author

Your Name

Published

February 5, 2025

Introduction

This document explores various Constraint Satisfaction Problems (CSPs) and their encoding techniques, with a focus on their implementation using MiniZinc. We will delve into different modeling approaches, including array-based and Boolean matrix-based methods, and illustrate their applications through real-world examples such as timetabling and error-correcting codes. The primary objectives are to:

Understand how to effectively model CSPs.
Learn about symmetry breaking and optimization techniques.
Apply these concepts to practical problems.

Key concepts discussed include the use of different constraint solvers, the encoding of various constraints, and the trade-offs inherent in different modeling approaches. This document aims to provide a comprehensive overview of these topics, enhancing the reader’s ability to tackle complex combinatorial problems.

Constraint Satisfaction Problems (CSPs): Problems where solutions must satisfy a set of constraints.
MiniZinc: A high-level constraint modeling language.
Array-Based Modeling: Using arrays to represent assignments.
Boolean Matrix Modeling: Using Boolean matrices to represent assignments.
Symmetry Breaking: Techniques to reduce search space by eliminating symmetric solutions.
Optimization Techniques: Methods to find the best solution according to a given objective function.
Constraint Solvers: Software tools that find solutions to CSPs.

Time Tabling Problem

General Idea

The timetabling problem is a classic combinatorial optimization challenge that involves assigning a set of $n$ workers to a set of $s$ slots, subject to various constraints. This problem is highly versatile and applicable to numerous real-world scenarios, such as scheduling employee shifts, allocating tasks to machines, or managing resource allocation. The core challenge lies in satisfying all constraints while optimizing some objective, such as minimizing conflicts or maximizing resource utilization.

Modeling Approaches

Approach 1: Array-Based Assignment

This approach uses an array $W$ of size $n$, where each element $W[i]$ represents the slot assigned to worker $i$. The domain of each variable $W[i]$ is the set of available slots $\{1, 2, \dots, s\}$. This method is straightforward and intuitive, making it suitable for problems where each worker is assigned to exactly one slot.

Data Structure: An array $W$ of size $n$.
Variables: $W[i] \in \{1, 2, \dots, s\}$ for $i = 1, 2, \dots, n$.
Assignment: $W[i] = j$ signifies that worker $i$ is assigned to slot $j$.

Example Constraints:

Monotonic Assignment: The slots assigned to workers are monotonically increasing, i.e., $W[i] \le W[i+1]$ for $i = 1, 2, \dots, n-1$. This constraint introduces an ordering among the assignments.
Different Slots for Specific Pairs: If the sum of the indices of two workers is a multiple of 3, they must be assigned to different slots, i.e., if $i + j \equiv 0 \pmod{3}$, then $W[i] \ne W[j]$. This constraint introduces a dependency between the assignments of certain pairs of workers.
At Most Two Workers per Slot: No more than two workers can be assigned to the same slot. This constraint limits the capacity of each slot.

Approach 2: Boolean Matrix Assignment

This approach utilizes a Boolean matrix $M$ of size $n \times s$, where $M[i, j] = 1$ if worker $i$ is assigned to slot $j$, and $M[i, j] = 0$ otherwise. This method is more general and can handle scenarios where workers can be assigned to multiple slots.

Data Structure: A Boolean matrix $M$ of size $n \times s$.
Variables: $M[i, j] \in \{0, 1\}$ for $i = 1, 2, \dots, n$ and $j = 1, 2, \dots, s$.
Assignment: $M[i, j] = 1$ indicates that worker $i$ is assigned to slot $j$.

Constraints:

Each Worker Assigned to Exactly One Slot: Each worker must be assigned to exactly one slot, i.e., $\sum_{j=1}^s M[i, j] = 1$ for $i = 1, 2, \dots, n$. This constraint ensures that every worker is assigned.
Monotonic Assignment: For any two workers $i$ and $i+1$, if worker $i$ is assigned to slot $k$ and worker $i+1$ is assigned to slot $j$, then if $j < k$, it cannot be the case that $M[i,k] = 1$ and $M[i+1,j] = 1$, i.e., $M[i, k] + M[i+1, j] \le 1$ for $i = 1, 2, \dots, n-1$ and $j < k$. This constraint enforces an ordering on the assignments.
Different Slots for Specific Pairs: If the sum of the indices of two workers is a multiple of 3, they must be assigned to different slots, i.e., if $i + j \equiv 0 \pmod{3}$, then $M[i, k] + M[j, k] \le 1$ for all $k$. This constraint ensures that certain pairs of workers are not assigned to the same slot.
At Most Two Workers per Slot: No more than two workers can be assigned to the same slot, i.e., $\sum_{i=1}^n M[i, j] \le 2$ for $j = 1, 2, \dots, s$. This constraint limits the capacity of each slot.

Approach 3: Reverse Assignment (Slots to Workers)

This approach reverses the perspective of the first approach, assigning slots to workers instead of workers to slots. It is particularly suitable for injective problems where each slot is assigned to at most one worker. This approach is symmetric to the array-based assignment approach and can be useful in specific scenarios.

Comparison of Approaches

Approach 1 (Array-Based) is simple and efficient when each worker is assigned to exactly one slot. It is intuitive and easy to implement.
Approach 2 (Boolean Matrix) is more general, allowing for scenarios where workers can be assigned to multiple slots. However, it requires additional constraints to enforce the desired assignment properties.
Approach 3 (Reverse Assignment) is useful for injective problems and offers a symmetric perspective to the array-based approach. The choice between Approach 1 and Approach 3 often depends on the specific constraints and problem structure.

MiniZinc Encoding

Approach 1: Array-Based Encoding

int: n = 10; % Number of workers
int: s = 7;  % Number of slots
array[1..n] of var 1..s: W; % Assignment of workers to slots

% Constraints
constraint forall(i in 1..n-1)(W[i] <= W[i+1]); % Monotonic assignment
constraint forall(i, j in 1..n where i < j)(if (i+j) mod 3 == 0 then W[i] != W[j] endif); % Different slots for specific pairs
constraint forall(k in 1..s)(sum(i in 1..n)(bool2int(W[i] == k)) <= 2); % At most two workers per slot

solve satisfy;

Approach 2: Boolean Matrix Encoding

int: n = 10; % Number of workers
int: s = 7;  % Number of slots
array[1..n, 1..s] of var bool: M; % Boolean matrix for assignment

% Constraints
constraint forall(i in 1..n)(sum(j in 1..s)(M[i, j]) == 1); % Each worker is assigned to exactly one slot
constraint forall(i in 1..n-1, j in 1..s, k in 1..s where k > j)(M[i, k] + M[i+1, j] <= 1); % Monotonic assignment
constraint forall(i, j in 1..n where i < j, k in 1..s)(if (i+j) mod 3 == 0 then M[i, k] + M[j, k] <= 1 endif); % Different slots for specific pairs
constraint forall(k in 1..s)(sum(i in 1..n)(M[i, k]) <= 2); % At most two workers per slot

solve satisfy;

Telethon Example

Problem Description

The Telethon problem involves assigning $n$ runners to $n$ slots, where each runner has a preference for each slot. The preferences are categorized as follows:

0: Not Available: The runner cannot be assigned to this slot.
1: Available but Not Preferred: The runner can be assigned to this slot, but it is not their first choice.
2: Preferred: The runner prefers to be assigned to this slot.

The objective is to minimize the number of assignments where runners are assigned to slots they are not happy with, i.e., slots with preference level 1. This problem is a practical example of a scheduling problem with preferences, and it can be modeled as a Constraint Optimization Problem (COP).

MiniZinc Encoding

int: n = 24; % Number of runners/slots
set of int: slots = 1..n;
array[slots, slots] of int: preferences; % Input preferences
array[slots] of var slots: assignment; % Assignment of runners to slots

% Hard constraint: If preference is 0, runner cannot be assigned to that slot
constraint forall(i, j in slots)(if preferences[i, j] == 0 then assignment[i] != j endif);

% Ensure a permutation (all different)
constraint all_different(assignment);

% Cost function: Minimize the number of unhappy assignments
var int: cost = sum(i, j in slots)(bool2int(assignment[i] == j /\ preferences[i, j] == 1));

solve minimize cost;

Explanation:

Input Data:
- n: The number of runners and slots (set to 24 in this example).
- slots: A set representing the available slots, defined as 1..n.
- preferences: A 2D array storing the preference level of each runner for each slot.
Decision Variable:
- assignment: An array representing the assignment of runners to slots. assignment[i] = j means runner i is assigned to slot j.
Constraints:
- Hard Constraint: If a runner’s preference for a slot is 0, they cannot be assigned to that slot.
- Permutation Constraint: The all_different constraint ensures that each runner is assigned to a unique slot, forming a permutation.
Cost Function:
- cost: The objective function to be minimized. It counts the number of assignments where the preference level is 1 (available but not preferred).
Solving:
- solve minimize cost: Instructs the solver to find an assignment that minimizes the total cost.

This encoding effectively captures the Telethon problem, allowing us to find an optimal assignment that respects the runners’ preferences while ensuring a valid schedule.

Graphical representation of the Telethon problem with runners and slots.

1 illustrates the assignment of runners to slots, where each arrow represents an assignment. The goal is to find an assignment that minimizes the cost function, which counts the number of assignments to slots with preference level 1.

Error Correcting Codes

Problem Description

The error-correcting code problem involves generating a set of $k$ code words, each of length $n$, such that the Hamming distance between any two code words is at least $d$. This problem is crucial in ensuring reliable data transmission and storage, as it allows for the detection and correction of errors introduced during transmission or storage.

Definition 1 (Hamming Distance).

The Hamming distance between two words of equal length is the number of positions at which the corresponding symbols are different. For binary words, this is equivalent to the number of positions where the bits differ.

MiniZinc Encoding

int: n = 6;  % Length of each word
int: k = 4;  % Number of words
int: d = 3;  % Minimum distance
array[1..k, 1..n] of var bool: code; % Boolean matrix representing the code

% Constraint: Ensure minimum distance between words
constraint forall(i, j in 1..k where i < j)(sum(l in 1..n)(abs(bool2int(code[i, l]) - bool2int(code[j, l]))) >= d);

% Symmetry breaking: Force the first row to be all zeros
constraint forall(l in 1..n)(code[1, l] == false);

% Lexicographical ordering constraint
constraint forall(i in 1..k-1)(code[i] < code[i+1]);

solve satisfy;

Explanation:

Input Data:
- n: The length of each code word (set to 6 in this example).
- k: The number of code words (set to 4 in this example).
- d: The minimum Hamming distance between any two code words (set to 3 in this example).
Decision Variable:
- code: A 2D Boolean array representing the code words. code[i, l] is true if the $l$-th bit of the $i$-th code word is 1, and false otherwise.
Constraints:
- Minimum Distance Constraint: Ensures that the Hamming distance between any two code words is at least d. The Hamming distance is computed by summing the absolute differences of the corresponding bits.
- Symmetry Breaking Constraint: Forces the first code word to be all zeros. This is a symmetry-breaking technique that reduces the search space without losing generality.
- Lexicographical Ordering Constraint: Ensures that the code words are lexicographically ordered. This further reduces the search space by eliminating symmetric solutions.
Solving:
- solve satisfy: Instructs the solver to find a solution that satisfies all the constraints.

Custom Lexicographical Ordering

predicate my_lex(array[int] of var bool: first, array[int] of var bool: second) =
  let {
    int: len = length(first);
    array[1..len] of var bool: temp;
  } in
  temp[1] == true /\
  forall(j in 1..len-1)(
    temp[len-j] == (first[len-j] < second[len-j] \/ (first[len-j] == second[len-j] /\ temp[len-j+1]))
  ) /\
  temp[len] == true;

% Using custom lexicographical ordering
constraint forall(i in 1..k-1)(my_lex(code[i], code[i+1]));

Explanation:

Predicate Definition:
- my_lex: A custom predicate that defines lexicographical ordering between two Boolean arrays.
- len: The length of the input arrays.
- temp: A temporary Boolean array used to build the lexicographical ordering constraint.
Lexicographical Ordering Logic:
- The predicate uses a temporary array temp to enforce the lexicographical order.
- temp[1] is initialized to true.
- For each position j from 1 to len-1, temp[len-j] is set to true if first[len-j] is less than second[len-j], or if they are equal and temp[len-j+1] is true.
- temp[len] must also be true.
Usage:
- The my_lex predicate is used to enforce lexicographical ordering between consecutive code words.

This custom predicate provides an alternative way to enforce lexicographical ordering, which can be useful for understanding how such constraints can be built from basic logical operations.

Graphical representation of error-correcting code words and their Hamming distance.

2 illustrates the concept of Hamming distance between two code words. The dashed red lines indicate the positions where the bits are compared to calculate the Hamming distance.

Knapsack Problem

Problem Description

The knapsack problem is a classic combinatorial optimization problem where, given a set of items, each with a weight and a value, the goal is to determine the number of each item to include in a collection such that the total weight is less than or equal to a given limit (the capacity of the knapsack), and the total value is as large as possible. This problem has numerous applications in resource allocation, logistics, and portfolio management. This version of the knapsack problem is an extension where we can select multiple instances of the same item, not just 0 or 1.

MiniZinc Encoding

int: n = 12; % Number of items
int: space = 100; % Maximum weight capacity
array[1..n] of int: weight = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]; % Weight of each item
array[1..n] of int: cost = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095]; % Cost of each item
array[1..n] of var 0..100: x; % Number of each item to include

% Constraint: Total weight must not exceed the capacity
constraint sum(i in 1..n)(x[i] * weight[i]) <= space;

% Objective: Maximize the total cost
var int: profit = sum(i in 1..n)(x[i] * cost[i]);
solve maximize profit;

Explanation:

Input Data:
- n: The number of items (set to 12 in this example).
- space: The maximum weight capacity of the knapsack (set to 100 in this example).
- weight: An array containing the weight of each item.
- cost: An array containing the value (or cost) of each item.
Decision Variable:
- x: An array of variables representing the number of each item to include in the knapsack. The domain of each variable is 0..100, meaning we can select between 0 and 100 instances of each item.
Constraints:
- Capacity Constraint: The total weight of the selected items must not exceed the knapsack’s capacity (space).
Objective Function:
- profit: The total value of the selected items, which is to be maximized.
Solving:
- solve maximize profit: Instructs the solver to find an assignment that maximizes the total profit while satisfying the capacity constraint.

Graphical representation of the knapsack problem with items, weights, costs, and quantities.

3 provides a visual representation of the knapsack problem, showing items with their respective weights, costs, and the quantities to be selected. The knapsack represents the capacity constraint, which must not be exceeded by the total weight of the selected items.

Course Timetabling Example

Problem Description

The course timetabling problem involves scheduling a set of courses over a given number of periods, considering various constraints such as teacher availability, course conflicts, and the required number of periods for each course. This problem is a complex combinatorial challenge that arises in educational institutions and other settings where resources must be allocated efficiently over time. In this specific example, we aim to schedule five courses over 20 periods, distributed across five days with four periods per day, in two available rooms.

Input Data

The input data for this problem includes:

Courses: 5 courses to be scheduled.
Periods: 20 periods available for scheduling (e.g., four periods per day for five days).
Rooms: 2 rooms available for scheduling courses.
Availability: A matrix indicating when each course can be scheduled. This matrix specifies the periods when a course is available, typically based on teacher availability or other constraints.
Conflict: A symmetric matrix indicating which courses cannot be scheduled simultaneously. This matrix captures conflicts arising from shared teachers, students, or other resource limitations.
Requirement: An array specifying the number of periods required for each course.

MiniZinc Encoding

int: nCourses = 5;
int: nPeriods = 20;
int: nRooms = 2;
array[1..nCourses, 1..nPeriods] of int: available;
array[1..nCourses, 1..nCourses] of int: conflict;
array[1..nCourses] of int: requirement;
array[1..nCourses, 1..nPeriods] of var bool: timetable;

% Constraint: At most one of two conflicting courses can be assigned in the same period
constraint forall(c1, c2 in 1..nCourses where conflict[c1, c2] == 1, p in 1..nPeriods)(timetable[c1, p] + timetable[c2, p] <= 1);

% Constraint: If a course is not available at a period, it cannot be assigned
constraint forall(c in 1..nCourses, p in 1..nPeriods)(if available[c, p] == 0 then timetable[c, p] == false endif);

% Constraint: At most two courses can be scheduled in any period
constraint forall(p in 1..nPeriods)(sum(c in 1..nCourses)(timetable[c, p]) <= nRooms);

% Constraint: The number of periods assigned to each course must meet the requirement
constraint forall(c in 1..nCourses)(sum(p in 1..nPeriods)(timetable[c, p]) == requirement[c]);

solve satisfy;

Explanation:

Input Data:
- nCourses: The number of courses to be scheduled (set to 5).
- nPeriods: The number of available time periods (set to 20).
- nRooms: The number of available rooms(set to 2).
- available: A 2D array indicating the availability of each course at each period.
- conflict: A 2D symmetric array indicating which courses cannot be scheduled simultaneously.
- requirement: An array specifying the number of periods required for each course.
Decision Variable:
- timetable: A 2D Boolean array representing the schedule. timetable[c, p] is true if course c is scheduled in period p, and false otherwise.
Constraints:
- Conflict Constraint: Ensures that at most one of two conflicting courses is scheduled in the same period.
- Availability Constraint: Ensures that a course is not scheduled in a period when it is not available.
- Room Capacity Constraint: Ensures that at most two courses are scheduled in any given period (since there are two rooms).
- Requirement Constraint: Ensures that each course is assigned the required number of periods.
Solving:
- solve satisfy: Instructs the solver to find a schedule that satisfies all the constraints.

Graphical representation of the course timetabling problem with courses, periods, and rooms.

4 illustrates the course timetabling problem, showing the courses, periods, and rooms. The goal is to find a valid schedule that satisfies all constraints, including availability, conflicts, and requirements.

Conclusion

This document has presented a comprehensive overview of various Constraint Satisfaction Problems (CSPs) and their encoding techniques using MiniZinc. We have explored different modeling approaches, including array-based and Boolean matrix-based methods, and illustrated their applications through practical examples such as timetabling, error-correcting codes, and the knapsack problem. Key takeaways from this exploration include:

Importance of Modeling Approach: The choice of an appropriate modeling approach (e.g., array-based vs. Boolean matrix-based) significantly impacts the efficiency and clarity of the solution.
Symmetry Breaking: Symmetry breaking techniques, such as forcing the first row to be all zeros in the error-correcting code problem, are crucial for reducing the search space and improving solver performance.
Optimization Techniques: Optimization techniques, such as minimizing the cost function in the Telethon problem, allow us to find the best solution according to a given objective.
Practical Applications: CSPs have wide-ranging applications in real-world scenarios, including scheduling, resource allocation, and data transmission.

Different modeling approaches (array-based, Boolean matrix) have different strengths and weaknesses.
Symmetry breaking is essential for efficient problem-solving.
Optimization techniques allow us to find the best solution according to a given objective.
CSPs have numerous real-world applications.

For future lectures and further study, we can delve deeper into advanced constraint programming techniques, explore other types of CSPs, and discuss how to handle more complex constraints and optimization criteria. Additionally, we can consider the following questions to guide our future explorations:

Efficiency of MiniZinc Models: How can we further improve the efficiency of our MiniZinc models, including the choice of appropriate data structures, constraints, and search strategies?
Real-World Applications: What are some other real-world applications of CSPs, and how can we model them effectively using MiniZinc or other constraint programming languages?
Integration with Other Techniques: How can we integrate constraint programming with other optimization techniques, such as integer programming, metaheuristics, or machine learning, to tackle more complex and challenging problems?

By addressing these questions, we can enhance our understanding of constraint satisfaction problems and their applications, and develop more effective solutions for complex real-world scenarios. The journey into constraint programming is ongoing, and there are always new techniques and applications to explore.

--- title: "Constraint Satisfaction Problems and Encoding Techniques" author: "Your Name" date: "2025-02-05" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction {#sec:introduction} This document explores various Constraint Satisfaction Problems (CSPs) and their encoding techniques, with a focus on their implementation using MiniZinc. We will delve into different modeling approaches, including array-based and Boolean matrix-based methods, and illustrate their applications through real-world examples such as timetabling and error-correcting codes. The primary objectives are to: - Understand how to effectively model CSPs. - Learn about symmetry breaking and optimization techniques. - Apply these concepts to practical problems. Key concepts discussed include the use of different constraint solvers, the encoding of various constraints, and the trade-offs inherent in different modeling approaches. This document aims to provide a comprehensive overview of these topics, enhancing the reader's ability to tackle complex combinatorial problems. ::: tcolorbox - **Constraint Satisfaction Problems (CSPs)**: Problems where solutions must satisfy a set of constraints. - **MiniZinc**: A high-level constraint modeling language. - **Array-Based Modeling**: Using arrays to represent assignments. - **Boolean Matrix Modeling**: Using Boolean matrices to represent assignments. - **Symmetry Breaking**: Techniques to reduce search space by eliminating symmetric solutions. - **Optimization Techniques**: Methods to find the best solution according to a given objective function. - **Constraint Solvers**: Software tools that find solutions to CSPs. ::: []{#sec:introduction label="sec:introduction"} # Time Tabling Problem {#sec:timetabling} ## General Idea {#subsec:timetabling_general} The timetabling problem is a classic combinatorial optimization challenge that involves assigning a set of $n$ workers to a set of $s$ slots, subject to various constraints. This problem is highly versatile and applicable to numerous real-world scenarios, such as scheduling employee shifts, allocating tasks to machines, or managing resource allocation. The core challenge lies in satisfying all constraints while optimizing some objective, such as minimizing conflicts or maximizing resource utilization. ## Modeling Approaches {#subsec:timetabling_modeling} ### Approach 1: Array-Based Assignment {#subsubsec:array_based_assignment} This approach uses an array $W$ of size $n$, where each element $W[i]$ represents the slot assigned to worker $i$. The domain of each variable $W[i]$ is the set of available slots $\{1, 2, \dots, s\}$. This method is straightforward and intuitive, making it suitable for problems where each worker is assigned to exactly one slot. - **Data Structure**: An array $W$ of size $n$. - **Variables**: $W[i] \in \{1, 2, \dots, s\}$ for $i = 1, 2, \dots, n$. - **Assignment**: $W[i] = j$ signifies that worker $i$ is assigned to slot $j$. **Example Constraints:** 1. **Monotonic Assignment**: The slots assigned to workers are monotonically increasing, i.e., $W[i] \le W[i+1]$ for $i = 1, 2, \dots, n-1$. This constraint introduces an ordering among the assignments. 2. **Different Slots for Specific Pairs**: If the sum of the indices of two workers is a multiple of 3, they must be assigned to different slots, i.e., if $i + j \equiv 0 \pmod{3}$, then $W[i] \ne W[j]$. This constraint introduces a dependency between the assignments of certain pairs of workers. 3. **At Most Two Workers per Slot**: No more than two workers can be assigned to the same slot. This constraint limits the capacity of each slot. ### Approach 2: Boolean Matrix Assignment {#subsubsec:boolean_matrix_assignment} This approach utilizes a Boolean matrix $M$ of size $n \times s$, where $M[i, j] = 1$ if worker $i$ is assigned to slot $j$, and $M[i, j] = 0$ otherwise. This method is more general and can handle scenarios where workers can be assigned to multiple slots. - **Data Structure**: A Boolean matrix $M$ of size $n \times s$. - **Variables**: $M[i, j] \in \{0, 1\}$ for $i = 1, 2, \dots, n$ and $j = 1, 2, \dots, s$. - **Assignment**: $M[i, j] = 1$ indicates that worker $i$ is assigned to slot $j$. **Constraints:** 1. **Each Worker Assigned to Exactly One Slot**: Each worker must be assigned to exactly one slot, i.e., $\sum_{j=1}^s M[i, j] = 1$ for $i = 1, 2, \dots, n$. This constraint ensures that every worker is assigned. 2. **Monotonic Assignment**: For any two workers $i$ and $i+1$, if worker $i$ is assigned to slot $k$ and worker $i+1$ is assigned to slot $j$, then if $j < k$, it cannot be the case that $M[i,k] = 1$ and $M[i+1,j] = 1$, i.e., $M[i, k] + M[i+1, j] \le 1$ for $i = 1, 2, \dots, n-1$ and $j < k$. This constraint enforces an ordering on the assignments. 3. **Different Slots for Specific Pairs**: If the sum of the indices of two workers is a multiple of 3, they must be assigned to different slots, i.e., if $i + j \equiv 0 \pmod{3}$, then $M[i, k] + M[j, k] \le 1$ for all $k$. This constraint ensures that certain pairs of workers are not assigned to the same slot. 4. **At Most Two Workers per Slot**: No more than two workers can be assigned to the same slot, i.e., $\sum_{i=1}^n M[i, j] \le 2$ for $j = 1, 2, \dots, s$. This constraint limits the capacity of each slot. ### Approach 3: Reverse Assignment (Slots to Workers) {#subsubsec:reverse_assignment} This approach reverses the perspective of the first approach, assigning slots to workers instead of workers to slots. It is particularly suitable for injective problems where each slot is assigned to at most one worker. This approach is symmetric to the array-based assignment approach and can be useful in specific scenarios. ## Comparison of Approaches {#subsec:comparison_approaches} - **Approach 1 (Array-Based)** is simple and efficient when each worker is assigned to exactly one slot. It is intuitive and easy to implement. - **Approach 2 (Boolean Matrix)** is more general, allowing for scenarios where workers can be assigned to multiple slots. However, it requires additional constraints to enforce the desired assignment properties. - **Approach 3 (Reverse Assignment)** is useful for injective problems and offers a symmetric perspective to the array-based approach. The choice between Approach 1 and Approach 3 often depends on the specific constraints and problem structure. ## MiniZinc Encoding {#subsec:minizinc_encoding} ### Approach 1: Array-Based Encoding {#subsubsec:array_based_minizinc} ::: tcolorbox int: n = 10; % Number of workers int: s = 7; % Number of slots array[1..n] of var 1..s: W; % Assignment of workers to slots % Constraints constraint forall(i in 1..n-1)(W[i] <= W[i+1]); % Monotonic assignment constraint forall(i, j in 1..n where i < j)(if (i+j) mod 3 == 0 then W[i] != W[j] endif); % Different slots for specific pairs constraint forall(k in 1..s)(sum(i in 1..n)(bool2int(W[i] == k)) <= 2); % At most two workers per slot solve satisfy; ::: []{#lst:array_based_minizinc label="lst:array_based_minizinc"} ### Approach 2: Boolean Matrix Encoding {#subsubsec:boolean_matrix_minizinc} ::: tcolorbox int: n = 10; % Number of workers int: s = 7; % Number of slots array[1..n, 1..s] of var bool: M; % Boolean matrix for assignment % Constraints constraint forall(i in 1..n)(sum(j in 1..s)(M[i, j]) == 1); % Each worker is assigned to exactly one slot constraint forall(i in 1..n-1, j in 1..s, k in 1..s where k > j)(M[i, k] + M[i+1, j] <= 1); % Monotonic assignment constraint forall(i, j in 1..n where i < j, k in 1..s)(if (i+j) mod 3 == 0 then M[i, k] + M[j, k] <= 1 endif); % Different slots for specific pairs constraint forall(k in 1..s)(sum(i in 1..n)(M[i, k]) <= 2); % At most two workers per slot solve satisfy; ::: []{#lst:boolean_matrix_minizinc label="lst:boolean_matrix_minizinc"} # Telethon Example {#sec:telethon} ## Problem Description {#subsec:telethon_description} The Telethon problem involves assigning $n$ runners to $n$ slots, where each runner has a preference for each slot. The preferences are categorized as follows: - **0: Not Available**: The runner cannot be assigned to this slot. - **1: Available but Not Preferred**: The runner can be assigned to this slot, but it is not their first choice. - **2: Preferred**: The runner prefers to be assigned to this slot. The objective is to minimize the number of assignments where runners are assigned to slots they are not happy with, i.e., slots with preference level 1. This problem is a practical example of a scheduling problem with preferences, and it can be modeled as a Constraint Optimization Problem (COP). ## MiniZinc Encoding {#subsec:telethon_minizinc} ::: tcolorbox int: n = 24; % Number of runners/slots set of int: slots = 1..n; array[slots, slots] of int: preferences; % Input preferences array[slots] of var slots: assignment; % Assignment of runners to slots % Hard constraint: If preference is 0, runner cannot be assigned to that slot constraint forall(i, j in slots)(if preferences[i, j] == 0 then assignment[i] != j endif); % Ensure a permutation (all different) constraint all_different(assignment); % Cost function: Minimize the number of unhappy assignments var int: cost = sum(i, j in slots)(bool2int(assignment[i] == j /\ preferences[i, j] == 1)); solve minimize cost; ::: []{#lst:telethon_minizinc label="lst:telethon_minizinc"} **Explanation:** - **Input Data**: - `n`: The number of runners and slots (set to 24 in this example). - `slots`: A set representing the available slots, defined as `1..n`. - `preferences`: A 2D array storing the preference level of each runner for each slot. - **Decision Variable**: - `assignment`: An array representing the assignment of runners to slots. `assignment[i] = j` means runner `i` is assigned to slot `j`. - **Constraints**: - **Hard Constraint**: If a runner's preference for a slot is 0, they cannot be assigned to that slot. - **Permutation Constraint**: The `all_different` constraint ensures that each runner is assigned to a unique slot, forming a permutation. - **Cost Function**: - `cost`: The objective function to be minimized. It counts the number of assignments where the preference level is 1 (available but not preferred). - **Solving**: - `solve minimize cost`: Instructs the solver to find an assignment that minimizes the total cost. This encoding effectively captures the Telethon problem, allowing us to find an optimal assignment that respects the runners' preferences while ensuring a valid schedule. <figure id="fig:telethon_graph"> <figcaption>Graphical representation of the Telethon problem with runners and slots.</figcaption> </figure> [1](#fig:telethon_graph){reference-type="ref+Label" reference="fig:telethon_graph"} illustrates the assignment of runners to slots, where each arrow represents an assignment. The goal is to find an assignment that minimizes the cost function, which counts the number of assignments to slots with preference level 1. []{#fig:telethon_example label="fig:telethon_example"} # Error Correcting Codes {#sec:error_correcting_codes} ## Problem Description {#subsec:error_correcting_codes_description} The error-correcting code problem involves generating a set of $k$ code words, each of length $n$, such that the Hamming distance between any two code words is at least $d$. This problem is crucial in ensuring reliable data transmission and storage, as it allows for the detection and correction of errors introduced during transmission or storage. :::: {.def:hamming_distance .definition} **Definition 1** (Hamming Distance). ::: tcolorbox *The Hamming distance between two words of equal length is the number of positions at which the corresponding symbols are different. For binary words, this is equivalent to the number of positions where the bits differ.* ::: :::: ## MiniZinc Encoding {#subsec:error_correcting_codes_minizinc} ::: tcolorbox int: n = 6; % Length of each word int: k = 4; % Number of words int: d = 3; % Minimum distance array[1..k, 1..n] of var bool: code; % Boolean matrix representing the code % Constraint: Ensure minimum distance between words constraint forall(i, j in 1..k where i < j)(sum(l in 1..n)(abs(bool2int(code[i, l]) - bool2int(code[j, l]))) >= d); % Symmetry breaking: Force the first row to be all zeros constraint forall(l in 1..n)(code[1, l] == false); % Lexicographical ordering constraint constraint forall(i in 1..k-1)(code[i] < code[i+1]); solve satisfy; ::: []{#lst:error_correcting_codes_minizinc label="lst:error_correcting_codes_minizinc"} **Explanation:** - **Input Data**: - `n`: The length of each code word (set to 6 in this example). - `k`: The number of code words (set to 4 in this example). - `d`: The minimum Hamming distance between any two code words (set to 3 in this example). - **Decision Variable**: - `code`: A 2D Boolean array representing the code words. `code[i, l]` is `true` if the $l$-th bit of the $i$-th code word is 1, and `false` otherwise. - **Constraints**: - **Minimum Distance Constraint**: Ensures that the Hamming distance between any two code words is at least `d`. The Hamming distance is computed by summing the absolute differences of the corresponding bits. - **Symmetry Breaking Constraint**: Forces the first code word to be all zeros. This is a symmetry-breaking technique that reduces the search space without losing generality. - **Lexicographical Ordering Constraint**: Ensures that the code words are lexicographically ordered. This further reduces the search space by eliminating symmetric solutions. - **Solving**: - `solve satisfy`: Instructs the solver to find a solution that satisfies all the constraints. ## Custom Lexicographical Ordering {#subsec:custom_lexicographical_ordering} ::: tcolorbox predicate my_lex(array[int] of var bool: first, array[int] of var bool: second) = let { int: len = length(first); array[1..len] of var bool: temp; } in temp[1] == true /\ forall(j in 1..len-1)( temp[len-j] == (first[len-j] < second[len-j] \/ (first[len-j] == second[len-j] /\ temp[len-j+1])) ) /\ temp[len] == true; % Using custom lexicographical ordering constraint forall(i in 1..k-1)(my_lex(code[i], code[i+1])); ::: []{#lst:custom_lexicographical_ordering label="lst:custom_lexicographical_ordering"} **Explanation:** - **Predicate Definition**: - `my_lex`: A custom predicate that defines lexicographical ordering between two Boolean arrays. - `len`: The length of the input arrays. - `temp`: A temporary Boolean array used to build the lexicographical ordering constraint. - **Lexicographical Ordering Logic**: - The predicate uses a temporary array `temp` to enforce the lexicographical order. - `temp[1]` is initialized to `true`. - For each position `j` from 1 to `len-1`, `temp[len-j]` is set to `true` if `first[len-j]` is less than `second[len-j]`, or if they are equal and `temp[len-j+1]` is `true`. - `temp[len]` must also be `true`. - **Usage**: - The `my_lex` predicate is used to enforce lexicographical ordering between consecutive code words. This custom predicate provides an alternative way to enforce lexicographical ordering, which can be useful for understanding how such constraints can be built from basic logical operations. <figure id="fig:hamming_distance"> <figcaption>Graphical representation of error-correcting code words and their Hamming distance.</figcaption> </figure> [2](#fig:hamming_distance){reference-type="ref+Label" reference="fig:hamming_distance"} illustrates the concept of Hamming distance between two code words. The dashed red lines indicate the positions where the bits are compared to calculate the Hamming distance. []{#fig:error_correcting_codes_example label="fig:error_correcting_codes_example"} # Knapsack Problem {#sec:knapsack} ## Problem Description {#subsec:knapsack_description} The knapsack problem is a classic combinatorial optimization problem where, given a set of items, each with a weight and a value, the goal is to determine the number of each item to include in a collection such that the total weight is less than or equal to a given limit (the capacity of the knapsack), and the total value is as large as possible. This problem has numerous applications in resource allocation, logistics, and portfolio management. This version of the knapsack problem is an extension where we can select multiple instances of the same item, not just 0 or 1. ## MiniZinc Encoding {#subsec:knapsack_minizinc} ::: tcolorbox int: n = 12; % Number of items int: space = 100; % Maximum weight capacity array[1..n] of int: weight = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]; % Weight of each item array[1..n] of int: cost = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095]; % Cost of each item array[1..n] of var 0..100: x; % Number of each item to include % Constraint: Total weight must not exceed the capacity constraint sum(i in 1..n)(x[i] * weight[i]) <= space; % Objective: Maximize the total cost var int: profit = sum(i in 1..n)(x[i] * cost[i]); solve maximize profit; ::: []{#lst:knapsack_minizinc label="lst:knapsack_minizinc"} **Explanation:** - **Input Data**: - `n`: The number of items (set to 12 in this example). - `space`: The maximum weight capacity of the knapsack (set to 100 in this example). - `weight`: An array containing the weight of each item. - `cost`: An array containing the value (or cost) of each item. - **Decision Variable**: - `x`: An array of variables representing the number of each item to include in the knapsack. The domain of each variable is `0..100`, meaning we can select between 0 and 100 instances of each item. - **Constraints**: - **Capacity Constraint**: The total weight of the selected items must not exceed the knapsack's capacity (`space`). - **Objective Function**: - `profit`: The total value of the selected items, which is to be maximized. - **Solving**: - `solve maximize profit`: Instructs the solver to find an assignment that maximizes the total profit while satisfying the capacity constraint. <figure id="fig:knapsack_graph"> <figcaption>Graphical representation of the knapsack problem with items, weights, costs, and quantities.</figcaption> </figure> [3](#fig:knapsack_graph){reference-type="ref+Label" reference="fig:knapsack_graph"} provides a visual representation of the knapsack problem, showing items with their respective weights, costs, and the quantities to be selected. The knapsack represents the capacity constraint, which must not be exceeded by the total weight of the selected items. []{#fig:knapsack_example label="fig:knapsack_example"} # Course Timetabling Example {#sec:course_timetabling} ## Problem Description {#subsec:course_timetabling_description} The course timetabling problem involves scheduling a set of courses over a given number of periods, considering various constraints such as teacher availability, course conflicts, and the required number of periods for each course. This problem is a complex combinatorial challenge that arises in educational institutions and other settings where resources must be allocated efficiently over time. In this specific example, we aim to schedule five courses over 20 periods, distributed across five days with four periods per day, in two available rooms. ## Input Data {#subsec:course_timetabling_input} The input data for this problem includes: - **Courses**: 5 courses to be scheduled. - **Periods**: 20 periods available for scheduling (e.g., four periods per day for five days). - **Rooms**: 2 rooms available for scheduling courses. - **Availability**: A matrix indicating when each course can be scheduled. This matrix specifies the periods when a course is available, typically based on teacher availability or other constraints. - **Conflict**: A symmetric matrix indicating which courses cannot be scheduled simultaneously. This matrix captures conflicts arising from shared teachers, students, or other resource limitations. - **Requirement**: An array specifying the number of periods required for each course. ## MiniZinc Encoding {#subsec:course_timetabling_minizinc} ::: tcolorbox int: nCourses = 5; int: nPeriods = 20; int: nRooms = 2; array[1..nCourses, 1..nPeriods] of int: available; array[1..nCourses, 1..nCourses] of int: conflict; array[1..nCourses] of int: requirement; array[1..nCourses, 1..nPeriods] of var bool: timetable; % Constraint: At most one of two conflicting courses can be assigned in the same period constraint forall(c1, c2 in 1..nCourses where conflict[c1, c2] == 1, p in 1..nPeriods)(timetable[c1, p] + timetable[c2, p] <= 1); % Constraint: If a course is not available at a period, it cannot be assigned constraint forall(c in 1..nCourses, p in 1..nPeriods)(if available[c, p] == 0 then timetable[c, p] == false endif); % Constraint: At most two courses can be scheduled in any period constraint forall(p in 1..nPeriods)(sum(c in 1..nCourses)(timetable[c, p]) <= nRooms); % Constraint: The number of periods assigned to each course must meet the requirement constraint forall(c in 1..nCourses)(sum(p in 1..nPeriods)(timetable[c, p]) == requirement[c]); solve satisfy; ::: []{#lst:course_timetabling_minizinc label="lst:course_timetabling_minizinc"} **Explanation:** - **Input Data**: - `nCourses`: The number of courses to be scheduled (set to 5). - `nPeriods`: The number of available time periods (set to 20). - `nRooms`: The number of available rooms(set to 2). - `available`: A 2D array indicating the availability of each course at each period. - `conflict`: A 2D symmetric array indicating which courses cannot be scheduled simultaneously. - `requirement`: An array specifying the number of periods required for each course. - **Decision Variable**: - `timetable`: A 2D Boolean array representing the schedule. `timetable[c, p]` is `true` if course `c` is scheduled in period `p`, and `false` otherwise. - **Constraints**: - **Conflict Constraint**: Ensures that at most one of two conflicting courses is scheduled in the same period. - **Availability Constraint**: Ensures that a course is not scheduled in a period when it is not available. - **Room Capacity Constraint**: Ensures that at most two courses are scheduled in any given period (since there are two rooms). - **Requirement Constraint**: Ensures that each course is assigned the required number of periods. - **Solving**: - `solve satisfy`: Instructs the solver to find a schedule that satisfies all the constraints. <figure id="fig:course_timetabling_graph"> <figcaption>Graphical representation of the course timetabling problem with courses, periods, and rooms.</figcaption> </figure> [4](#fig:course_timetabling_graph){reference-type="ref+Label" reference="fig:course_timetabling_graph"} illustrates the course timetabling problem, showing the courses, periods, and rooms. The goal is to find a valid schedule that satisfies all constraints, including availability, conflicts, and requirements. []{#fig:course_timetabling_example label="fig:course_timetabling_example"} # Conclusion {#sec:conclusion} This document has presented a comprehensive overview of various Constraint Satisfaction Problems (CSPs) and their encoding techniques using MiniZinc. We have explored different modeling approaches, including array-based and Boolean matrix-based methods, and illustrated their applications through practical examples such as timetabling, error-correcting codes, and the knapsack problem. Key takeaways from this exploration include: - **Importance of Modeling Approach**: The choice of an appropriate modeling approach (e.g., array-based vs. Boolean matrix-based) significantly impacts the efficiency and clarity of the solution. - **Symmetry Breaking**: Symmetry breaking techniques, such as forcing the first row to be all zeros in the error-correcting code problem, are crucial for reducing the search space and improving solver performance. - **Optimization Techniques**: Optimization techniques, such as minimizing the cost function in the Telethon problem, allow us to find the best solution according to a given objective. - **Practical Applications**: CSPs have wide-ranging applications in real-world scenarios, including scheduling, resource allocation, and data transmission. ::: tcolorbox - Different modeling approaches (array-based, Boolean matrix) have different strengths and weaknesses. - Symmetry breaking is essential for efficient problem-solving. - Optimization techniques allow us to find the best solution according to a given objective. - CSPs have numerous real-world applications. ::: []{#box:key_takeaways label="box:key_takeaways"} For future lectures and further study, we can delve deeper into advanced constraint programming techniques, explore other types of CSPs, and discuss how to handle more complex constraints and optimization criteria. Additionally, we can consider the following questions to guide our future explorations: - **Efficiency of MiniZinc Models**: How can we further improve the efficiency of our MiniZinc models, including the choice of appropriate data structures, constraints, and search strategies? - **Real-World Applications**: What are some other real-world applications of CSPs, and how can we model them effectively using MiniZinc or other constraint programming languages? - **Integration with Other Techniques**: How can we integrate constraint programming with other optimization techniques, such as integer programming, metaheuristics, or machine learning, to tackle more complex and challenging problems? By addressing these questions, we can enhance our understanding of constraint satisfaction problems and their applications, and develop more effective solutions for complex real-world scenarios. The journey into constraint programming is ongoing, and there are always new techniques and applications to explore. []{#sec:future_directions label="sec:future_directions"}