This is the fifty eighth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve kantoriiroodo riddle. Refer to the link to see how it works. Basically, we have a board of any size (like a chess board) divided into multiple “parcels” just like building parcels. Each parcel may (but is not obliged to) have a cost. We want to build a closed road (basically a loop) which goes through multiple fields and satisfies the following:

- It can enter and exit the parcel exactly once
- It must not cross itself
- It can go horizontally or vertically (so we cannot go diagonally, only four basic directions)
- Two neighboring fields may be empty in the solution if and only if they belong to the same parcel
- If parcel has a cost then it indicates how many fields of the parcel need to be occupied by road (no more, no less)

Let’s solve it with ILP. For each field we will have four variables indicating whether we have a road going up, down, left, or right. Full solution looks like this:

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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 |
var owners = new char[][] { new char[] { '1', '1', '2', '2', '3', '3', '4', '4', '4', '5' }, new char[] { '1', '1', '2', '6', '6', '3', '3', '4', '7', '7' }, new char[] { '8', '9', '9', '6', 'A', 'B', 'B', 'C', '7', '7' }, new char[] { '8', 'D', 'D', '6', 'A', 'E', 'C', 'C', 'F', 'F' }, new char[] { '8', 'G', 'D', '6', '6', 'E', 'H', 'H', 'I', 'F' }, new char[] { 'J', 'G', 'D', 'D', 'K', 'L', 'L', 'H', 'I', 'M' }, new char[] { 'J', 'J', 'N', 'N', 'K', 'O', 'L', 'H', 'H', 'M' }, new char[] { 'P', 'P', 'N', 'Q', 'Q', 'O', 'L', 'R', 'R', 'M' }, new char[] { 'P', 'P', 'S', 'T', 'T', 'L', 'L', 'U', 'V', 'V' }, new char[] { 'W', 'S', 'S', 'S', 'T', 'T', 'U', 'U', 'V', 'V' } }; var mustTake = new Dictionary<char, int>() { { '1', 4 }, { '4', 3 }, { '6', 2 }, { '7', 4 }, { 'D', 3 }, { 'F', 2 }, { 'J', 2 }, { 'L', 4 }, { 'M', 2 }, { 'N', 1 }, { 'P', 2 }, { 'S', 3 }, { 'U', 3 }, { 'V', 1 } }; var height = owners.Length; var width = owners[0].Length; var solver = new CplexMilpSolver(23); dynamic fields = Enumerable.Range(0, height).Select(i => Enumerable.Range(0, width).Select(j => new System.Dynamic.ExpandoObject()).ToArray()).ToArray(); for(int i = 0;i<height;++i) { for(int j = 0;j<width;++j) { IVariable right = j < width - 1 ? solver.CreateAnonymous(Domain.BinaryInteger) : null; IVariable bottom = i < height - 1 ? solver.CreateAnonymous(Domain.BinaryInteger) : null; IVariable top = i > 0 ? solver.CreateAnonymous(Domain.BinaryInteger) : null; IVariable left = j > 0 ? solver.CreateAnonymous(Domain.BinaryInteger) : null; fields[i][j].Right = right; fields[i][j].Bottom = bottom; fields[i][j].Top = top; fields[i][j].Left = left; if(j > 0) { solver.Set(ConstraintType.Equal, left, fields[i][j-1].Right); } if(i > 0) { solver.Set(ConstraintType.Equal, top, fields[i-1][j].Bottom); } fields[i][j].All = new IVariable[] { right, bottom, left, top }.Where(x => x != null).ToArray(); } } Console.WriteLine("Make sure field is used at most once"); for(int i = 0;i<height;++i) { for(int j = 0;j<width;++j) { var sum = solver.Operation(OperationType.Addition, fields[i][j].All); var isEmpty = solver.Operation(OperationType.IsEqual, sum, solver.FromConstant(0)); var isInOut = solver.Operation(OperationType.IsEqual, sum, solver.FromConstant(2)); var or = solver.Operation(OperationType.Disjunction, isEmpty, isInOut); solver.Set(ConstraintType.Equal, or, solver.FromConstant(1)); } } Console.WriteLine("Make sure the road is a loop - most likely not needed"); Console.WriteLine("Make sure neighbouring fields for different owners are not both empty"); for(int i = 0;i<height;++i) { for(int j = 0;j<width;++j) { if(i < height - 1) { if(owners[i][j] != owners[i+1][j]) { IVariable[] a = fields[i][j].All; IVariable[] b = fields[i+1][j].All; solver.Set(ConstraintType.GreaterOrEqual, solver.Operation(OperationType.Addition, a.Concat(b).ToArray()), solver.FromConstant(1)); } } if(j < width - 1) { if(owners[i][j] != owners[i][j+1]) { IVariable[] a = fields[i][j].All; IVariable[] b = fields[i][j+1].All; solver.Set(ConstraintType.GreaterOrEqual, solver.Operation(OperationType.Addition, a.Concat(b).ToArray()), solver.FromConstant(1)); } } } } Console.WriteLine("Make sure we use exact number of fields in owners"); foreach(var key in mustTake.Keys) { var fieldsToUse = mustTake[key]; var usedFields = new List<IVariable>(); for(int i = 0;i<height;++i) { for(int j = 0;j<width;++j) { if(owners[i][j] == key) { usedFields.Add(solver.Operation(OperationType.Disjunction, fields[i][j].All)); } } } solver.Set(ConstraintType.Equal, solver.Operation(OperationType.Addition, usedFields.ToArray()), solver.FromConstant(fieldsToUse)); } Console.WriteLine("Make sure we enter and exit the owner exactly once"); foreach(var key in owners.SelectMany(r => r).Distinct()) { var outerEdges = new List<IVariable>(); for(int i = 0;i<height;++i) { for(int j = 0;j<width;++j) { if(owners[i][j] == key) { if(i > 0 && owners[i-1][j] != key) { outerEdges.Add(fields[i][j].Top); } if(i < height - 1 && owners[i+1][j] != key) { outerEdges.Add(fields[i][j].Bottom); } if(j > 0 && owners[i][j-1] != key) { outerEdges.Add(fields[i][j].Left); } if(j < width - 1 && owners[i][j+1] != key) { outerEdges.Add(fields[i][j].Right); } } } } solver.Set(ConstraintType.Equal, solver.Operation(OperationType.Addition, outerEdges.ToArray()), solver.FromConstant(2)); } var goal = solver.FromConstant(0); solver.AddGoal("Goal", goal); solver.Solve(); for(int i = 0;i<height;++i) { for(int j = 0;j<width;++j) { var top = i > 0 ? solver.GetValue(fields[i][j].Top) > 0 : false; var right = j < width -1 ? solver.GetValue(fields[i][j].Right) > 0 : false; var left = j > 0 ? solver.GetValue(fields[i][j].Left) > 0 : false; var bottom = i < height - 1 ? solver.GetValue(fields[i][j].Bottom) > 0 : false; if(top && bottom) Console.Write("¦"); if(top && left) Console.Write("+"); if(top && right) Console.Write("+"); if(left && right) Console.Write("-"); if(bottom && left) Console.Write("+"); if(bottom && right) Console.Write("+"); if(top == left && left == right && right == bottom && bottom == false) Console.Write("o"); } Console.WriteLine(); } |

In lines 1-12 we specify the parcels. The example is from the linked blog (the second example, without given solution). You can see each character denotes parcel owner.

In lines 14-29 we specify how many fields we need to take for the road for each parcel with a cost. Notice that some parcels do not have a cost.

First, in lines 38-60 we initialize variables for each directions. Not all variables exist as we can go out of the board. Each variable is a binary integer denoting whether given direction is used for the road or not. Also, we make sure that if we go up from some field then we at the same time go down from the field above (and the same for other directions).

Lines 62-72 specify that we use each field exactly once – the road doesn’t cross itself. For that we must have either zero directions used in the field (meaning there is no road in the field) or exactly two directions.

In lines 76-96 we make sure neighboring fields of different parcels are not empty. We iterate through fields and check if they have same owners – if they don’t then we add directions for both of them and make sure they are not zero (so there will be road in at least one of the fields).

In lines 98-114 we take the cost into account. For each parcel with a cost we find its fields, for each field we calculate a binary indicating whether there is a road or not (by using disjunction), finally we add all these results and make sure correct number of fields is used.

In lines 118-144 we make sure we enter and exit the parcel exactly once. For each field of the parcel we find its outer directions, add all of them and make sure there is one entrance and one exit.

Finally, we add a dummy goal and that’s all.

You may notice we didn’t specify the requirement that the road is a loop. This doesn’t break the solution but in general should be added as well. This can’t be added as a local requirement for each neighboring fields, should be considered globally and hence is slightly more sophisticated.

Result:

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 |
Tried aggregator 4 times. MIP Presolve eliminated 1264 rows and 611 columns. MIP Presolve modified 2799 coefficients. Aggregator did 672 substitutions. Reduced MIP has 410 rows, 233 columns, and 1706 nonzeros. Reduced MIP has 233 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 0.02 sec. (11.91 ticks) Found incumbent of value 0.000000 after 0.02 sec. (14.03 ticks) Root node processing (before b&c): Real time = 0.02 sec. (14.10 ticks) Parallel b&c, 4 threads: Real time = 0.00 sec. (0.00 ticks) Sync time (average) = 0.00 sec. Wait time (average) = 0.00 sec. ------------ Total (root+branch&cut) = 0.02 sec. (14.10 ticks) ┌┐┌--┐o┌-┐ │││oo└┐│┌┘ │└┘o┌-┘│└┐ │oo┌┘┌-┘o│ └┐┌┘o│oo┌┘ o│└-┐└┐┌┘o ┌┘oo└┐│└-┐ │o┌┐o└┘o┌┘ │o│└┐oo┌┘o └-┘o└--┘oo |

And the image: