Constraint Solving with F# and Min Conflicts

Read Time: 11 minutes

Sticking on the theme constraint solvers, Min Conflicts is one of the many algorithms that can be used to find a solution. Today I’ll take a look into how this works in F#.

The Min Conflicts algorithm focuses on continually reducing constraint violations one variable at a time. Using this iterative approach, it can eventually converge to a solution that ideally satisfies all constraints. At least this is the theory.

There are a couple considerations when discussing Min Conflicts. First, no solution is guaranteed using this approach. The algorithm could get stuck in a locally optima, making a true solution difficult to find. Second, using random selection and iteration, even if successful it could just take too long to practically find a solution.

Understanding these limits is important, but that does not mean all is not lost. First, complete solutions can be found, its just not always a guarantee. But when it can’t, it can provide partial solutions. In the real world, sometimes “close enough” can get the job done. Just getting to this point can be a huge win. Second, sometimes the problem statement doesn’t start from scratch. Min Conflicts can also be thought of as a healing algorithm, where the solution defined is mostly correct, but final iteration is required. It can be used to fix smaller parts of a larger problem.

Similar to previous constraint solving problems (CSP) discussed, there are a couple definitions. A CSP consists of several components. It starts with variables. Those variables can have possible values (domain). Variables have relationships between each other (constraints). A constraint is ultimately just a function which defines valid combinations of values.

It often helps to see how a problem is defined and how the components interact, so here is a simple example. The first part is to define the variables and their domains. As you can see below, there are 3 variables (A, B, C), each of which have a possible value of 1 - 100. The second part is to define the constraints the variables must adhere to. A must even, B must be even, A must be less than B, C must be greater than A, and the values of A, B, and C must be able to conform to the lengths of the sides of a right triangle.

Variables:
A = { 1 .. 100 }
B = { 1 .. 100 }
C = { 1 .. 100 }

Constraints:
A, even()
B, even()
A, B, lessThan()
C, A, greaterThan()
A, B, C isRightTriangle()

How does this work in practice? I’ll manually walk through an example. To keep the explanation short I will also have a very lucky randomizer. In practice there is a lot more wandering than the steps I show below. To help track progress, values with at least one constraint failure are marked with a ‘*’. The first step is to initialize the variables with random values. Second, a variable with conflicts is randomly selected (in this case A). The algorithm iterates through all the possible values of A, counting the number of conflicts resulting from each value. In this case ‘2’ provides the least number of conflicts for the solution. Note, it’s not perfect yet, but it is at least slightly better. This process is repeated. Next B is processed (finding 96), then A again (finding 28), then finally C (finding 100). At this point we have a solution. The values A=28, B=96, and C=100 pass all the provided constraints.

A B C
init 5* 3* 80*
step 1: A 2* 3* 80*
step 2: B 2* 96* 80*
step 3: A 28* 96* 80*
step 4: C 28 96 100

With that short explanation out of the way, its time to dig into how the algorithm is implemented in F#. Before getting to the meat of the algorithm, there are some definitions to make the code cleaner to read. This is pretty similar to the definitions in my previous AC-3 post. One notable aspect is Min Conflicts is not limited to unary and binary constraints like AC-3. Constraints can have an arbitrary number of variables. This makes the search space larger, but the power it provides by allowing the definition of more complex problems is important. So the NaryConstraint takes variables as an array of variable ids.

1
2
3
4
5
6
7
8
9
10
type Domain = int list
type Id = int
type Variables = Map<Id, Domain>
type NaryConstraint = Id[] * (Id[] -> bool)
type NaryConstraints = NaryConstraint list

let listToVariables (variables: (int list) list) :Variables =
  variables
  |> List.mapi (fun i x -> (i, x))
  |> Map.ofList

What does solving actually look like? In the below implementation, the solver initializes the variables to a random value from their respective domains. It then randomly picks a variable that has failed constraints. For that variable it then iterates through all possible values in its domain. It determines the value that results in the fewest number of conflicts (constraint failures). Once its found, it sets the variable’s value. The algorithm continues this process until a solution is found. There is also a safety value of “max rounds”. If a solution can’t be found, it at least won’t run until infinity. The solver returns the success/failure of finding a solution. In the case of failure it also returns a partial solution along with the conflict state of each variable. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
let solve (maxRounds: int) (constraints: NaryConstraints) (variableDomains: Variables) :(bool * Map<Id, int> * ((Id * int * bool) list)) =
  let variables =
    variableDomains
    |> initVariables

  let conflicts = getConflicts constraints variables

  let mutable round = 1
  let mutable success = false
  let mutable keepGoing = true

  let conflictCount =
    conflicts
    |> Seq.filter (fun x -> x.Value)
    |> Seq.length

  success <- conflictCount = 0
  keepGoing <- conflictCount > 0

  while keepGoing do
    // Determine a variable for modifying
    let modifyTarget =
      let possible =
        conflicts
        |> Seq.filter (fun x -> x.Value)
        |> Seq.map (fun x -> x.Key)
        |> Seq.toList
      (possible[rand.Next(List.length possible)])

    // Determine the value of variable that maximially reduces conflicts
    let mutable bestValue = variables[modifyTarget]
    let mutable bestConflictCount = Int32.MaxValue
    for domainValue in variableDomains[modifyTarget] do
      variables[modifyTarget] <- domainValue
      let alternateConflicts = getConflicts constraints variables
      let conflictCount =
        alternateConflicts
        |> Seq.filter (fun x -> x.Value)
        |> Seq.length

      if conflictCount < bestConflictCount || (conflictCount = bestConflictCount && rand.NextDouble() < 0.5) then
        bestValue <- domainValue
        bestConflictCount <- conflictCount
        conflicts.Clear()
        alternateConflicts
        |> Seq.iter (fun x -> conflicts.Add(x.Key, x.Value))

    variables[modifyTarget] <- bestValue

    // Determine success state
    let conflictCount =
      conflicts
      |> Seq.filter (fun x -> x.Value)
      |> Seq.length

    success <- conflictCount = 0
    round <- round + 1
    keepGoing <- (not success) && (round <= maxRounds)

  let variablesMap =
    if success then
      variables
      |> Seq.map (fun x -> (x.Key, x.Value))
      |> Map.ofSeq
    else
      [] |> Map.ofList

  let conflictsMap =
    if success then
      []
    else
      conflicts
      |> Seq.map (fun x -> (x.Key, variables[x.Key], x.Value))
      |> Seq.toList
  (success, variablesMap, conflictsMap)

There are a couple supporting components to this algorithm. The first is variable initialization. This just takes each variable, and assigns it to a random value from its domain. The second is calculating the conflicts for the current set of variables’ values. It returns the state of each variable, if it is in a conflicted state or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
let initVariables (variables: Variables) :Dictionary<Id, int> =
  let variableValues = new Dictionary<Id, int>()

  variables
  |> Map.toList
  |> List.map (fun (vId, vDomain) ->
      let i = rand.Next(vDomain.Length)
      (vId, vDomain[i]))
  |> List.iter (fun (id, value) -> variableValues.Add(id, value))

  variableValues

let getConflicts (constraints: NaryConstraints) (variables: Dictionary<Id, int>) :Dictionary<Id, bool> =
  let mutable conflicts = new Dictionary<Id, bool>()
  variables
  |> Seq.iter (fun x -> conflicts.Add(x.Key, false))

  // For each constraint, determine if there is a conflict
  for (ids, f) in constraints do
    let values =
      ids
      |> Array.map (fun id -> variables[id])

    let success = f values
    if not success then
      // There was a conflict, flag all impacted variables
      for id in ids do
        conflicts[id] <- true

  conflicts

Time to put it all together and see how it works. Below is a definition of the problem. As mentioned above, the constraints use arrays of variables. Admittedly this is not my preferred way of doing things. It lacks the explicit definitions I prefer. But its the only way to provide the arity flexibility I need. There are 4 variables, with varying ranges. Lastly are the constraint definitions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// Constraints
let even (a: int[]) = a[0] % 2 = 0
let different (a: int[]) = a[0] <> a[1]
let lessThan (a: int[]) = a[0] < a[1]
let multiSumCompare (a: int[]) =
  let x = a[0]
  let y = a[1..]
  Array.sum y < x

// Variables and their domains
let variables =
  [ [ 1 .. 100 ]
    [ 1 .. 100 ]
    [ 1 .. 100 ]
    [ 1 .. 100 ] ]
  |> listToVariables

// Nary constraints
let constraints =
  [
    ([| 0 |], even)
    ([| 1 |], even)
    ([| 3 |], odd)
    ([| 0; 1 |], lessThan)
    ([| 1; 2 |], lessThan)
    ([| 3; 0; 1; 2 |], multiSumCompare)
  ]

The solving looks like below. For this example, the maximum number of rounds is 5. For a real problem this would need to be higher.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Solve
let (success, reducedVariables, conflicts) = solve 5 constraints variables

// Display results
printfn "success: %b" success

// variable values (if success)
reducedVariables
|> Map.toList
|> List.iter (fun x -> printfn "%A" x)

// conflicts (if failure)
conflicts
|> List.iter (fun (k,v,c) ->
    printfn "Variable %d with Value %d has a Conflict %b" k v c)

Here is an example of finding a successful solution to the defined problem.

1
2
3
4
5
success: true
(0, 2)
(1, 8)
(2, 10)
(3, 81)

Here is an example where a successful solution could not be found. The results include where the conflicts arise. This is a case where in the real world a partial solution might be good enough. If so, you can use it. If not, then the solver needs to be run again, perhaps with a higher rounds configuration.

1
2
3
4
5
success: false
Variable 0 with Value 7 has a Conflict true
Variable 1 with Value 0 has a Conflict true
Variable 2 with Value 19 has a Conflict false
Variable 3 with Value 29 has a Conflict false

These examples give a glimpse into how a Min Conflicts algorithm can be implemented and used when dealing with constraint satisfaction problems. I hope you enjoyed this small view into how F# can be used to build interesting things. Until next time.

Related Posts: