Optimization on a square lattice: Torsten Sillke, FRA, June 1997 Problem: (Ingo Alth"ofer, Jena, 31. Jan 1995) -------- Arrange the four letters {A,B,C,D} into a 5x5 square. You have to use 9*A, 6*B, 5*C, and 5*D. Adjacent letters get a cost shown in the following table: Cost Phi: A B C D +----------- A | 0 0 1 4 B | 0 3 2 2 C | 1 2 0 0 D | 4 2 0 0 The cost table is symmetric. Determine all arrangements which give the minimal total cost according the cost function Phi. Example arrangement: B D A B C 8 A C A A D 6 C A C A B 3 B C D B B 7 A D D A A 8 3 2 1 0 5 The numbers give the sum of cost in each row and column. The total sum of cost for this example is 43. Solution: (Torsten Sillke, FRA, 8. June 1995) --------- I make the following chain of reduction: - 4 letter optimization problem - 2 letter optimization problem - isoperimetric problem (graphs) - isoperimetric problem (geometric) Reduction to a 2 letter optimization problem: Replace the cost function Phi by Phi' which has lower cost. The minimal total cost of Phi' will give a lower bound for the minimal total cost of Phi. Cost Phi': A B C D +----------- A | 0 0 1 1 B | 0 0 1 1 C | 1 1 0 0 D | 1 1 0 0 But for Phi' A and B as well as C and D become equal. So we only have two distinct letters '0' for A or B and '1' for C or D. Our new two letter problem can be written with a new cost function Psi. Cost Psi: 0 1 +----- 0 | 0 1 1 | 1 0 We have 15 * '0' (9*A and 6*B) and 10 * '1' (5*C and 5*D). The reduced problem is to find a 5*5 square arrangement of 15 * '0' and 10 * '1' such that the number of adjacent '0' and '1' is minimal. This is a isoperimetric problem. The isoperimetric problem in the 2-dimensional lattice: This discrete (edge version) of the isoperimetric problem has been analyzed by B. Bollobas and I. Leader. In this case (seperating 10 points in a 5*5 grid) it is sufficient to consider the geometric isoperimetric problem with a boarder which is parrallel to the axis. Local optimal configurations are: type 1 | |________ | | | | | A = 10 | (inner) boarder length = 2*sqrt(10) = 6.32 | | |________|______ type 2 | | |_______________| | | | A = 10 | (inner) boarder length = 5 |_______________| Going back to the discrete problem we have for the type 1 has a boarder length of at least 7, _ _ _ x x| x|_ _ x x|_ x x x| examples of boarder length = 7 x x x| x x x| x x x| x x x| type 2 has a boarder length a least 5. _ _ _ _ _ x x x x x x x x x x A boarder length 6 is not possible as a 'one step' boarder is impossible for type 2 for aera 10. ------------------------------------------------------ Discretization don't increase the boarder for type 2. Therefore we get total cost = 5 for function Psi. ------------------------------------------------------ The unique arrangement with total cost 5 is: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 So we have a lower bound for Phi' and therefore for Phi. ------------------------------------------------------ The total cost for Phi is at least 5. ------------------------------------------------------ Going back from Psi to Phi: The (0, 1)-problem has a unique solution with cost Psi 5. If there is a solution with total cost 5 of the Phi function, this will give a total cost 5 solution of the Psi function. To get minimal costs only placements which give Phi(x,y) = Phi'(x,y) are allowed. In the following table all combinations which are forbidden are marked with '-'. Cost Phi'': A B C D +----------- A | 0 0 1 - B | 0 - - - C | 1 - 0 0 D | - - 0 0 Dissect the 5*5 square in the following seven regions 'a' to 'g': a b c d e a b c d e f f f f f g g g g g g g g g g Now there are 6 letters 'B' to place on the upper three rows. If there was a 'B' on a f-place we would have a B-C of B-D combination which is forbidden. Therefore all 'B' must be on places 'a' to 'e'. By the pigeonhole principle one region must contain a double 'B'. But a B-B combination is forbidden. This shows that total cost 5 for the Phi function is impossible. ------------------------------------------------------ The total cost for Phi is at least 6. ------------------------------------------------------ The construction of all solutions with total cost 6: There is no (0, 1)-solution of total cost 6. (This could have been of type 2 only.) Therefore a total cost 6 solution of Phi results in the total cost 5 solution of Psi. To get minimal costs only placements which give Phi(x,y) <= Phi'(x,y) + 1 are allowed. In the following table all combinations which are forbidden are marked with '-'. Cost Phi'': A B C D +----------- A | 0 0 1 - B | 0 - 2 2 C | 1 2 0 0 D | - 2 0 0 Region 'f' must contain exactly one 'B' (this will increase 5 to 6). The regions 'a' to 'e' can be filled in two different ways: A B A B A B A B A B B A B A B A B A B A This gives for the upper part the five possibilities: B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A B A A A A A B A A A A A B A A A A A B A A A A A B At the boarder between the regions 'f' and 'g' we will find four A-C combinations. The last 'C' can be placed anywhere as B-C and B-D cost the same. Therefore we get in total 16 different solutions (ignoring reflections). The two symmetric ones are: B A B A B B A B A B A B A B A A B A B A A A B A A A A B A A C C C C C C C D C C D D D D D D D C D D Ingo says he constructed the problem by random.