Pedro Roque / PHACT_src

Blame view

src/csps/qap.c 14.4 KB
Edit Raw Normal View History
94b2b13d   Pedro Roque   PHACT source 
1
2
3
4
 
/*
 * qap.c
 *
 *  Created on: 12/12/2016
4d26a735   Pedro Roque   Increased recogni... 
5
 
 *      Author: pedro
94b2b13d   Pedro Roque   PHACT source 
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
 *
 *		http://anjos.mgi.polymtl.ca/qaplib//
 *
 *		Quadratic assignment problem:
 *      There are a set of n facilities and a set of n locations. For each pair of locations,
 *      a distance is specified and for each pair of facilities a weight or flow is specified
 *      (e.g., the amount of supplies transported between the two facilities). The problem is
 *      to assign all facilities to different locations with the goal of minimizing the sum of
 *      the distances multiplied by the corresponding flows.
 */

#include "qap.h"

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "../config.h"
#include "../constraints/all_different.h"
4d26a735   Pedro Roque   Increased recogni... 
26
27
 
#include "../constraints/element_var.h"
#include "../constraints/linear_var.h"
94b2b13d   Pedro Roque   PHACT source 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
#include "../constraints/minimize.h"
#include "../split.h"
#include "../variables.h"

unsigned int p2_flow[] = { 0, 1, 3, 0 };
unsigned int p2_dist[] = { 0, 4, 2, 0 };

unsigned int p2c_flow[] = { 0, 1, 0, 0 };
unsigned int p2c_dist[] = { 3, 5, 7, 9 };

unsigned int p3_flow[] = { 0, 1, 4, 1, 0, 2, 4, 2, 0 };
unsigned int p3_dist[] = { 0, 2, 4, 2, 0, 1, 4, 1, 0 };

unsigned int p3b_flow[] = { 0, 1, 1, 1, 0, 1, 1, 1, 0 };
unsigned int p3b_dist[] = { 0, 1, 1, 1, 0, 1, 1, 1, 0 };

unsigned int p3c_flow[] = { 0, 0, 1, 0, 0, 0, 0, 0, 0 };
unsigned int p3c_dist[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

unsigned int p5_flow[] = { 0, 1, 2, 1, 0, 1, 0, 2, 1, 0, 2, 2, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0 };
unsigned int p5_dist[] = { 0, 5, 1, 3, 2, 5, 0, 2, 1, 4, 1, 2, 0, 2, 1, 3, 1, 2, 0, 2, 2, 4, 1, 2, 0 };
4d26a735   Pedro Roque   Increased recogni... 
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
 
unsigned int p10_flow[] = { 0, 1, 2, 1, 0, 0, 1, 2, 1, 0, 1, 0, 2, 1, 0, 0, 1, 2, 0, 1, 2, 2, 0, 1, 0, 0, 1, 0, 2, 2, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0,
		0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 2, 2, 0, 1, 0, 0, 1, 0, 2, 2, 1, 0, 2, 1, 0, 0, 1, 2, 0, 1, 0, 1, 2, 1, 0, 0, 1, 2, 1, 0 };
unsigned int p10_dist[] = { 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0,
		1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0 };

unsigned int choi15_flow[] = {
  16,  4,  6,  8,  7,  4,  6,  8,  7,  4,  6,  8,  7,  4,  6,
   4,  6,  1,  3,  4,  6,  1,  3,  4,  6,  1,  3,  4,  6,  1,
   6,  1,  4,  2,  6,  1,  9,  2,  6,  1,  9,  2,  6,  1,  9,
   8,  3,  2, 10,  8,  3,  2,  5,  8,  3,  2,  5,  8,  3,  2,
   7,  4,  6,  8, 16,  4,  6,  8,  7,  4,  6,  8,  7,  4,  6,
   4,  6,  1,  3,  4,  6,  1,  3,  4,  6,  1,  3,  4,  6,  1,
   6,  1,  9,  2,  6,  1,  4,  2,  6,  1,  9,  2,  6,  1,  9,
   8,  3,  2,  5,  8,  3,  2, 10,  8,  3,  2,  5,  8,  3,  2,
   7,  4,  6,  8,  7,  4,  6,  8, 16,  4,  6,  8,  7,  4,  6,
   4,  6,  1,  3,  4,  6,  1,  3,  4,  6,  1,  3,  4,  6,  1,
   6,  1,  9,  2,  6,  1,  9,  2,  6,  1,  4,  2,  6,  1,  9,
   8,  3,  2,  5,  8,  3,  2,  5,  8,  3,  2, 10,  8,  3,  2,
   7,  4,  6,  8,  7,  4,  6,  8,  7,  4,  6,  8, 16,  4,  6,
   4,  6,  1,  3,  4,  6,  1,  3,  4,  6,  1,  3,  4,  6,  1,
   6,  1,  9,  2,  6,  1,  9,  2,  6,  1,  9,  2,  6,  1,  4
};

unsigned int choi15_dist[] = {
  1, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2,
  1, 2, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3,
  2, 1, 3, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4,
  3, 2, 1, 4, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5,
  4, 3, 2, 1, 5, 1, 2, 3, 4, 5, 6, 7, 8, 7, 6,
  5, 4, 3, 2, 1, 6, 1, 2, 3, 4, 5, 6, 7, 8, 7,
  6, 5, 4, 3, 2, 1, 7, 1, 2, 3, 4, 5, 6, 7, 8,
  7, 6, 5, 4, 3, 2, 1, 8, 1, 2, 3, 4, 5, 6, 7,
  8, 7, 6, 5, 4, 3, 2, 1, 7, 1, 2, 3, 4, 5, 6,
  7, 8, 7, 6, 5, 4, 3, 2, 1, 6, 1, 2, 3, 4, 5,
  6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 5, 1, 2, 3, 4,
  5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 4, 1, 2, 3,
  4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 3, 1, 2,
  3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 2, 1,
  2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1, 1
};

unsigned int esc16i_flow[] = {
  0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 1, 2, 0, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 1, 3, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 1, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
94b2b13d   Pedro Roque   PHACT source 
110
111
112
113
 
unsigned int esc16i_dist[] = {
  0, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3,
  0, 0, 1, 0, 1, 0, 2, 1, 1, 0, 2, 1, 2, 1, 3, 2,
  0, 1, 0, 0, 1, 2, 0, 1, 1, 2, 0, 1, 2, 3, 1, 2,
4d26a735   Pedro Roque   Increased recogni... 
114
 
  1, 0, 0, 0, 2, 1, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1,
94b2b13d   Pedro Roque   PHACT source 
115
 
  0, 1, 1, 2, 0, 0, 0, 1, 1, 2, 2, 3, 0, 1, 1, 2,
4d26a735   Pedro Roque   Increased recogni... 
116
117
 
  1, 0, 2, 1, 0, 0, 1, 0, 2, 1, 3, 2, 1, 0, 2, 1,
  1, 2, 0, 1, 0, 1, 0, 0, 2, 3, 1, 2, 1, 2, 0, 1,
94b2b13d   Pedro Roque   PHACT source 
118
119
120
 
  2, 1, 1, 0, 1, 0, 0, 0, 3, 2, 2, 1, 2, 1, 1, 0,
  0, 1, 1, 2, 1, 2, 2, 3, 0, 0, 0, 1, 0, 1, 1, 2,
  1, 0, 2, 1, 2, 1, 3, 2, 0, 0, 1, 0, 1, 0, 2, 1,
4d26a735   Pedro Roque   Increased recogni... 
121
122
 
  1, 2, 0, 1, 2, 3, 1, 2, 0, 1, 0, 0, 1, 2, 0, 1,
  2, 1, 1, 0, 3, 2, 2, 1, 1, 0, 0, 0, 2, 1, 1, 0,
94b2b13d   Pedro Roque   PHACT source 
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
169
170
171
172
173
174
175
176
177
178
 
  1, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 0, 0, 0, 1,
  2, 1, 3, 2, 1, 0, 2, 1, 1, 0, 2, 1, 0, 0, 1, 0,
  2, 3, 1, 2, 1, 2, 0, 1, 1, 2, 0, 1, 0, 1, 0, 0,
  3, 2, 2, 1, 2, 1, 1, 0, 2, 1, 1, 0, 1, 0, 0, 0
};

unsigned int esc16e_flow[] = {
  0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 1, 1, 0, 2, 3, 2, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 1, 1, 2, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 1, 1, 3, 2, 0, 2, 0, 0, 0, 0, 0, 0, 0,
  1, 0, 0, 1, 1, 2, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

unsigned int esc16e_dist[] = {
  0, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3,
  0, 0, 1, 0, 1, 0, 2, 1, 1, 0, 2, 1, 2, 1, 3, 2,
  0, 1, 0, 0, 1, 2, 0, 1, 1, 2, 0, 1, 2, 3, 1, 2,
  1, 0, 0, 0, 2, 1, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1,
  0, 1, 1, 2, 0, 0, 0, 1, 1, 2, 2, 3, 0, 1, 1, 2,
  1, 0, 2, 1, 0, 0, 1, 0, 2, 1, 3, 2, 1, 0, 2, 1,
  1, 2, 0, 1, 0, 1, 0, 0, 2, 3, 1, 2, 1, 2, 0, 1,
  2, 1, 1, 0, 1, 0, 0, 0, 3, 2, 2, 1, 2, 1, 1, 0,
  0, 1, 1, 2, 1, 2, 2, 3, 0, 0, 0, 1, 0, 1, 1, 2,
  1, 0, 2, 1, 2, 1, 3, 2, 0, 0, 1, 0, 1, 0, 2, 1,
  1, 2, 0, 1, 2, 3, 1, 2, 0, 1, 0, 0, 1, 2, 0, 1,
  2, 1, 1, 0, 3, 2, 2, 1, 1, 0, 0, 0, 2, 1, 1, 0,
  1, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 0, 0, 0, 1,
  2, 1, 3, 2, 1, 0, 2, 1, 1, 0, 2, 1, 0, 0, 1, 0,
  2, 3, 1, 2, 1, 2, 0, 1, 1, 2, 0, 1, 0, 1, 0, 0,
  3, 2, 2, 1, 2, 1, 1, 0, 2, 1, 1, 0, 1, 0, 0, 0
};

unsigned int esc16g_flow[] = {
		0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 1, 0, 1, 1, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 1, 1, 0, 1, 2, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0,
		1, 2, 1, 1, 0, 3, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
		1, 1, 0, 2, 3, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 1, 2, 3, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4d26a735   Pedro Roque   Increased recogni... 
179
180
 
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
94b2b13d   Pedro Roque   PHACT source 
181
182
 
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
4d26a735   Pedro Roque   Increased recogni... 
183
 
		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
94b2b13d   Pedro Roque   PHACT source 
184
185
186
187
188
189
190
191
192
193
194
195
 
};

unsigned int esc16g_dist[] = {
		0, 0, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 2, 3,
		0, 0, 1, 0, 1, 0, 2, 1, 1, 0, 2, 1, 2, 1, 3, 2,
		0, 1, 0, 0, 1, 2, 0, 1, 1, 2, 0, 1, 2, 3, 1, 2,
		1, 0, 0, 0, 2, 1, 1, 0, 2, 1, 1, 0, 3, 2, 2, 1,
		0, 1, 1, 2, 0, 0, 0, 1, 1, 2, 2, 3, 0, 1, 1, 2,
		1, 0, 2, 1, 0, 0, 1, 0, 2, 1, 3, 2, 1, 0, 2, 1,
		1, 2, 0, 1, 0, 1, 0, 0, 2, 3, 1, 2, 1, 2, 0, 1,
		2, 1, 1, 0, 1, 0, 0, 0, 3, 2, 2, 1, 2, 1, 1, 0,
		0, 1, 1, 2, 1, 2, 2, 3, 0, 0, 0, 1, 0, 1, 1, 2,
4d26a735   Pedro Roque   Increased recogni... 
196
 
		1, 0, 2, 1, 2, 1, 3, 2, 0, 0, 1, 0, 1, 0, 2, 1,
94b2b13d   Pedro Roque   PHACT source 
197
198
199
200
201
 
		1, 2, 0, 1, 2, 3, 1, 2, 0, 1, 0, 0, 1, 2, 0, 1,
		2, 1, 1, 0, 3, 2, 2, 1, 1, 0, 0, 0, 2, 1, 1, 0,
		1, 2, 2, 3, 0, 1, 1, 2, 0, 1, 1, 2, 0, 0, 0, 1,
		2, 1, 3, 2, 1, 0, 2, 1, 1, 0, 2, 1, 0, 0, 1, 0,
		2, 3, 1, 2, 1, 2, 0, 1, 1, 2, 0, 1, 0, 1, 0, 0,
4d26a735   Pedro Roque   Increased recogni... 
202
 
		3, 2, 2, 1, 2, 1, 1, 0, 2, 1, 1, 0, 1, 0, 0, 0
94b2b13d   Pedro Roque   PHACT source 
203
204
205
206
207
208
209
210
211
212
213
 
};

/*
 * Solve one of the above instances of the Quadratic assignment problem
 */
void run_qap(char* csp_inst_name) {
	int n;
	int* p_flow;
	unsigned int* p_dist;
	unsigned long result;
	unsigned int d_max;
4d26a735   Pedro Roque   Increased recogni... 
214
215
 
	unsigned int cost;
	unsigned int* n_pos;
94b2b13d   Pedro Roque   PHACT source 
216
217
218
219
220
221
 
	unsigned int* new_dist;
	unsigned int vs[3];
	bool symmetrical = true;
	bool symmetrical_aux;
	int i, j;
4d26a735   Pedro Roque   Increased recogni... 
222
223
 
	if (!strcmp(csp_inst_name, "p2")) {
		n = 2;
94b2b13d   Pedro Roque   PHACT source 
224
 
		p_flow = (int*) p2_flow;
4d26a735   Pedro Roque   Increased recogni... 
225
 
		p_dist = p2_dist;
94b2b13d   Pedro Roque   PHACT source 
226
227
228
 
	} else if (!strcmp(csp_inst_name, "p2c")) {
		n = 2;
		p_flow = (int*) p2c_flow;
4d26a735   Pedro Roque   Increased recogni... 
229
 
		p_dist = p2c_dist;
94b2b13d   Pedro Roque   PHACT source 
230
231
232
233
 
	} else if (!strcmp(csp_inst_name, "p3")) {
		n = 3;
		p_flow = (int*) p3_flow;
		p_dist = p3_dist;
4d26a735   Pedro Roque   Increased recogni... 
234
235
 
	} else if (!strcmp(csp_inst_name, "p3b")) {
		n = 3;
94b2b13d   Pedro Roque   PHACT source 
236
 
		p_flow = (int*) p3b_flow;
4d26a735   Pedro Roque   Increased recogni... 
237
 
		p_dist = p3b_dist;
94b2b13d   Pedro Roque   PHACT source 
238
239
240
 
	} else if (!strcmp(csp_inst_name, "p3c")) {
		n = 3;
		p_flow = (int*) p3c_flow;
4d26a735   Pedro Roque   Increased recogni... 
241
242
 
		p_dist = p3c_dist;
	} else if (!strcmp(csp_inst_name, "p5")) {
94b2b13d   Pedro Roque   PHACT source 
243
244
245
 
		n = 5;
		p_flow = (int*) p5_flow;
		p_dist = p5_dist;
4d26a735   Pedro Roque   Increased recogni... 
246
 
	} else if (!strcmp(csp_inst_name, "p10")) {
94b2b13d   Pedro Roque   PHACT source 
247
248
249
250
251
 
		n = 10;
		p_flow = (int*) p10_flow;
		p_dist = p10_dist;
	} else if (!strcmp(csp_inst_name, "choi15")) {
		n = 15;
4d26a735   Pedro Roque   Increased recogni... 
252
253
254
 
		p_flow = (int*) choi15_flow;
		p_dist = choi15_dist;
	} else if (!strcmp(csp_inst_name, "esc16i")) {
94b2b13d   Pedro Roque   PHACT source 
255
256
 
		n = 16;
		p_flow = (int*) esc16i_flow;
4d26a735   Pedro Roque   Increased recogni... 
257
 
		p_dist = esc16i_dist;
94b2b13d   Pedro Roque   PHACT source 
258
259
 
	} else if (!strcmp(csp_inst_name, "esc16e")) {
		n = 16;
4d26a735   Pedro Roque   Increased recogni... 
260
261
 
		p_flow = (int*) esc16e_flow;
		p_dist = esc16e_dist;
94b2b13d   Pedro Roque   PHACT source 
262
 
	} else if (!strcmp(csp_inst_name, "esc16g")) {
4d26a735   Pedro Roque   Increased recogni... 
263
 
		n = 16;
94b2b13d   Pedro Roque   PHACT source 
264
265
 
		p_flow = (int*) esc16g_flow;
		p_dist = esc16g_dist;
4d26a735   Pedro Roque   Increased recogni... 
266
267
 
	} else {
		printf("\n%s QAP problem is not available. Please select an instance from \"csps/qap.c\" file.\n", csp_inst_name);
94b2b13d   Pedro Roque   PHACT source 
268
269
270
271
272
 
		return;
	}

	int cs[] = { n, 1, 1 };
4d26a735   Pedro Roque   Increased recogni... 
273
 
	unsigned int* pos = malloc((unsigned int)n * sizeof(unsigned int));
94b2b13d   Pedro Roque   PHACT source 
274
275
276
277
278
 
	unsigned int* dist = malloc((unsigned int)n * (unsigned int)n * sizeof(unsigned int));

	// see if the problem is symmetric
	for (i = 0; i < n; ++i) {
		for (j = 0; j < i; ++j) {
4d26a735   Pedro Roque   Increased recogni... 
279
 
			if (p_flow[i * n + j] != p_flow[j * n + i] || p_dist[i * n + j] != p_dist[j * n + i]) {
94b2b13d   Pedro Roque   PHACT source 
280
281
282
283
284
 
				symmetrical = false;
				break;
			}
		}
	}
4d26a735   Pedro Roque   Increased recogni... 
285
286
287
 

	// see if the cost associated with the main diagonal is 0
	symmetrical_aux = symmetrical;
94b2b13d   Pedro Roque   PHACT source 
288
289
 

	if (symmetrical) {
4d26a735   Pedro Roque   Increased recogni... 
290
 
		for (i = 0; i < n; ++i) {
94b2b13d   Pedro Roque   PHACT source 
291
292
293
294
295
296
 
			if (p_flow[i * n + i] != 0) {
				break;
			}
		}
		if (i < n) {
			for (i = 0; i < n; ++i) {
4d26a735   Pedro Roque   Increased recogni... 
297
 
				if (p_dist[i * n + i] != 0) {
94b2b13d   Pedro Roque   PHACT source 
298
299
300
301
302
303
304
305
306
307
308
 
					break;
				}
			}
		}
		if (i < n) {
			symmetrical_aux = false;
		}
	}

	d_max = 0;
	for (i = 0; i < n * n; ++i) {
4d26a735   Pedro Roque   Increased recogni... 
309
 
		d_max += (unsigned int)p_flow[i] * p_dist[i];
94b2b13d   Pedro Roque   PHACT source 
310
311
312
313
314
 
	}
	d_max++;
	if (d_max > 255) {
		d_max = 255;
	}
4d26a735   Pedro Roque   Increased recogni... 
315
94b2b13d   Pedro Roque   PHACT source 
316
317
318
319
320
321
322
323
324
325
326
 
	for (i = 0; i < n; ++i) {
		pos[i] = v_new_range(0, (unsigned int)n - 1, true);
	}
	c_all_different(pos, (unsigned int)n);

	cost = v_new_range(0, d_max, false);

	for (i = 0; i < n * n; ++i) {
		dist[i] = v_new_val(p_dist[i]);
	}