Pedro Roque / PHACT_src

Blame view

Debug/src/csps/qap.c 14.1 KB
Edit Raw Normal View History
0c8ce2b0   Pedro Roque   missing files 
1
2
3
4
 
/*
 * qap.c
 *
 *  Created on: 12/12/2016
4d26a735   Pedro Roque   Increased recogni... 
5
 
 *      Author: Pedro
0c8ce2b0   Pedro Roque   missing files 
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/array_var_int_element.h"
#include "../constraints/int_lin_var.h"
0c8ce2b0   Pedro Roque   missing files 
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 };

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, 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 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, 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 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, 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 };
0c8ce2b0   Pedro Roque   missing files 
110
111
112
113
 

/*
 * Solve one of the above instances of the Quadratic assignment problem
 */
4d26a735   Pedro Roque   Increased recogni... 
114
 
void run_qap(char *csp_inst_name) {
0c8ce2b0   Pedro Roque   missing files 
115
 
	int n;
4d26a735   Pedro Roque   Increased recogni... 
116
117
 
	int *p_flow;
	unsigned int *p_dist;
0c8ce2b0   Pedro Roque   missing files 
118
119
120
 
	unsigned long result;
	unsigned int d_max;
	unsigned int cost;
4d26a735   Pedro Roque   Increased recogni... 
121
122
 
	unsigned int *n_pos;
	unsigned int *new_dist;
0c8ce2b0   Pedro Roque   missing files 
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
 
	unsigned int vs[3];
	bool symmetrical = true;
	bool symmetrical_aux;
	int i, j;

	if (!strcmp(csp_inst_name, "p2")) {
		n = 2;
		p_flow = (int*) p2_flow;
		p_dist = p2_dist;
	} else if (!strcmp(csp_inst_name, "p2c")) {
		n = 2;
		p_flow = (int*) p2c_flow;
		p_dist = p2c_dist;
	} else if (!strcmp(csp_inst_name, "p3")) {
		n = 3;
		p_flow = (int*) p3_flow;
		p_dist = p3_dist;
	} else if (!strcmp(csp_inst_name, "p3b")) {
		n = 3;
		p_flow = (int*) p3b_flow;
		p_dist = p3b_dist;
	} else if (!strcmp(csp_inst_name, "p3c")) {
		n = 3;
		p_flow = (int*) p3c_flow;
		p_dist = p3c_dist;
	} else if (!strcmp(csp_inst_name, "p5")) {
		n = 5;
		p_flow = (int*) p5_flow;
		p_dist = p5_dist;
	} else if (!strcmp(csp_inst_name, "p10")) {
		n = 10;
		p_flow = (int*) p10_flow;
		p_dist = p10_dist;
	} else if (!strcmp(csp_inst_name, "choi15")) {
		n = 15;
		p_flow = (int*) choi15_flow;
		p_dist = choi15_dist;
	} else if (!strcmp(csp_inst_name, "esc16i")) {
		n = 16;
		p_flow = (int*) esc16i_flow;
		p_dist = esc16i_dist;
	} else if (!strcmp(csp_inst_name, "esc16e")) {
		n = 16;
		p_flow = (int*) esc16e_flow;
		p_dist = esc16e_dist;
	} else if (!strcmp(csp_inst_name, "esc16g")) {
		n = 16;
		p_flow = (int*) esc16g_flow;
		p_dist = esc16g_dist;
	} else {
		printf("\n%s QAP problem is not available. Please select an instance from \"csps/qap.c\" file.\n", csp_inst_name);
		return;
	}

	int cs[] = { n, 1, 1 };
4d26a735   Pedro Roque   Increased recogni... 
179
180
 
	unsigned int *pos = malloc((unsigned int) n * sizeof(unsigned int));
	unsigned int *dist = malloc((unsigned int) n * (unsigned int) n * sizeof(unsigned int));
0c8ce2b0   Pedro Roque   missing files 
181
182
 

	// see if the problem is symmetric
4d26a735   Pedro Roque   Increased recogni... 
183
 
	for (i = 0; i < n; i++) {
0c8ce2b0   Pedro Roque   missing files 
184
185
186
187
188
189
190
191
192
193
194
195
 
		for (j = 0; j < i; ++j) {
			if (p_flow[i * n + j] != p_flow[j * n + i] || p_dist[i * n + j] != p_dist[j * n + i]) {
				symmetrical = false;
				break;
			}
		}
	}

	// see if the cost associated with the main diagonal is 0
	symmetrical_aux = symmetrical;

	if (symmetrical) {
4d26a735   Pedro Roque   Increased recogni... 
196
 
		for (i = 0; i < n; i++) {
0c8ce2b0   Pedro Roque   missing files 
197
198
199
200
201
 
			if (p_flow[i * n + i] != 0) {
				break;
			}
		}
		if (i < n) {
4d26a735   Pedro Roque   Increased recogni... 
202
 
			for (i = 0; i < n; i++) {
0c8ce2b0   Pedro Roque   missing files 
203
204
205
206
207
208
209
210
211
212
213
 
				if (p_dist[i * n + i] != 0) {
					break;
				}
			}
		}
		if (i < n) {
			symmetrical_aux = false;
		}
	}

	d_max = 0;
4d26a735   Pedro Roque   Increased recogni... 
214
215
 
	for (i = 0; i < n * n; i++) {
		d_max += (unsigned int) p_flow[i] * p_dist[i];
0c8ce2b0   Pedro Roque   missing files 
216
217
218
219
220
221
 
	}
	d_max++;
	if (d_max > 255) {
		d_max = 255;
	}
4d26a735   Pedro Roque   Increased recogni... 
222
223
 
	for (i = 0; i < n; i++) {
		pos[i] = v_new_range(0, (unsigned int) n - 1, true);
0c8ce2b0   Pedro Roque   missing files 
224
 
	}
4d26a735   Pedro Roque   Increased recogni... 
225
 
	c_all_different(pos, (unsigned int) n);
0c8ce2b0   Pedro Roque   missing files 
226
227
228
 

	cost = v_new_range(0, d_max, false);
4d26a735   Pedro Roque   Increased recogni... 
229
 
	for (i = 0; i < n * n; i++) {
0c8ce2b0   Pedro Roque   missing files 
230
231
232
233
 
		dist[i] = v_new_val(p_dist[i]);
	}

	if (!symmetrical_aux) {
4d26a735   Pedro Roque   Increased recogni... 
234
235
 
		new_dist = malloc((unsigned long) n * (unsigned long) n * sizeof(unsigned int));
		n_pos = malloc((unsigned long) n * (unsigned long) n * sizeof(unsigned int));
0c8ce2b0   Pedro Roque   missing files 
236
4d26a735   Pedro Roque   Increased recogni... 
237
 
		for (i = 0; i < n * n; i++) {
0c8ce2b0   Pedro Roque   missing files 
238
239
240
 
			new_dist[i] = v_new_range(0, d_max, false);
		}
4d26a735   Pedro Roque   Increased recogni... 
241
242
 
		for (i = 0; i < n * n; i++) {
			n_pos[i] = v_new_range(1, (unsigned int) n * (unsigned int) n, false);
0c8ce2b0   Pedro Roque   missing files 
243
244
245
 
		}

		vs[2] = v_new_val(1);	// element_var works with Y indexs from 1 to ... Because of Flatzinc specification
4d26a735   Pedro Roque   Increased recogni... 
246
 
		for (i = 0; i < n; i++) {
0c8ce2b0   Pedro Roque   missing files 
247
248
249
250
251
 
			vs[0] = pos[i];

			for (j = 0; j < n; ++j) {
				vs[1] = pos[j];
4d26a735   Pedro Roque   Increased recogni... 
252
253
254
 
				c_int_lin_var(cs, vs, 3, n_pos[i * n + j]);
				c_array_var_int_element(dist, (unsigned int) n * (unsigned int) n, n_pos[(unsigned int) i * (unsigned int) n + (unsigned int) j],
						new_dist[(unsigned int) i * (unsigned int) n + (unsigned int) j]);
0c8ce2b0   Pedro Roque   missing files 
255
256
 
			}
		}
4d26a735   Pedro Roque   Increased recogni... 
257
 
		c_int_lin_var(p_flow, new_dist, (unsigned int) n * (unsigned int) n, cost);
0c8ce2b0   Pedro Roque   missing files 
258
259
 

	} else {
4d26a735   Pedro Roque   Increased recogni... 
260
261
 
		new_dist = malloc((unsigned long) n * (unsigned long) n * sizeof(unsigned int));
		n_pos = malloc((unsigned long) n * (unsigned long) n * sizeof(unsigned int));
0c8ce2b0   Pedro Roque   missing files 
262
4d26a735   Pedro Roque   Increased recogni... 
263
 
		for (i = 1; i < n; i++) {
0c8ce2b0   Pedro Roque   missing files 
264
265
 
			for (j = 0; j < i; ++j) {
				new_dist[i * n + j] = new_dist[j * n + i] = v_new_range(0, d_max, false);
4d26a735   Pedro Roque   Increased recogni... 
266
267
 
				n_pos[(unsigned int) i * (unsigned int) n + (unsigned int) j] = n_pos[(unsigned int) j * (unsigned int) n + (unsigned int) i] = v_new_range(1,
						(unsigned int) n * (unsigned int) n, false);
0c8ce2b0   Pedro Roque   missing files 
268
269
270
271
272
 
			}
		}

		unsigned int val = 0;
		unsigned int v_id = v_new_val(val);
4d26a735   Pedro Roque   Increased recogni... 
273
 
		for (i = 0; i < n; i++) {
0c8ce2b0   Pedro Roque   missing files 
274
275
276
277
278
 
			new_dist[i * n + i] = v_id;
			n_pos[i * n + i] = v_id;
		}

		vs[2] = v_new_val(1);	// element_var works with Y indexs from 1 to ... Because of Flatzinc specification
4d26a735   Pedro Roque   Increased recogni... 
279
 
		for (i = 1; i < n; i++) {
0c8ce2b0   Pedro Roque   missing files 
280
281
282
283
284
 
			vs[0] = pos[i];

			for (j = 0; j < i; ++j) {
				vs[1] = pos[j];
4d26a735   Pedro Roque   Increased recogni... 
285
286
287
 
				c_int_lin_var(cs, vs, 3, n_pos[i * n + j]);
				c_array_var_int_element(dist, (unsigned int) n * (unsigned int) n, n_pos[(unsigned int) i * (unsigned int) n + (unsigned int) j],
						new_dist[(unsigned int) i * (unsigned int) n + (unsigned int) j]);
0c8ce2b0   Pedro Roque   missing files 
288
289
 
			}
		}
4d26a735   Pedro Roque   Increased recogni... 
290
 
		c_int_lin_var(p_flow, new_dist, (unsigned int) n * (unsigned int) n, cost);
0c8ce2b0   Pedro Roque   missing files 
291
292
293
294
295
296
 
	}

	// for optimization
	c_minimize(cost);

	if (OPTIMIZING) {
4d26a735   Pedro Roque   Increased recogni... 
297
 
		printf("\nOptimizing %s Quadratic Assignment Problem with %d values.\n", csp_inst_name, n);
0c8ce2b0   Pedro Roque   missing files 
298
299
300
301
302
303
304
305
306
307
308
 
	} else if (FINDING_ONE_SOLUTION) {
		printf("\nFinding one solution for %s Quadratic Assignment Problem with %d values.\n", csp_inst_name, n);
	} else {
		printf("\nCounting all the solutions for %s Quadratic Assignment Problem with %d values.\n", csp_inst_name, n);
	}

	// Solve the CSP
	result = solve_CSP();

	if (OPTIMIZING && result == 1) {
		printf("Best solution:\n");
4d26a735   Pedro Roque   Increased recogni... 
309
 
		vs_print_single_val(pos, (unsigned int) n, 1);
0c8ce2b0   Pedro Roque   missing files 
310
311
312
313
314
 
		printf("\n");
		v_print_cost(0);

	} else if (FINDING_ONE_SOLUTION && result == 1) {
		printf("Solution:\n");
4d26a735   Pedro Roque   Increased recogni... 
315
 
		vs_print_single_val(pos, (unsigned int) n, 1);
0c8ce2b0   Pedro Roque   missing files 
316
317
318
319
320
321
322
323
324
325
326
 
		printf("\n");

	} else {
		printf("%lu solution(s) found\n", result);
	}

	free(pos);
	free(dist);
	free(n_pos);
	free(new_dist);
}