Theory

Question 1

Question: What is Linear Programming (LP)?

Answer 1

Linear Programming is a mathematical method for solving optimization problems where the objective function and constraints are linear. The goal is to find the maximum or minimum of the objective function, subject to given constraints.

Question 2

What is the general form of an LP problem? (Included in the tableaux)

Answer 2

The general form of an LP problem is:
Minimize or Maximize 𝑐(^𝑇)𝑥
Subject to 𝐴𝑥≤𝑏
and 𝑥≥0
where A is a matrix of coefficients,
b is a vector of constraints,
c is a vector of costs or coefficients, and
x is a vector of decision variables

Question 3

What does the Fundamental Theorem of LP state?

Answer 3

The Fundamental Theorem of Linear Programming states that if an optimal solution exists, it will occur at an extreme point of the feasible region, which is the convex set defined by the constraints.

Question 4

What is a convex set?

Answer 4

A set is convex if, for any two points within the set, the line segment connecting them lies entirely within the set.

Question 5

What is the Simplex Algorithm?

Answer 5

The Simplex Algorithm is a method for solving linear programming problems by moving along the edges of the feasible region to find the optimal extreme point (vertex) that maximizes or minimizes the objective function.

Question 6

What are slack variables in LP?

Answer 6

Slack variables are added to convert inequalities into equalities in a linear programming problem. They represent the difference between the left-hand side and the right-hand side of the inequality constraints.

Question 7

What is the dual problem in LP?

Answer 7

The dual problem in LP is derived from the primal problem and involves maximizing a function subject to constraints derived from the original problem. The optimal value of the dual problem is equal to the optimal value of the primal problem.

Question 8

What is an infeasible LP problem?

Answer 8

An LP problem is infeasible when no solution satisfies all of the constraints, meaning the feasible set is empty.

Question 9

What is an unbounded LP problem?

Answer 9

Answer: An LP problem is unbounded if the objective function can be made arbitrarily large (or small in minimization problems) without violating any of the constraints.

Question 10

What is computational complexity in the context of optimization?

Answer 10

Computational complexity refers to the difficulty of solving an optimization problem in terms of the time and resources required, often classified into categories such as P (polynomial time) and NP-hard (non-deterministic polynomial-time hard).

Question 11

What does it mean for a solution to be sound in optimization problems?

Answer 11

A solution is sound if every solution found by the algorithm is a valid solution, meaning it satisfies all the constraints of the problem.

Question 12

What does it mean for a solution to be complete in optimization problems?

Answer 12

A solution is complete if the algorithm can find a solution whenever one exists. In other words, it is guaranteed to find a solution if the problem is solvable.

Question 13

Can an algorithm be sound but not complete?

Answer 13

Yes, an algorithm can be sound but not complete. This means it only finds valid solutions, but it might not always find a solution even if one exists.

Question 14

Can an algorithm be complete but not sound?

Answer 14

No

If an algorithm is complete but not sound, it would mean it finds all possible solutions but also includes incorrect ones. In this case, it would not truly “find” the solutions in a meaningful way because it would lack confidence in the correctness of what it outputs. Essentially, its results would be unreliable, making it invalid as an algorithm for solving the problem, as algorithms are typically required to give correct answers.

In summary, an algorithm can be:

• Sound but not complete (always correct but might miss some solutions),
• Both sound and complete (correctly finds all solutions), or
• Neither sound nor complete (may give incorrect answers and miss solutions).

Question 15

Is it possible for a solution to be neither sound nor complete?

Answer 15

Yes, it is possible for an algorithm to be neither sound nor complete, meaning it might produce invalid solutions and fail to find all valid solutions when they exist.

Question 16

LP: What does it mean when there are no negative values in the bottom row?

Answer 16

There are two cases when the cT row has no negative values:
1. When the origin is not in the feasible set, which happens if there are surplus variables
that have negative values at the origin; or
2. all variables have non-negtive values at the current basic solution.
In the first case we need to do phase 1 to get into the feasible set. In the second case we cannot
improve the objective function value, and so we have found the optimum.

Question 17

When solving LP problems, we typically (but not necessarily) select the pivot column by the largest negative value in the bottom row. Why?

Answer 17

When solving, we typically let the pivot column be decided by the currently larges negative
value in the cT row, as this affects the objective function value the most, and has a good
chance of finding the optimum with examining few extreme points.

Question 18

For the A* algorithm, we learned that the heuristic should be admissible and monotone, explain what those properties mean and why they are important

Answer 18

A heuristic is admissible if it never overestimates the true cost to reach the goal from any node in the search space. In other words, it always provides a cost estimate that is equal to or less than the actual lowest cost from the current node to the goal.A heuristic is admissible if it never overestimates the cost to the goal

A heuristic is monotone if Cost (a -> c) <= Cost(a -> b) + Cost(b -> c), compare the triangle inequality.
Consistency ensures that as A* progresses, the total estimated cost along any path will only increase or stay the same, preventing the need to revisit nodes and making A* more efficient.

Question 19

If the heuristic cost at the goal node is 0, then one of those properties implies the other, which one and why?

Answer 19

Monotonicity implies admissibility (assuming that h(goal)=0)

monotonicity –> admissible
not admissible –> not monotone

Note: h can be admissible without being monotone

Question 20

A* is said to be optimal, what does that really mean?

Answer 20

A* is optimal means that there can exist no other algorithm using the same information that searches fewer nodes than what A* does.

Question 21

Describe the P vs NP problem

Answer 21

NP represents the class of problems for which given a solution, we can in polynomial (with respect to the size of the input) time verify that this is indeed a correct solution.

P represents the class of problems for which we can compute a solution in polynomial time. We know that P is included in NP, but is P = NP?
This we do not know. No-one expects the equality to hold, if it did our world would be a bleaker place, but no one knows for sure.

Question 22

There is something special with the set of problems that we call NP-complete. What is so special about them?

Answer 22

NP-complete problems are a special kind of NP problem that are also very hard (we call this NP-hard).

Here’s what’s interesting about them:

• All NP-complete problems are connected: You can convert one NP-complete problem into another quickly (in a reasonable amount of time). This means that, in a way, all NP-complete problems are different versions of the same tough problem.
• Why they matter for P vs. NP: Every NP problem can be turned into an NP-complete problem, but the reverse isn’t true. So, if we could find a fast (polynomial-time) way to solve even one NP-complete problem, we would suddenly be able to solve all NP problems quickly. That would prove that P = NP.

NP problems are ones where, if you have a solution, you can quickly check it’s correct — but finding that solution from scratch can be very hard.

Question 23

What is the key difference between Mixed Integer Linear Programming (MILP) and Constraint Programming (CP)?

Answer 23

MILP focuses on optimizing a linear objective function with constraints that may include both continuous and integer variables, while CP focuses on satisfying constraints, typically used in combinatorial problems, without necessarily optimizing a linear objective function.

Question 24

How can you convert a model from MILP to CP?

Answer 24

To convert from MILP to CP, you replace the linear objective function with constraints and remove the requirement for an objective function. You may need to reformulate constraints to fit into CP’s structure of variable domains and satisfaction of constraints rather than optimization.

Question 25

In what situations is Mixed Integer Linear Programming (MILP) preferable over Constraint Programming (CP)?

Answer 25

MILP is preferable when the problem involves linear relationships and the goal is to optimize an objective function, especially in scenarios where precision is required, such as resource allocation, financial optimization, and logistics.

Question 26

In what situations is Constraint Programming (CP) preferable over Mixed Integer Linear Programming (MILP)?

Answer 26

CP is better suited for combinatorial problems, scheduling, and problems with complex constraints that are hard to express linearly, or where feasibility is the primary concern over optimization.

Question 27

What is the A* algorithm, and where is it typically used?

Answer 27

The A* algorithm is a heuristic search algorithm used to find the shortest path in graph-based problems. It combines the actual cost from the start with an estimated cost to the goal, making it efficient for pathfinding and routing.

Question 28

What is Dijkstra’s algorithm, and how does it differ from A*?

Answer 28

Dijkstra’s algorithm is a graph search algorithm that finds the shortest path from a start node to all other nodes by expanding the least costly paths first. Unlike A*, it doesn’t use a heuristic and explores nodes based purely on path cost.

Question 29

What are heuristic algorithms, and why are they important in optimization?

Answer 29

Heuristic algorithms are problem-solving methods that use practical approaches to finding good-enough solutions efficiently, especially when exact methods are computationally expensive. They are important for solving large, complex problems quickly.

Question 30

What does it mean if a linear programming problem is infeasible?

Answer 30

A problem is infeasible if no satisfiable assignment exists, meaning the feasible set spanned by the constraints and domains is empty due to conflicting constraints.

Question 31

Give an example of an infeasible linear programming problem.

Answer 31

Objective: Maximize 𝑧 = 𝑥 + 𝑦
Subject to the constraints:
𝑥 + 𝑦 ≤ 1
𝑥 + 𝑦 ≥ 3
𝑥 ≥ 0
𝑦 ≥ 0

Question 32

What does it mean if a linear programming problem is unbounded?

Answer 32

A problem is unbounded when there is no bounded solution, meaning the objective function can grow arbitrarily large or small because the constraints are not tight enough to limit the solution space.

Question 33

Give an example of an unbounded linear programming problem.

Answer 33

An example of an unbounded problem is:
maximize x1 + 3*x2
subject to x1+x2 >= 4,
x1, x2 >= 0
Here, there is no upper limit on the values can take, making the solution unbounded.

Question 34

What does it mean for a solution to be feasible in linear programming?

Answer 34

A solution is feasible if it satisfies all the constraints, meaning the solution lies within the bounded feasible region defined by the constraints.

Question 35

What is a unique feasible solution in linear programming?

Answer 35

A unique feasible solution occurs when there is only one optimal solution, which appears at an extreme point where constraints intersect.

Question 36

What is a non-unique feasible solution in linear programming?

Answer 36

A non-unique feasible solution occurs when there are infinitely many optimal solutions along a constraint boundary, typically when the objective function is parallel to one of the constraints.

Question 37

Can a non-unique solution still include extreme points?

Answer 37

Yes, even in a non-unique solution, at least one solution will occur at an extreme point of the feasible region.

Question 38

When is a feasible set convex?

Answer 38

If all constraints C of an optimization problem are linear

Question 39

When is a function unimodal?

Answer 39

A function f(x) is unimodal (over an interval) if there exists an m (the mode) such that f(x) strictly (monotonically) increases for x < m and strictly decreases for x > m (over the interval).

Question 40

When is every local optimum is also a global optimum

Answer 40

If for an optimization problem
* the objective function is unimodal, and
* the constraints define a convex feasible set

Question 41

What is the Simplex method in linear programming?

Answer 41

The Simplex method is an iterative algorithm used to find the optimal solution to a linear programming problem by moving along the edges of the feasible region to reach an extreme point that optimizes the objective function.

Question 42

Where does the Simplex method start when solving a problem?

Answer 42

The Simplex method starts at a feasible extreme point, typically the origin, where all decision variables are zero (if it satisfies the constraints).

Question 43

How does the Simplex method move between solutions?

Answer 43

The Simplex method moves from one extreme point (vertex) of the feasible region to another by increasing or decreasing decision variables, following the direction that improves the objective function the most.

Question 44

How does the Simplex method decide which variable to increase or decrease?

Answer 44

The method selects the non-basic variable with the most negative coefficient in the objective function (for maximization problems) to increase, because increasing it will improve the objective function the fastest.

Question 45

How does the Simplex method determine when it has found the optimal solution?

Answer 45

The Simplex method stops when there are no negative coefficients left in the row of the objective function (for maximization problems), indicating that increasing any variable will no longer improve the objective value.

Question 46

Can the Simplex method handle both bounded and unbounded problems?

Answer 46

The Simplex method can handle bounded problems efficiently by finding the optimal solution at an extreme point, but for unbounded problems, the method will detect that the solution can be increased indefinitely without violating constraints.

Question 47

What is a pivot in the Simplex method?

Answer 47

In the Simplex method, a pivot is the step where we adjust the current solution to improve it and move closer to the optimal solution of a linear programming problem.

Here’s what a pivot involves:

1. Choosing an entering variable: We select a variable that can increase or decrease to improve the objective function (e.g., profit or cost). This variable enters the basis (the set of variables we’re currently focusing on).
2. Choosing a leaving variable: To keep the solution feasible (meeting all constraints), we need to adjust another variable to exit the basis. This is often chosen based on a rule that prevents any constraint from being violated.
3. Swapping the variables: The entering variable takes the place of the leaving variable, and we recalculate the values of all variables based on this new setup.

Question 48

What good is relaxation?

Answer 48

• show infeasibility (if the relaxed problem don’t have a solution, then the original problem wont either)
• get bounds on the true optimal solutions (lower bounds for min, upper bound for max)
• rounded solutions may be good enough
• Disregards the discrete domain constraint, treat discrete variables as real values
• if the relaxed optimum is also feasible for the original problem, then it is the optimum for the original solution

Question 48

A unimodular matrix is:

Answer 48

• Square
• Integer
• Determinant ±1

Note: Square and non-zero determinant means that the matrix is invertible
Note: Integer and determinant ±1 means that the inverse matrix is also integer

Question 49

Totally unimodular matrix

Answer 49

• not necessarily square, but
• every square, non-singular sub-matrix is unimodular

1. Each element of A either −1, 0, or 1
2. At most two non-zero elements in each column (row)
3. The columns (rows) can be partitioned into M1, M2, such that:

If A is totally unimodular, then the optimal solution is integer, since then for every basic solution B, x = B^(−1) b is integer (whenever b is integer).

(a) for two non-zero elements of equal sign in same column (row), one is in M1, the other in M2
(b) for two non-zero elements of different signs in same column (row), both are in M1, or both in M2

Question 50

IP summarized

Answer 50

The equation Ax = b, with A non-square, has many solutions (typically).

Such solutions are given by
invertible m × m sub-matrices of A.
The optimization problem now involves finding one solution that minimizes the objective function cT x.

If the relaxed (LP) problem happened to give a solution where also x ∈ N+, then this is a solution to the IP problem.

If A is totally unimodular, then every invertible sub-matrix is uni-modular, its inverse exists and is integer. Thus, if A totally unimodular, and b is integer, then all the solutions will be integer.

Question 51

Formulating LP/IP/MILP problems

Answer 51

1. Define what seems like the necessary variables
2. Define a set of constraints so the feasible set is closed (and preferably convex)
3. Define the objective function
   If difficulties arise, define additional or alternative sets of variables and iterate.

Be picky!
Remember, we are formulating the problem to be solved by a computer. There is no hand-wavy “nudge, nudge, know what I mean, eh?”

Question 52

When is Less More? (Variables in a model)

Answer 52

An important notable exception for when we want to have less, rather than more, variables is for highly symmetric problems, where instead the symmetry is best removed. See Example (10.2)

Question 53

A CSP can be (states)

Answer 53

• consistent, a solution (or more than one) exists
• inconsistent, no solution exists
• solved, the domains are singletons and together a solution to the CSP
• failed, one (or more) empty domains, or only singleton domains that are together not a solution to the CSP

A solution is a domain.
A failed CSP is inconsistent.

Question 54

Solving CSPs revolves around different notions of concistency:

Answer 54

• Node consistency (aka domain consistency)
• Arc consistency (aka binary consistency)
• Directed arc consistency (fwd, bwd)
• Hyper-arc consistency
• Bounds consistency

The overall aim is to tighten the bounds on the problem, until only a solution is left.
Most of the procedures are rather straightforward, yet applying them iteratively lead to powerful solution procedures.

Question 55

Notes on linear inequality constraints domain reduction:

Answer 55

• The reduction needs to be iterated until they “stabilize” (a fix-point is reached)
• The calculated domain bounds may or may not result in domain reduction
  If the calculated bounds are less constraining than the original bounds, then no reduction.

Question 56

Constraint propagation

Answer 56

Constraint propagation is a technique used in constraint programming to reduce the search space by deducing variable constraints and eliminating values that cannot be part of any valid solution, thereby simplifying the problem before or during the search process.

Variables depend on each other by being part of the same constraint(s) - if one variables domain changes then the others also do

(there is a good example on page 136)

Question 57

Types of constraints

Answer 57

Unary Constraints: Restrictions applied to a single variable (e.g., 𝑥>5)

Binary Constraints: Constraints involving two variables (e.g.,x+y≤10).

Global Constraints: Involve multiple variables and capture common patterns, such as AllDifferent, which requires all variables to have different values.

Linear Constraints: Expressed as a linear equation or inequality (e.g., 2x+3y≤15).

Nonlinear Constraints: Involve nonlinear relationships between variables (e.g., x 2+y 2≤25).

Logical Constraints: Use logical operators (AND, OR, NOT) to link constraints (e.g., x>5 ANDy<3).

Time/Temporal Constraints: Apply to scheduling problems, where variables are bound by timing constraints (e.g., start time, end time).

Resource Constraints: In resource allocation, these limit how much of a resource can be used (e.g., limited machine hours in production).

Mutual Exclusion Constraints: Specify that certain variables or values cannot coexist (e.g., Investment A and Investment B cannot both be selected).

Question 58

Define the dual problem (equation)

Answer 58

max b^(t)y, subject to A^(T)y = c, y>=0
The dual problem is larger or equal to the constraints compared to standard LP
Original: m constraints, n decision variables –> Dual: n cons., m dec. var.
Has the same optimal value as original problem

Question 59

Costs in discrete optimization can be:

Answer 59

uniform, all costs equal
non-uniform

Question 60

Mixed Integer Linear Programming

Answer 60

• Involves both discrete & continuous variables (linear constraints)
• Real x E R^(m), discrete z E Z^(n)

Question 61

Big M

Answer 61

• If we want either one or another constraint to be true
• M is a large enough number
• M * gamma OR M*(1-gamma) (these are present in each ones equation, gamma 1 or 0)

Question 62

Graph search algorithms are:

Answer 62

Branch - Left or right, take decision

Bound - Compare current cost with best seen so far, can cut off branches if we know costs are monotonically increasing

Question 63

Breadth first

Answer 63

• Uninformed
• Looking for possible path at different “levels”
• The first time we see the goal, its via the shortest path (not guaranteed if depth first search is used)

Question 64

Informed algorithms

Answer 64

Dijkstras and A*

Question 65

What information does dijkstra and A* use

Answer 65

Dijkstras:
- current cost (nodes are picked based on this)

A*:
- Current cost
- Estimate to reach the goal (heuristic)

Question 66

Describe Dijkstras

Answer 66

1. Start at beginning
2. Assign beginning = 0 and all other nodes = inf
3. Visit the nearest & check for neighboring nodes
   If you can reach that neighbor with a shorter distance than previously known –> update distance
4. Mark current node as visited
5. Move to unvisited node with shortest path
6. Repeat until all nodes are visited or goal is reached

Question 67

Describe A*

Answer 67

1. Start at the beginning
2. Visit the node with lowest total cost (distance so far + estimate)
3. For this node, check for neighbors, update if its shorter(less costly) than you knew before, also estimate remaining distance
4. Keep track of which node came from wich (parent and children)
5. Repeat visiting neighbors with lowest total cost, continue until goal is reached

A* is faster since it’s using a heuristic to guess which path is best

It’s a difference between finding the optimum and being optimal - A* is optimal!

Question 68

Heuristic

Answer 68

Straight line distance between current point & goal

Question 69

CP model formulation

Answer 69

<X, D, C>
X - set of decision variables
D - set of domain, Di for variable xi etc
C - set of global constraints

Question 70

When is X bound, inconsistent and free?

Answer 70

bound:
|Di| = 1 (single value)

inconsistent:
|Di| = 0 (Dx=0)

free:
|Di| >= 2 (more than one value)

Question 71

CP
Constraints are defined by:

Answer 71

intension:
defining an explicit relation between the variables (x!=y)

extension:
defining valid tuples

Question 72

Several feasible solutions is called

Answer 72

The solution set

Question 73

CSP feasible solution

Answer 73

(p.110)
Given a CSP ⟨X, D, C⟩, a solution δ ⊆ D is feasible if
^ c(δ) is true

Question 74

Inequality constraints

Answer 74

Sum(X aixi, i∈POS) − Sum(X aixi, i∈NEG) ≤b

• ai positive integer for i ∈ POS U NEG
• xi and xj are different variables for i,j ∈ POS U NEG and i != j
• b is integer

POS is the set of indices for the variables with positive contribution to the constraint

NEG is the set of indices for the variables with negative contribution to the constraint

The constraint is then said to be normalized. Assume the domains are integer intervals
xi ∈ min(xi)..max(xi)

Question 75

How to handle disequalities

Answer 75

Given: 𝑆 ≠ 𝑇 with domains 𝐷 for variables in 𝑆 and 𝑇.

Step 1: Introduce a new variable 𝑥 , rewriting as:
𝑥 ≠ 𝑇 with domain 𝐷
𝑥 = 𝑆 where x∈{min(S)..max(S)}

Why this helps: It simplifies the disequality by splitting it into two constraints, making it easier to process.

Step 2: Apply again to 𝑥 ≠ 𝑇:
𝑥 ≠ 𝑦 , where x∈{min(S)..max(S)}
𝑥 = 𝑆 where y∈{min(T)..max(T)}
𝑦 = 𝑇, D

Result: We obtain two equalities (x=S and 𝑦 = 𝑇 ) and a simpler disequality 𝑥 ≠ 𝑦

Question 76

Boolean CSP Basics

Answer 76

Domain: Boolean domains,
x∈{0,1}
Boolean Connectives:
¬: Negation (“not”)
∧: Conjunction (“and”)
∨: Disjunction (“or”)
Equality Relation: =

Question 77

Simple Boolean Constraints

Answer 77

Given variables x,y,z:
x=y: Equality constraint
¬x=y: NOT constraint
x∧y=z: AND constraint
x∨y=z: OR constraint

Question 78

Transforming Compound Boolean Constraints to simple - how?

Answer 78

Non-simple (compound) Boolean constraints can be transformed into simple constraints by introducing new variables.

Question 79

Transformation rules for boolean CSP (make it more simple)

Answer 79

Let S:= S1∨(S2∧S3) with Si variables
Then ¬S = t is transformed into ¬x = t1, S = x

SEE EXAMPLE IN BOOK p.132

Question 80

Constraint Propagation (definition and how it works)

Answer 80

Definition: A process in constraint satisfaction problems where variables depend on each other through shared constraints.

How it works: When one variable is changed (e.g., assigned a value or has its domain reduced), other dependent variables may also be affected.

Propagation: These changes spread through the constraints, affecting related variables.

Purpose: Helps to reduce possible values for variables, making the problem easier to solve.

Question 81

Constraint graph

Answer 81

A graph with:
- The variables associated to the nodes
- The constraints associated to the edges
- Straight forward for binary relations

Question 82

Dual graph

Answer 82

• Had the constraints as the nodes
• The edges representing the variable connections

Question 83

Node consistency

Answer 83

A CSP is node consistent if for every unary constraint over the variable x, the constraint is valid over Dx (the whole domain)
A CSP without unary constraints is node consistent

Note:
Node consistency does not imply consistency
Consistency does not imply node consistency

Question 84

Arc consistency

Answer 84

A CSP is arc consistent if for every binary constraint over variables X and Y , the constraint is valid for all values of Dx and Dy
(p.146)

Question 85

Hyper-arc-consistency

Answer 85

A CSP is hyper-arc-consistent if for every constraint C, for every involved domain, each element participates in a solution to C

Ex:
C: x<y<z
x E {0,1}
y E {1,2}
z E {2,3}

Question 86

Path consistency

Answer 86

Simple explanation:
- Think of a path from xi to xj where xk is in the middle

Path consistency tightens the binary constraints using implicit constraints inferred from looking at triplets of variables

More complex:
- A two-variable set {xi, xj} is path consistent with a third variable xk, if for every assignment xi & xj consistent with the constraints on {xi, xj} there is an assignment to xk that satisfies the constraints on {xi, xk} and {xk, xj}

Question 87

Bound propagation (consistency)

Answer 87

• For large domains, it is not practical to represent all values in the domain explicitly
• Instead, the domain is represented by its bounds
• Thus, it is not possible to use the local consistency rules to gradually reduce the domain
  (Something is called local if it only considers subsets of variables/constraints/domains, never the whole global problem

Question 88

Minimum Remaining Values (MRV)

Answer 88

• Selects the most constrained variable in a “fail first” attempt
• The degree heuristic attempts to reduce the branching factor of future choices by selecting the variable involved in the largest number of constraints with other unassigned variables

The MRV heuristic chooses the variable that has the fewest possible values left in its domain — in other words, the variable with the most constraints or restrictions. The idea is to tackle the hardest (most constrained) variables first, to see if a solution is even possible. If we hit a dead end, we know sooner rather than later, which can save time.

Question 89

Order domain values (MRV)

Answer 89

• The least constraining value heuristic is often a good choice
  It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph
• Tries to leave the maximum flexibility for subsequent variable assignments

By choosing the least constraining value each time, we reduce the chance of getting stuck in a situation where there are no valid options left for other variables. This strategy can make it easier and faster to find a solution.

Question 90

Maintaining arc consistency (MAC)

Answer 90

• Aka full look ahead, does what FC does + recursively propagate constraints when changes are made to the domains

When you assign a value to a variable, MAC checks all constraints to see if the remaining possible values for other variables are consistent with the new assignment. It does this by enforcing something called arc consistency:

Arc consistency means that for every possible value of one variable, there must be at least one compatible value for every other variable it’s connected to by a constraint.
If assigning a value to a variable causes any other variable to lose all possible values (because it no longer has any options that are consistent with the new assignment), MAC will trigger backtracking immediately.

MAC is powerful because it ensures the entire problem remains consistent with every assignment, which reduces the chance of getting deep into the search only to discover a problem later. This can make the search process much more efficient by cutting off invalid paths sooner.

Question 91

Forward Checking (FC)

Answer 91

• Checks the effect of a tentative assignment for every variable, one at a time

When you assign a value to a variable, forward checking immediately looks ahead to the neighboring variables (those directly connected to it by constraints) to see if the chosen value would prevent any of them from having valid options left. If assigning this value would eliminate all possible values for any neighboring variable, the algorithm stops and “backtracks” — meaning it undoes this choice and tries a different value.

Forward checking prevents the algorithm from going too far down a path that won’t work. By catching conflicts early, it avoids wasting time on assignments that will lead to failure later, making it more efficient in finding solutions.

Question 92

Partial look ahead

Answer 92

• Enforces single step directional arc consistency in the “forward” direction for xi, xj with i < j <= n (needs some idea of ordering)

Question 93

Full look ahead

Answer 93

• Enforces arc consistency between every unassigned pair xi, xj (only single step)

Whenever a variable xi is assigned, full lookahead checks all pairs of variables ⟨xj,xk⟩ in both forward and backward direction.

Question 94

Arc consistency

Answer 94

• Iteratively checks arc consistency for all pairs until stabilizing

Question 95

WHY DO PROPAGATION DURING SEARCH INSTEAD OF JUST SIMPLE FORWARD CHECKING AND EVALUATING THE TREE UNTIL SOLUTION OR INCONSISTENCY IS FOUND?

Answer 95

• Find inconsistencies early by doing local examination of neighboring values
• Shrink the domains of the variables so that the search tree is narrowed “underneath” the current partial assignment
• Avoid searching identical subtrees underneath different assignments