Instances on Chess-Board

The instances are created by 3k x 3k chess-board, k = 1,2,... The boundaries of the chess-board are identified to get a torus. The Uncapacitated Facility Location Problem has n =9k² facilities and m = n customers. The facility i can serve the customer j if the corresponding cells of the chess-board have at least one common point. In other words, the facility is a chess king which captures all neighbor cells. Opening cost of each facility is equal 3000. The matrix g_ijhas 9 non-forbidden (non-infinited) elements from the set {0, 1, 2, 3, 4} in each row and column. The optimal solution contains k² opened facilities and corresponds to the minimal number of chess kings which can capture all cells. The total number of sets with k² facilities which cover the chess-board equals 2*3^(k+1)-9 and grows exponentially as k increases. The instances for k = 4, n=m=144 are given in the tables. Allocation of local optima for the first instance one can see on the diagram.

Code	The optimal value	Duality Gap (%)	The optimal solution
334	48258.00	0.01	3, 6, 21, 36, 39, 42, 57, 72, 75, 78, 93, 108, 111, 114, 129, 144
434	48247.00	0.00	2, 5, 8, 11, 38, 41, 44, 47, 73, 76, 79, 82, 109, 112, 115, 118
534	48246.00	0.00	1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84, 111, 114, 117, 120
634	48235.00	0.01	26, 29, 32, 35, 63, 66, 69, 72, 99, 102, 105, 108, 134, 137, 140, 143
734	48257.00	0.01	15, 18, 21, 24, 51, 54, 57, 60, 85, 88, 91, 94, 121, 124, 127, 130
834	48236.00	0.00	2, 5, 8, 11, 38, 41, 44, 47, 74, 77, 80, 83, 110, 113, 116, 119
934	48249.00	0.00	2, 5, 11, 32, 38, 41, 47, 68, 74, 77, 83, 104, 110, 113, 119, 140
1034	48239.00	0.01	3, 6, 9, 12, 39, 42, 45, 48, 74, 77, 80, 83, 109, 112, 115, 118
1134	48232.00	0.00	10, 13, 16, 19, 46, 49, 52, 55, 82, 85, 88, 91, 118, 121, 124, 127
1234	48244.00	0.01	26, 29, 32, 35, 63, 66, 69, 72, 97, 100, 103, 106, 135, 138, 141, 144
1334	48249.00	0.01	16, 25, 31, 34, 52, 61, 67, 70, 88, 97, 103, 106, 124, 133, 139, 142
1434	48247.00	0.00	25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103, 106, 133, 136, 139, 142
1534	48247.00	0.00	6, 9, 27, 36, 42, 45, 63, 72, 78, 81, 99, 108, 114, 117, 135, 144
1634	48250.00	0.00	13, 16, 19, 22, 51, 54, 57, 60, 85, 88, 91, 94, 121, 124, 127, 130
1734	48247.00	0.01	25, 28, 31, 34, 62, 65, 68, 71, 97, 100, 103, 106, 135, 138, 141, 144
1834	48253.00	0.00	8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116, 125, 134, 143
1934	48251.00	0.00	26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103, 106, 134, 137, 140, 143
2034	48243.00	0.01	8, 17, 26, 35, 44, 53, 62, 71, 80, 89, 98, 107, 116, 125, 134, 143
2134	48242.00	0.01	25, 28, 31, 34, 62, 65, 68, 71, 98, 101, 104, 107, 134, 137, 140, 143
2234	48249.00	0.01	1, 4, 7, 10, 38, 41, 44, 47, 75, 78, 81, 84, 111, 114, 117, 120
2334	48250.00	0.01	9, 12, 18, 27, 45, 48, 54, 63, 81, 84, 90, 99, 117, 120, 126, 135
2434	48249.00	0.01	27, 30, 33, 36, 63, 66, 69, 72, 97, 100, 103, 106, 134, 137, 140, 143
2534	48256.00	0.01	3, 6, 9, 12, 38, 41, 44, 47, 75, 78, 81, 84, 110, 113, 116, 119
2634	48239.00	0.01	7, 10, 16, 25, 43, 46, 52, 61, 79, 82, 88, 97, 115, 118, 124, 133
2734	48248.00	0.01	7, 13, 28, 34, 43, 49, 64, 70, 79, 85, 100, 106, 115, 121, 136, 142
2834	48232.00	0.00	27, 30, 33, 36, 61, 64, 67, 70, 99, 102, 105, 108, 134, 137, 140, 143
2934	48239.00	0.01	13, 16, 19, 34, 49, 52, 55, 70, 85, 88, 91, 106, 121, 124, 127, 142
3034	48247.00	0.01	3, 6, 9, 12, 38, 41, 44, 47, 74, 77, 80, 83, 110, 113, 116, 119
3134	48239.00	0.00	26, 29, 32, 35, 61, 64, 67, 70, 97, 100, 103, 106, 133, 136, 139, 142
3234	48226.00	0.00	5, 11, 14, 20, 41, 47, 50, 56, 77, 83, 86, 92, 113, 119, 122, 128