Not getting the whole loop to finish

kbklpl21 (72)
First of all, I'm not sure if this is supposed to be posted in the beginner forum because as a beginner myself I do not fully understand the whole coding as most of the coding were given by my lecturer and only some were typed by me.

I've been getting an error return value 3221225477 and when I debug I get segmentation fault at the line where I call the first_2_opt_symmetric function (the one in the for loop, not the one outside the for loop), I've read online about the return value stating that I'm trying to access memories I shouldn't access. I don't understand where in the coding I'm trying to do that, so I would really appreciate it if someone can point out the mistakes I'm doing in this coding.

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
 
#include <iostream>
#include <string>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cassert>
#include <ctime>

using namespace std;

long int **read_matrix(ifstream &input, long int n);
double ran01(long int *idum);
long int *generate_random_vector(long int n);
unsigned long int compute_evaluation_function(long int **, long int **, long int *, long int n);
void first_2_opt_symmetric ( long int *, long int, long int **, long int **);
void swap(long int pos_1, long int pos_2, long int *);
void perturbation(long int *p, long int pert_size, long int **, long int **);
long int *p;
long int **d;
long int **f;
long int n;
long int i;
long int j;

#define IA 16807
#define IM 2147483647
#define AM (1.0/IM)
#define IQ 127773
#define IR 2836

int main()
{
	string name;
	long int optimum;
	ifstream infile;
	long int current_best_eval;
	long int *best_p;
	long int new_eval;
	long int current_eval; 
	long int actual_solution_value;
	current_best_eval = INT_MAX;
	long int k;

	infile.open("nug12.dat");
	cout << "Name: ";
	infile >> name;
	cout << name << "\n";

	cout << "Rows and Columns: ";
	infile >> n;
	cout << n << "\n";

	cout << "Optimum solution: ";
	infile >> optimum;
	cout << optimum<<"\n";

	long int **d=read_matrix(infile, n);
	cout << endl;
	cout << endl;
	long int **f=read_matrix(infile, n);
	cout << endl;

	p=generate_random_vector(n);
	cout << "Objective function value= ";
	compute_evaluation_function(d, f, p, n);//initial solution
	cout <<"\n";
	first_2_opt_symmetric (p, n, d, f);//permutation
	cout <<"\n";
	compute_evaluation_function(d, f, p, n);
	cout <<"\n";
		
	for (i = 0; i < 100; i++) //ILS loop
	{
		cout << "iteration = " << i << " ";
		perturbation(p, 3, d, f); 
		cout << endl;
		first_2_opt_symmetric (p, n, d, f);
		cout << endl;
		new_eval = compute_evaluation_function(d, f, p, n);
		cout << endl << "new eval = " << new_eval << endl;
		cout <<"\n";
		
		if (new_eval < current_best_eval)
		{
			current_best_eval = new_eval;
			*best_p=*p;
		}
	}
	cout << "current best eval = " << current_best_eval << endl;

	return 0;
}

long int **read_matrix(ifstream &input, long int n)
{

	long int **matrix = new long int *[n];
	for (i = 0; i < n; i++)
	{
		matrix[i] = new long int[n];
    	for (j = 0; j < n; j++)
		{
			if( !(input >> matrix[i][j]) )
			{
				cerr << "Error reading at " << i << j << endl;
			exit(1);
			}
    	}
	}
    return matrix;
}

double ran01(long int *idum)
{

	long k;
	double ans;

	k =(*idum)/IQ;
	*idum = IA * (*idum - k * IQ) - IR * k;
	if (*idum < 0 )
	{
		*idum += IM;
	}
    ans = AM * (*idum);
	return ans;
}

long int *generate_random_vector(long int n)
{
   
	long int  i, j, help;
	long int  *v;
	srand(time(0));
	long int seed=rand();

	v = new long int( n * sizeof(long int) );

	for ( i = 0 ; i < n; i++ )
	{
		v[i] = i;
	}

	for ( i = 0 ; i < n-1 ; i++)
	{
    	j = (long int) ( ran01( &seed ) * (n - i));
    	assert( i + j < n );
    	help = v[i];
    	v[i] = v[i+j];
    	v[i+j] = help;
  	}
  	return v;
}

unsigned long int compute_evaluation_function(long int **d, long int **f, long int *p, long int n)
{

	unsigned long obj_f_value;

	obj_f_value = 0;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			obj_f_value += d[i][j] * f[p[i]][p[j]];
    	}
  	}
  	cout << obj_f_value;
	return obj_f_value;
}

void first_2_opt_symmetric (long int *q, long int n, long int **d, long int **f)
{
	long int improvement = 1;
	long int improve_item = 0;
	register long int u, v, k;
	register long int tmp;
	long int *x;  
 
	improvement = 1;
	x = generate_random_vector(n);
	while (improvement)
	{
		improvement = 0;
    	for ( i = 0 ; i < n ; i++ )
		{
      		u = x[i];
      		improve_item = 0;
      		for ( j = 0 ; j < n ; j++ )
			{
        		v = x[j];
        		if (u == v)
          			continue;
        			tmp = 0;
        		for ( k = 0 ; k < n ; k++ )
				{
					if ( (k != u) && (k != v) )
					{
            			tmp += (d[u][k] - d[v][k]) * (f[q[v]][q[k]] - f[q[u]][q[k]]);
          			}    
        		}
        		if (tmp < 0)
				{
          			//cout <<"improve"<<"\n";
					improvement = 1;
          			improve_item = 1;    
          			swap (u, v, q);
        		}
      		}
		}
	}
	delete (x);
}

void swap(long int pos_1, long int pos_2, long int *p)
{
	long int tmp;

	tmp = p[pos_1];
	p[pos_1] = p[pos_2];
  	p[pos_2] = tmp;
}

void perturbation(long int *p, long int pert_size, long int **d, long int **f)
{
	long int hold_value[n];			//allocate memory for items to be chosen in move/*
	int chosen[pert_size];			//*allocate temporary memory to determine items to be moved */*

    
	for(i = 0; i < n; i++)
	{
    	hold_value[i] = p[i];				//initialize hold_value with the same value from local search/*
	} 
  	int j = n - 1;
	int rand_number;
  	int rand_no;
  
  	for(i = 1; i <= pert_size; i++)
	{
	rand_number = rand();
    	rand_no = rand_number % j;				//choose random number from 1 to size - 1/
    	chosen[i - 1] = rand_no + i;			//copy the value to chosen[i]
        }
  	long int temp;
  	for(i = 0; i < pert_size; i++)
	{
    	temp = chosen[i];
		swap(i, temp, hold_value);		     //swap chosen[i] and hold_value[i]; n first item in hold_value[i] is the index array that will be included in perturbation/
  	} 
	long int temp1;
	long int temp2;
	temp1 = p[hold_value[1]];//
	temp2 = p[hold_value[0]];
	for(i = 0; i < pert_size - 1; i++)
	{
    	p[hold_value[i + 1]] = temp2;
    	temp2 = temp1;
    	temp1 = p[hold_value[i + 2]]; 
  	}
  	p[hold_value[0]] = temp2;
	cout <<endl;
}


Also, this is the file I'm reading from:

Nug12
12
578
0 1 2 3 1 2 3 4 2 3 4 5
1 0 1 2 2 1 2 3 3 2 3 4
2 1 0 1 3 2 1 2 4 3 2 3
3 2 1 0 4 3 2 1 5 4 3 2
1 2 3 4 0 1 2 3 1 2 3 4
2 1 2 3 1 0 1 2 2 1 2 3
3 2 1 2 2 1 0 1 3 2 1 2
4 3 2 1 3 2 1 0 4 3 2 1
2 3 4 5 1 2 3 4 0 1 2 3
3 2 3 4 2 1 2 3 1 0 1 2
4 3 2 3 3 2 1 2 2 1 0 1
5 4 3 2 4 3 2 1 3 2 1 0

0 5 2 4 1 0 0 6 2 1 1 1
5 0 3 0 2 2 2 0 4 5 0 0
2 3 0 0 0 0 0 5 5 2 2 2
4 0 0 0 5 2 2 10 0 0 5 5
1 2 0 5 0 10 0 0 0 5 1 1
0 2 0 2 10 0 5 1 1 5 4 0
0 2 0 2 0 5 0 10 5 2 3 3
6 0 5 10 0 1 10 0 0 0 5 0
2 4 5 0 0 1 5 0 0 0 10 10
1 5 2 0 5 5 2 0 0 0 5 0
1 0 2 5 1 4 3 5 10 5 0 2
1 0 2 5 1 0 3 0 10 0 2 0
Last edited on
Enoizat (1343)
Sorry, cannot reproduce your issue. This is my output:
Name: Nug12
Rows and Columns: 12
Optimum solution: 578



Objective function value= 728


Anyway, I get a large number of warnings (I’d say too many for a program provided by a lecturer):

main.cpp: In function 'int main()':
main.cpp:58:16: warning: declaration of 'd' shadows a global declaration [-Wshadow]
   58 |     long int **d=read_matrix(infile, n);
      |                ^
main.cpp:20:12: note: shadowed declaration is here
   20 | long int **d;
      |            ^
main.cpp:61:16: warning: declaration of 'f' shadows a global declaration [-Wshadow]
   61 |     long int **f=read_matrix(infile, n);
      |                ^
main.cpp:21:12: note: shadowed declaration is here
   21 | long int **f;
      |            ^
main.cpp:40:14: warning: unused variable 'current_eval' [-Wunused-variable]
   40 |     long int current_eval;
      |              ^~~~~~~~~~~~
main.cpp:41:14: warning: unused variable 'actual_solution_value' [-Wunused-variable]
   41 |     long int actual_solution_value;
      |              ^~~~~~~~~~~~~~~~~~~~~
main.cpp:43:14: warning: unused variable 'k' [-Wunused-variable]
   43 |     long int k;
      |              ^
main.cpp: In function 'long int** read_matrix(std::ifstream&, long int)':
main.cpp:95:51: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   95 | long int **read_matrix(ifstream &input, long int n)
      |                                                   ^
main.cpp:22:10: note: shadowed declaration is here
   22 | long int n;
      |          ^
main.cpp: In function 'long int* generate_random_vector(long int)':

(…a lot of warnings about shadowing…)

main.cpp:177:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  177 |     register long int u, v, k;
      |                       ^
main.cpp:177:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  177 |     register long int u, v, k;
      |                          ^
main.cpp:177:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  177 |     register long int u, v, k;
      |                             ^
main.cpp:178:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
  178 |     register long int tmp;
      |                       ^~~
main.cpp:193:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  193 |                 if (u == v)
      |                 ^~
main.cpp:195:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  195 |                     tmp = 0;
      |                     ^~~
main.cpp:176:14: warning: variable 'improve_item' set but not used [-Wunused-but-set-variable]
  176 |     long int improve_item = 0;
      |              ^~~~~~~~~~~~
main.cpp: In function 'void swap(long int, long int, long int*)':
main.cpp:216:54: warning: declaration of 'p' shadows a global declaration [-Wshadow]
  216 | void swap(long int pos_1, long int pos_2, long int *p)
      |                                                      ^
main.cpp:19:11: note: shadowed declaration is here
   19 | long int *p;
      |           ^
main.cpp: In function 'void perturbation(long int*, long int, long int**, long int**)':
main.cpp:225:78: warning: declaration of 'f' shadows a global declaration [-Wshadow]
  225 | void perturbation(long int *p, long int pert_size, long int **d, long int **f)
      |                                                                              ^
main.cpp:21:12: note: shadowed declaration is here
   21 | long int **f;
      |            ^
main.cpp:225:78: warning: declaration of 'd' shadows a global declaration [-Wshadow]
  225 | void perturbation(long int *p, long int pert_size, long int **d, long int **f)
      |                                                                              ^
main.cpp:20:12: note: shadowed declaration is here
   20 | long int **d;
      |            ^
main.cpp:225:78: warning: declaration of 'p' shadows a global declaration [-Wshadow]
  225 | void perturbation(long int *p, long int pert_size, long int **d, long int **f)
      |                                                                              ^
main.cpp:19:11: note: shadowed declaration is here
   19 | long int *p;
      |           ^
main.cpp:227:14: warning: ISO C++ forbids variable length array 'hold_value' [-Wvla]
  227 |     long int hold_value[n];   //allocate memory for items to be chosen in move/*
      |              ^~~~~~~~~~
main.cpp:228:9: warning: ISO C++ forbids variable length array 'chosen' [-Wvla]
  228 |     int chosen[pert_size];   //*allocate temporary memory to determine items to be moved */*
      |         ^~~~~~
main.cpp:235:9: warning: declaration of 'j' shadows a global declaration [-Wshadow]
  235 |     int j = n - 1;
      |         ^
main.cpp:24:10: note: shadowed declaration is here
   24 | long int j;
      |          ^
main.cpp:225:63: warning: unused parameter 'd' [-Wunused-parameter]
  225 | void perturbation(long int *p, long int pert_size, long int **d, long int **f)
      |                                                    ~~~~~~~~~~~^
main.cpp:225:77: warning: unused parameter 'f' [-Wunused-parameter]
  225 | void perturbation(long int *p, long int pert_size, long int **d, long int **f)
      |                                                                  ~~~~~~~~~~~^
main.cpp: In function 'int main()':
main.cpp:87:20: warning: 'best_p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |             *best_p=*p;
      |             ~~~~~~~^~~


Is your code about this?
https://en.wikipedia.org/wiki/Iterated_local_search

I must admit I can’t guess the involved math, but there’s at least an indentation issue in the function you mention:
1
2
3
 
if (u == v)
    continue;
    tmp = 0;

if u != v, tmp is set to zero – but that can’t be the problem.

The fact is this is mostly a C code with some C++ feature (the new and delete operators), and all those global variables make it hard to follow what happens in the code.
For example, “p” is a global variable, but it is passed in the function call as a parameter
first_2_opt_symmetric (p, size, matrix_1, matrix_2);
and later used with the name “q”…
salem c (3715)
> v = new long int( n * sizeof(long int) );
This looks for all the world like someone tried to turn v = malloc( n * sizeof(long int) ); into C++.
Especially considered with delete (x); as formerly being free(x);

Unfortunately, now, v is only one element in size, not n.

It should be
v = new long int[ n ];
and
delete [] x;

+ diplomacy points to Enoizat.

As tutor written "C++" code, it's a train wreck.
kbklpl21 (72)
Yes Enoizat, the code is about iterated local search, can I know how did you get the warnings like that? Being able to get those would definitely make it easier to correct unnecessary mistakes! Also I apologise that you are not able to reproduce the issue, but it keeps happening to me whenever I run the code hmm...
By the way Enoizat, is the tmp=0 part included in the 'if'? Since there's no braces that include it with the 'if'. And yes too to the code being C, my lecturer gave me the C codes and I'm supposed to use C++. For the last part, I know many of the global variables are passed in several function calls as a parameter, but I also don't know why I couldn't get the value stored in the global variables without doing that, so I had to pass them as parameters in order to get the value stored.
kbklpl21 (72)
Salem C, I didn't understand that line of code from my lecturer so I didn't change anything except for the malloc to new, this is due to not having any basics and classes in C, and when I searched online, the examples given were only changing malloc to new, without any examples having the * sizeof(long int) part. Thanks for the error you pointed out!
Enoizat (1343)
how did you get the warnings like that?

The answer varies according to your compiler. I use (a windows porting of) GCC, and to raise the warning level near the maximum, assuming the file to be compiled is "main.cpp", I add the following flags:

g++ -std=c++2a -Werror -Wall -Wextra -Wpedantic -Wshadow main.cpp -o main.exe

For Visual Studio, I’m afraid you need to read the manual.


I apologise that you are not able to reproduce the issue

No need to apologize, you did nothing wrong.
Sometimes different compilers produce different executables. Sometimes debug versions stop working when compiled in release mode.


is the tmp=0 part included in the 'if'?

No, you’re right, it isn’t. But it might look as if it were.
That’s why I warned you “tmp = 0” will be executed when u != v (while, when u == v, ‘continue’ would restart the loop). But it seems you already knew it :)


why I couldn't get the value stored in the global variables without doing that

A global variable should be visible in any scope where is not shadowed by a local variable (and not outside the file if it’s static).
I’m not aware of any exception of this rule. You could try to cut down on duplicated names and see if it is true.
I know it’s very hard not to duplicate one character length names :-) and perhaps that’s why many programmers say it’s better to give global variable long names. Let’s say, the wider the scope, the longer the name – but that’s just a general advice, absolutely not a rule.


It seems salem c spot the biggest problem, so far.

If you are allowed to use C++ feature, you could try to use std::vectors instead of C-style arrays. std::vectors might throw exceptions when you go out of boundaries by means of the at() method.
I don’t think I can really help you, mainly because I’m not good at math.
If you want, I could try to rewrite your code to make it look more ‘C++ style’, but let me repeat it works for me.

Good luck and happy coding!
salem c (3715)
First valgrind run.
$ g++ -g foo.cpp
$ valgrind ./a.out 
==3756== Memcheck, a memory error detector
==3756== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==3756== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==3756== Command: ./a.out
==3756== 
Name: Nug12
Rows and Columns: 12
Optimum solution: 578



Objective function value= 792

640
==3756== Use of uninitialised value of size 8
==3756==    at 0x401D19: swap(long, long, long*) (foo.cpp:222)
==3756==    by 0x401F5F: perturbation(long*, long, long**, long**) (foo.cpp:249)
==3756==    by 0x4013CF: main (foo.cpp:77)
==3756== 
==3756== Use of uninitialised value of size 8
==3756==    at 0x401D36: swap(long, long, long*) (foo.cpp:223)
==3756==    by 0x401F5F: perturbation(long*, long, long**, long**) (foo.cpp:249)
==3756==    by 0x4013CF: main (foo.cpp:77)
==3756== 
==3756== Invalid read of size 8
==3756==    at 0x401D19: swap(long, long, long*) (foo.cpp:222)
==3756==    by 0x401F5F: perturbation(long*, long, long**, long**) (foo.cpp:249)
==3756==    by 0x4013CF: main (foo.cpp:77)
==3756==  Address 0x10268b1fe8 is not stack'd, malloc'd or (recently) free'd
==3756== 
==3756== 
==3756== Process terminating with default action of signal 11 (SIGSEGV)


First gdb run
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) target remote | /usr/lib/valgrind/../../bin/vgdb --pid=4112
Remote debugging using | /usr/lib/valgrind/../../bin/vgdb --pid=4112
relaying data between gdb and process 4112
warning: remote target does not support file transfer, attempting to access files from local filesystem.
Reading symbols from /lib64/ld-linux-x86-64.so.2...Reading symbols from /usr/lib/debug//lib/x86_64-linux-gnu/ld-2.23.so...done.
done.
0x0000000004000c30 in _start () from /lib64/ld-linux-x86-64.so.2
(gdb) c
Continuing.

Program received signal SIGSEGV, Segmentation fault.
0x0000000000401d19 in swap (pos_1=2, pos_2=82928825, p=0xffefffa20) at foo.cpp:222
222		p[pos_1] = p[pos_2];
(gdb) bt
#0  0x0000000000401d19 in swap (pos_1=2, pos_2=82928825, p=0xffefffa20) at foo.cpp:222
#1  0x0000000000401f60 in perturbation (p=0x5aba3b0, pert_size=3, d=0x5ab9370, f=0x5ab9b90) at foo.cpp:249
#2  0x00000000004013d0 in main () at foo.cpp:77
(gdb) up
#1  0x0000000000401f60 in perturbation (p=0x5aba3b0, pert_size=3, d=0x5ab9370, f=0x5ab9b90) at foo.cpp:249
249			swap(i, temp, hold_value);
(gdb) p i
$1 = 2
(gdb) p temp
$2 = 82928825
(gdb) p n
$3 = 12
(gdb) p chosen
$4 = {9, 0, 82928825}

Yeah, element 82928825 is so not inside any of your arrays.

Examining the code further - oh yeah, indentation always wins!
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
 
void perturbation(long int *p, long int pert_size, long int **d, long int **f)
{
  long int hold_value[n];       //allocate memory for items to be chosen in move/*
  int chosen[pert_size];        //*allocate temporary memory to determine items to be moved */*


  for (i = 0; i < n; i++) {
    hold_value[i] = p[i];       //initialize hold_value with the same value from local search/*
  }
  int j = n - 1;
  int rand_number;
  int rand_no;

  for (i = 1; i <= pert_size; i++) {
    rand_number = rand();
    rand_no = rand_number % j;  //choose random number from 1 to size - 1/
    chosen[i - 1] = rand_no + i;  //copy the value to chosen[i]
    long int temp;
    for (i = 0; i < pert_size; i++) {
      temp = chosen[i];
      swap(i, temp, hold_value);
      // swap chosen[i] and hold_value[i]; n first item in hold_value[i] 
      // is the index array that will be included in perturbation/
    }
    long int temp1;
    long int temp2;
    temp1 = p[hold_value[1]];   //
    temp2 = p[hold_value[0]];
    for (i = 0; i < pert_size - 1; i++) {
      p[hold_value[i + 1]] = temp2;
      temp2 = temp1;
      temp1 = p[hold_value[i + 2]];
    }
    p[hold_value[0]] = temp2;
    cout << endl;
  }
}

Look at the loops at lines 14 and 19.
The outer loop only sets the first element of chosen, but the inner loop then tries to use all of chosen.

Also, you're using the SAME variable for both loops - this will end badly for you.
Enoizat (1343)
Other potential issues could be there in rows 166
 
 
obj_f_value += d[i][j] * f[p[i]][p[j]];

and 200:
 
 
tmp += (d[u][k] - d[v][k]) * (f[q[v]][q[k]] - f[q[u]][q[k]]);

In both cases, f is a pointer to pointer to long and p/q are pointers to long.
The problem is the size of ‘p’ (later called ‘q’) seems the square radix of ‘f’:
‘f’:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
long int **f=read_matrix(infile, n);
// ...
long int **read_matrix(ifstream &input, long int n)
{
    long int **matrix = new long int *[n];
    for (i = 0; i < n; i++)
    {
        matrix[i] = new long int[n];
        for (j = 0; j < n; j++)
        {
            if( !(input >> matrix[i][j]) )
            {
                cerr << "Error reading at " << i << j << endl;
                exit(1);
            }
        }
    }
    return matrix;
}

where ‘n’ is the size read from the file (12) – so ‘f’ is n * n. While ‘p’:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
p=generate_random_vector(n);
// ...
long int *generate_random_vector(long int n)
{
    long int  i, j, help;
    long int  *v;
    srand(time(0));
    long int seed=rand();

    v = new long int( n * sizeof(long int) );
    // . . .
    return v;
}

Apart from the syntax error pointed out by salem c, maybe you want ‘p’ to be n * n too.

- - -
 
 
obj_f_value += d[i][j] * f[p[i]][p[j]];

Again, I’m not good at math, but are sure you want to access an element getting its index from the random values stored in ‘p’? I simply can’t get the logic.
By the way, I’m not sure this check (line 148):
assert( i + j < n );
it’s enough to guarantee you aren’t going beyond boundaries, since “[ p[i] ][ p[j] ]” it’s more a multiplication than an addiction. I might be wrong, of course.
dhayden (5799)
kbklpl21, please post the C code that your prof gave you. That will help us help you to translate it to C++.
Enoizat (1343)
My first attempt of making the code more readable.
It crashes badly, but it could be me who have misinterpreted something.

I hope it could encourage someone else to give better help!

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
 
#include <algorithm>
#include <chrono>
#include <exception>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <numeric>
#include <random>
#include <string>
#include <vector>


using m2d = std::vector< std::vector<long> >;


std::ostream& operator<< (std::ostream& os, const m2d& rhs)
{
    for (std::size_t i {}; i < rhs.size(); ++i) {
        for (std::size_t j {}; j < rhs.size(); ++j) {
            os << std::setw(4) << rhs.at(i).at(j);
        }
        os << '\n';
    }
    return os;
}


struct MyTwoMatrices {
    m2d one;
    m2d two;
    int size {};        // two square matrices of the same size
    MyTwoMatrices() = default;

//friend
    friend std::ostream& operator<< (std::ostream&, const MyTwoMatrices&);
};


std::ostream& operator<< (std::ostream& os, const MyTwoMatrices& rhs)
{
    os << rhs.one << '\n';
    os << rhs.two << '\n';
    return os;
}


MyTwoMatrices readDataFromFile( const std::string&, long& );
m2d readMatrix( std::ifstream&, int );
std::vector<long> generateRandomVector( int );
std::mt19937& rndEngine();
unsigned long int computeEvaluation( const MyTwoMatrices&,
                                     const std::vector<long>& );
void first2OptSymmetric ( std::vector<long>&,
                          const MyTwoMatrices& );
void mySwap(long, long, std::vector<long>&);
void perturbation( std::vector<long>&,
                   long,
                   const MyTwoMatrices& );
template <typename T> T getRndInt( T = std::numeric_limits<T>::min(),
                                   T = std::numeric_limits<T>::max() );


int main()
{
    long opt_sol {};
    auto matrs { readDataFromFile( "nug12.dat", opt_sol ) };
    std::cout << "Matrices are:\n" << matrs << '\n';
    auto rnd_v { generateRandomVector( matrs.size ) };

    std::cout << "Objective function value = "
              << computeEvaluation( matrs, rnd_v )  // initial solution
              << '\n';

    first2OptSymmetric( rnd_v, matrs );             // permutation
    std::cout  << computeEvaluation( matrs, rnd_v ) << '\n';

    unsigned long current_best_eval { std::numeric_limits<unsigned int>::max() };
    for (int i {}; i < 100; ++i) //ILS loop
    {
        std::cout << "iteration = " << i << ' ';
        perturbation(rnd_v, 3, matrs);
        std::cout << '\n';
        first2OptSymmetric( rnd_v, matrs );
        std::cout << '\n';
        unsigned long new_eval { computeEvaluation( matrs, rnd_v ) };
        std::cout << "\nnew eval = " << new_eval << "\n\n";

        if (new_eval < current_best_eval) {
            current_best_eval = new_eval;
            std::vector<long> best { rnd_v };
        }
    }
    std::cout << "current best eval = " << current_best_eval << '\n';
    return 0;
}


MyTwoMatrices readDataFromFile( const std::string& fname, long& opt_sol )
{
    std::ifstream infile(fname);
    if (!infile) {
        std::cout << "Cannot open '" << fname << "'.\n";
        return MyTwoMatrices();
    }
    std::string name;
    infile >> name;
    std::cout << "Name: " << name << '\n';

    MyTwoMatrices both;
    infile >> both.size;
    std::cout << "Rows and Columns: " << both.size << '\n';

    infile >> opt_sol;
    std::cout << "Optimum solution: " << opt_sol << '\n';

    both.one = readMatrix(infile, both.size);
//    infile >> name;     // discard empty line
    both.two = readMatrix(infile, both.size);
    return both;
}


// Might throw!
m2d readMatrix( std::ifstream& fin, int size )
{
    m2d matrix( size, std::vector<long>( size ) );

    for (int i {}; i < size; ++i) {
        for (int j {}; j < size; ++j) {
            if (! (fin >> matrix.at(i).at(j))) {
                std::cerr << "Error reading at [" << i << "][" << j << "]\n"
                          << "Read data so far:\n " << matrix << '\n';
                throw std::invalid_argument("Cannot read data from file.");
            }
        }
    }

    return matrix;
}


std::vector<long> generateRandomVector( int size )
{
    std::vector<long> v( size );            // size * size?
    std::iota( v.begin(), v.end(), 1 );     // begin by 1?
    std::shuffle( v.begin(), v.end(), rndEngine() );

    return v;
}


std::mt19937& rndEngine()
{
    static std::mt19937 eng {
        static_cast<unsigned>(
            std::chrono::high_resolution_clock::now().time_since_epoch().count()
        )
    };
    return eng;
}


unsigned long int computeEvaluation( const MyTwoMatrices& both,
                                     const std::vector<long>& v )
{
    unsigned long obj_f_value {};
    for (int i {}; i < both.size; ++i) {
        for (int j {}; j < both.size; ++j) {
            // I'm not sure if the following matches your original code.
            // Please correct it:
            obj_f_value +=   both.one.at(i).at(j)
                           * both.two.at( v.at(i) ).at( v.at(j) );
        }
    }
    return obj_f_value;
}


void first2OptSymmetric ( std::vector<long>& rnd_vec,
                          const MyTwoMatrices& both )
{
    std::vector<long> tmp_rnd_vec { generateRandomVector( both.size ) };
    long int improvement { 1 };
    while (improvement) {
        improvement = 0;
        for (int i {} ; i < both.size ; ++i) {
            long u { tmp_rnd_vec.at(i) };
            // long improve_item {}; not used!!

            for (int j {} ; j < both.size ; ++j) {
                long v { tmp_rnd_vec.at(j) };
                if (u == v) {
                    continue;
                }

                // u != v
                long tmp {};
                for (int k {} ; k < both.size ; ++k) {
                    if (    (k != static_cast<int>(u))
                         && (k != static_cast<int>(v)) )
                    {
                        tmp +=   (   both.one.at(u).at(k)
                                   - both.one.at(v).at(k) )
                               * (   both.two.at( rnd_vec.at(v) ).at( rnd_vec.at(k) )
                                   - both.two.at( rnd_vec.at(u) ).at( rnd_vec.at(k) ) );
                    }
                }

                if (tmp < 0) {
                    //std::cout << "improve" << '\n';
                    improvement = 1;
                    // improve_item = 1; not used!!
                    mySwap (u, v, rnd_vec);
                }
            }
        }
    }
}


void mySwap(long pos_1, long pos_2, std::vector<long>& v)
{
    long int tmp { v.at(pos_1) };
    v.at(pos_1) = v.at(pos_2);
    v.at(pos_2) = tmp;
}


void perturbation( std::vector<long>& rnd_vec,
                   long pert_size,
                   const MyTwoMatrices& both )
{
    auto hold_value { rnd_vec };                // items to be chosen in move
    std::vector<int> chosen( pert_size );       // items to be moved

    for (int i { 1 }; i <= pert_size; ++i) {
        int rand_number { getRndInt<int>( 1, both.size - 1) };
        chosen.at(i - 1) = rand_number + i;     // copy the value to chosen[i]
        for(int j {}; j < pert_size; ++j) {
            long temp { chosen.at(j) };
            mySwap(j, temp, hold_value);        // swap chosen[i] and hold_value[i];
                                                // first item in hold_value[i] is
                                                // the index array that will be
                                                // included in perturbation
        }
        long int temp1 { rnd_vec.at( hold_value.at(1) ) };
        long int temp2 { rnd_vec.at( hold_value.at(0) ) };
        for(int j {}; j < pert_size - 1; ++j) {
            rnd_vec.at( hold_value.at(i + 1) ) = temp2;
            temp2 = temp1;
            temp1 = rnd_vec.at( hold_value.at(i + 2) );
        }
        rnd_vec.at( hold_value.at(0) ) = temp2;
    }
}


template <typename T> T getRndInt( T min, T max )
{
    std::uniform_int_distribution<T> dst( min, max );
    return dst( rndEngine() );
}

kbklpl21 (72)
please post the C code that your prof gave you.

You're right Dhayden, these were the codes sent by my lecturer. They were sent function by function, not as a complete coding but I arranged them in the order of the codes posted above.

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
 
int **read_matrix(FILE *input, long int size){

    /*    
    FUNCTION:       read instance matrices
    INPUT:          instance file name, instance size
    OUTPUT:         d-matrix and f-matrix
    (SIDE)EFFECTS:  none
    COMMENTS:       read the distance matrix and flow matrix
    */

  
  long int i, j;
  long int **matrix;

  

  for (i = 0; i < size; i++){
    matrix[i] = (long int *)(matrix + size) + i*size;
    for (j = 0; j < size; j++){
      if(fscanf(input, "%ld", &matrix[i][j]) < 0){
	fprintf(stderr, "error reading (%ld, %ld) in file", i, j);
	exit(1);
      }
//       printf("%ld ", matrix[i][j]);
    }
  }
  return matrix;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
double ran01(long int *idum){

    /* 
    FUNCTION:      returns a pseudo-random number
    INPUT:         a pointer to the seed variable 
    OUTPUT:        a pseudo-random number uniformly distributed in [0,1]
    (SIDE)EFFECTS: changes the value of seed
    */

  
  long k;
  double ans;

  
  k =(*idum)/IQ;
  *idum = IA * (*idum - k * IQ) - IR * k;
  if (*idum < 0 ) *idum += IM;
    ans = AM * (*idum);
  return ans;
}


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
 
long int * generate_random_vector(long int size){
    
    /*    
    FUNCTION:      generates a random vector
    INPUT:         vector dimension
    OUTPUT:        returns pointer to vector, free memory when vector is not needed anymore 
    (SIDE)EFFECTS: none
    */

  
  long int  i, j, help;
  long int  *v;

  v = malloc( size * sizeof(long int) );

  for ( i = 0 ; i < size; i++ ) 
    v[i] = i;

  for ( i = 0 ; i < size-1 ; i++) {
    j = (long int) ( ran01( &seed ) * (size - i)); 
    assert( i + j < size );
    help = v[i];
    v[i] = v[i+j];
    v[i+j] = help;
  }
  return v;
}


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
 
unsigned long int compute_evaluation_function(long int *p){

    /* 
  FUNCTION:      compute evaluation function
  INPUT:         pointer to solution
  OUTPUT:        evaluation function
  (SIDE)EFFECTS: none
  COMMENTS:      none
    */

  
  long int i, j;
  unsigned long obj_f_value;

  
  obj_f_value = 0;
  for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
      obj_f_value += d[i][j] * f[p[i]][p[j]];
    }
  }
  if(make_symmetric_flag)
    obj_f_value /= 2;
  return obj_f_value;
}


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
 
void first_2_opt_symmetric ( long int *q, long int *dlb ) {
/*    
  FUNCTION:      first improvement 2-opt local search for symmetric instances
  INPUT:         pointer to some initial assignment
  OUTPUT:        none
  (SIDE)EFFECTS: initial assignment is locally optimized, dlb is used to increase the search speed, the dlb value is changed to false if item change it's location during perturbation
  COMMENT:       neighborhood is scanned in random order, use of register for faster computation
*/

  long int   improvement = TRUE;
  long int   improve_item = FALSE; 
  register long int   i, j, u, v, k;
  register long int   tmp, help1, help2, help3;
  long int   *x;  
  
  improvement   = TRUE;
  x = generate_random_vector(n);
  while ( improvement ) {
    improvement = FALSE;
    for ( i = 0 ; i < n ; i++ ) {
      u = x[i];
      if ( dlb_flag && dlb[u] )
        continue;
      improve_item = FALSE;
      for ( j = /i + 1/0 ; j < n ; j++ ) {
        v = x[j];
        if (u == v)
          continue;
        tmp = 0;
        help1 = q[u];
        help2 = q[v];
        for ( k = 0 ; k < n ; k++ ) {
          if ( (k != u) && (k != v) ) {
            help3 = q[k];
            tmp += (d[u][k] - d[v][k]) * (f[help2][help3] - f[help1][help3]);
          }    
        }
        tmp *= symmetric_factor;
        if (tmp < 0) {
          improvement = TRUE;
          improve_item = TRUE;	  
          dlb[u] = FALSE;
          dlb[v] = FALSE;	  
          swap( u, v, q);
          improvement_steps_count++;
        }
      }
      if (!improve_item)
        dlb[u] = TRUE;	
    }
  }
  free ( x );
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
void swap(long int pos_1, long int pos_2, long int *p){

    /*
    FUNCTION:      swap position of two items in a vector
    INPUT:         position 1, position 2, pointer to vector
    OUTPUT:        none
    (SIDE)EFFECTS: none
    COMMENTS:      none
    */
  
  
  long int tmp;

  
  tmp = p[pos_1];
  p[pos_1] = p[pos_2];
  p[pos_2] = tmp;
}


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
 
void perturbation_dlb(long int *p, long int pert_type, long int pert_size, long int pert_change, long int pert_end, long int *dlb){

    /*    
    FUNCTION:         apply random perturbation
    INPUT:            pointer to solution, perturbation scheme, perturbation strength, change in perturbation, end perturbation size
    OUTPUT:           none
    (SIDE)EFFECTS:    new solution formed from old solution
    COMMENTS:         none
    */

  int i;
  long int hold_value[n];			/*allocate memory for items to be chosen in move*/
  int chosen[pert_size];			/*allocate temporary memory to determine items to be moved */
  
  for(i = 0; i < n; i++){
    hold_value[i] = p[i];				/*initialize hold_value with the same value from local search*/
  }
  	
  int j = n - 1;
  int rand_no;
  
/*  printf("pert_size %ld\n", pert_size);*/
  
  for(i = 1; i <= pert_size; i++){
    rand_no = rand() % j;				/*choose random number from 1 to size - 1*/
    chosen[i - 1] = rand_no + i;			//copy the value to chosen[i]
/*    printf("chosen[%d]=%d\n", i-1,rand_no + i);*/
/*    chosen[i - 1] = rand_no;			copy the value to chosen[i]*/
/*    printf("chosen[%d]=%d\n", i-1,rand_no);*/
    j--;
  }	
/*  getchar();*/
  long int temp;

  for(i = 0; i < pert_size; i++){
    temp = chosen[i];
/*    printf("%d--%ld\n", i, temp);*/
    swap(i, temp, hold_value);				/*swap chosen[i] and hold_value[i]; n first item in hold_value[i] is the index array that will be included in perturbation*/
  }
  
  long int temp1;
  long int temp2;

  temp1 = p[hold_value[1]];
  temp2 = p[hold_value[0]];
  for(i = 0; i < pert_size - 1; i++){
    p[hold_value[i + 1]] = temp2;
    if(dlb_flag)
      dlb[hold_value[i + 1]] = FALSE;
    temp2 = temp1;
    temp1 = p[hold_value[i + 2]];
  }
  p[hold_value[0]] = temp2;
  if(dlb_flag)  
    dlb[hold_value[0]] = FALSE;  

/*  printf("locations to be perturbed\t");*/
/*  for(i = 0; i < pert_size; i++){*/
/*    printf("%ld\n", hold_value[i]);*/
/*  }*/
/*  printf("\n");*/
  
  actual_solution_value = compute_evaluation_function(p);
  new_eval = actual_solution_value;
  current_eval = new_eval;
}


kbklpl21 (72)
Hello again Enoizat.
I add the following flags

Sorry but can I know how do you add flags, I'm currently using Dev C++ and the compiler is TDM-GCC.

A global variable should be visible in any scope where is not shadowed by a local variable (and not outside the file if it’s static)

I'll try to correct the shadow problem. :)

If you want, I could try to rewrite your code to make it look more ‘C++ style’

That would be a great help!

obj_f_value += d[i][j] * f[p[i]][p[j]]; tmp += (d[u][k] - d[v][k]) * (f[q[v]][q[k]] - f[q[u]][q[k]]);
These two lines shouldn't be a problem, it's part of the process of the iterated local search, also mathematically it's one digit multiplying another so there shouldn't be any problem.
Last edited on
kbklpl21 (72)
Hello again Salem C.
Sorry the indentations were messed up after I copy the codes and I didn't notice them getting messed up.

The outer loop only sets the first element of chosen, but the inner loop then tries to use all of chosen

Sorry those 2 loops are separate loops, I think I accidentally removed the closing brace when I deleted some comments from the coding. I'll edit the question immediately.

82928825

This must've happened due to the two loops.
kbklpl21 (72)
A friendly reminder to all the helpful people trying to help me with my problem, the code in the question was flawed when I copy and paste the coding, I sincerely apologise for my careless mistake.
kbklpl21 (72)
So after everyone's help, this is my corrected coding, doesn't show any errors and it does run properly (not sure if the output is correct or not though). There are some added calculations but they do not affect the code from the question, just some added calculation. Wouldn't mind if you guys can find anymore mistakes in the coding. It isn't complete (for doing iterated local search), but only a little bit of code need to be added. Also, I think some of it is still C, mind pointing out where?

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
 
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cassert>
#include <ctime>
#include <cmath>

using namespace std;

long int **read_matrix(ifstream &input, long int n);
double ran01(long int *idum);
long int *generate_random_vector(long int n);
unsigned long int compute_evaluation_function(long int n);
void first_2_opt_symmetric (long int n);
void swap(long int pos_1, long int pos_2, long int *);
void perturbation(long int pert_size);
long int *p;
long int **d;
long int **f;
long int n;

#define IA 16807
#define IM 2147483647
#define AM (1.0/IM)
#define IQ 127773
#define IR 2836

int main()
{
	long int optimum;
	ifstream infile;
	long int current_best_eval;
	long int *best_p;
	long int new_eval;
	current_best_eval = INT_MAX;
	long int i;
	long int j;

	infile.open("nug12.dat");
	cout << "Name: ";
	infile >> name;
	cout << name << "\n";

	cout << "Rows and Columns: ";
	infile >> n;
	cout << n << "\n";

	cout << "Optimum solution: ";
	infile >> optimum;
	cout << optimum<<"\n";

	d=read_matrix(infile, n);
	cout << endl;
	cout << endl;
	f=read_matrix(infile, n);
	cout << endl;

	p=generate_random_vector(n);


	compute_evaluation_function(n);
	cout << endl;
	first_2_opt_symmetric (n);
	cout << endl;	
	compute_evaluation_function(n);
	cout << endl << endl;
	
	for (i = 0; i < 100; i++) //ILS loop
	{
		cout << "iteration = " << i+1 << " " << endl;
		cout << " Vector before perturbation = ";
		for (j = 0; j < n; j++)
		{
			cout << p[j] << " ";
		}
		 
		perturbation(3); 
		cout << endl;
		
		cout << " Vector after perturbation = ";
		for (j = 0; j < n; j++)
		{
			cout << p[j] << " ";
		}
		cout << endl;     

		first_2_opt_symmetric (n);
		
		cout << endl;
		
		cout << " Vector after permutation = ";
		for (j = 0; j < n; j++)
		{
			cout << p[j] << " ";
		}
		cout << endl;
		new_eval = compute_evaluation_function(n);
		cout <<"\n";
		
		if (new_eval < current_best_eval)
		{
			current_best_eval = new_eval;
			best_p = p;
			p = best_p;
		}
	}
	cout << endl << "current best eval = " << current_best_eval << endl;

	cout << "ILS best vector = ";
	for (i = 0; i < n; i++)
	{
		cout << p[i] << " ";
	}
	
	
	cout <<endl;
	return 0;
}

long int **read_matrix(ifstream &input, long int n)
{

    /*    
    FUNCTION:       read instance matrices
    INPUT:          instance file name, instance size
    OUTPUT:         d-matrix and f-matrix
    (SIDE)EFFECTS:  none
    COMMENTS:       read the distance matrix and flow matrix
    */

 
	long int i, j;
	long int **matrix = new long int *[n];
	for (i = 0; i < n; i++)
	{
		matrix[i] = new long int[n];
    	for (j = 0; j < n; j++)
		{
			if( !(input >> matrix[i][j]) )
			{
				cerr << "Error reading at " << i << j << endl;
			exit(1);
			}
    	}
	}
    return matrix;
}

double ran01(long int *idum)
{

    /*
    FUNCTION:      returns a pseudo-random number
    INPUT:         a pointer to the seed variable
    OUTPUT:        a pseudo-random number uniformly distributed in [0,1]
    (SIDE)EFFECTS: changes the value of seed
    */

 
	long k;
	double ans;

	k =(*idum)/IQ;
	*idum = IA * (*idum - k * IQ) - IR * k;
	if (*idum < 0 )
	{
		*idum += IM;
	}
    ans = AM * (*idum);
	return ans;
}

long int *generate_random_vector(long int n)
{
   
	/*    
    FUNCTION:      generates a random vector
    INPUT:         vector dimension
    OUTPUT:        returns pointer to vector, free memory when vector is not needed anymore
    (SIDE)EFFECTS: none
    */

 
	long int  i, j, help;
	long int  *v;
	srand(time(0));
	long int seed=rand();

	v = new long int[ n ];

	for ( i = 0 ; i < n; i++ )
	{
		v[i] = i;
	}

	for ( i = 0 ; i < n-1 ; i++)
	{
    	j = (long int) ( ran01( &seed ) * (n - i));
    	assert( i + j < n );
    	help = v[i];
    	v[i] = v[i+j];
    	v[i+j] = help;
  	}
  	return v;
}

unsigned long int compute_evaluation_function(long int n)
{

	/*
	FUNCTION:      compute evaluation function
	INPUT:         pointer to solution
	OUTPUT:        evaluation function
	(SIDE)EFFECTS: none
	COMMENTS:      none
    */

	long int i, j;
	unsigned long obj_f_value;

	obj_f_value = 0;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			obj_f_value += d[i][j] * f[p[i]][p[j]];
    	}
  	}
  	cout << obj_f_value;
	return obj_f_value;
}

void first_2_opt_symmetric (long int n)
{
	/*    
  	FUNCTION:      first improvement 2-opt local search for symmetric instances
  	INPUT:         pointer to some initial assignment
  	OUTPUT:        none
  	(SIDE)EFFECTS: initial assignment is locally optimized, dlb is used to increase the search speed, the dlb value is changed to false if item change it's location during perturbation
  	COMMENT:       neighborhood is scanned in random order, use of register for faster computation
	*/

	long int improvement = 1;
	long int improve_item = 0;
	long int u, v, i, j, k;
	long int tmp;
	long int *x;  
 
	improvement = 1;
	x = generate_random_vector(n);

	while (improvement)
	{
		improvement = 0;
    	for ( i = 0 ; i < n ; i++ )
		{
      		u = x[i];
      		improve_item = 0;
      		for ( j = 0 ; j < n ; j++ )
			{
        		v = x[j];
        		if (u == v)
          			continue;
        		tmp = 0;
        		for ( k = 0 ; k < n ; k++ )
				{
					if ( (k != u) && (k != v) )
					{
            			tmp += (d[u][k] - d[v][k]) * (f[p[v]][p[k]] - f[p[u]][p[k]]);
          			}    
        		}
        		if (tmp < 0)
				{
					improvement = 1;
          			improve_item = 1;    
          			swap (u, v, p);
        		}
      		}
		}
	}
	delete []x;
}

void swap(long int pos_1, long int pos_2, long int *p)
{

    /*
    FUNCTION:      swap position of two items in a vector
    INPUT:         position 1, position 2, pointer to vector
    OUTPUT:        none
    (SIDE)EFFECTS: none
    COMMENTS:      none
    */

	long int tmp;

	tmp = p[pos_1];
	p[pos_1] = p[pos_2];
  	p[pos_2] = tmp;
}

void perturbation(long int pert_size)
{
	/*    
    FUNCTION:         apply random perturbation
    INPUT:            pointer to solution, perturbation scheme, perturbation strength, change in perturbation, end perturbation size
    OUTPUT:           none
    (SIDE)EFFECTS:    new solution formed from old solution
    COMMENTS:         none
    */

	long int hold_value[n];			//allocate memory for items to be chosen in move/*
	int chosen[pert_size];			//*allocate temporary memory to determine items to be moved */*
	long int i;
   
	for(i = 0; i < n; i++)
	{
    	hold_value[i] = p[i];				//initialize hold_value with the same value from local search/*
	}
  	int j = n - 1;
	int rand_number;
  	int rand_no;
   
  	for(i = 1; i <= pert_size; i++)
	{
		rand_number = rand();
    	rand_no = rand_number % j;				//choose random number from 1 to size - 1/
    	chosen[i - 1] = rand_no + i;			//copy the value to chosen[i]
    	j--;
  	}	
  	long int temp;
  	
  	for(i = 0; i < pert_size; i++)
	{
    	temp = chosen[i];
		swap(i, temp, hold_value);				//swap chosen[i] and hold_value[i]; n first item in hold_value[i] is the index array that will be included in perturbation/
  	}

	long int temp1;
	long int temp2;
	temp1 = p[hold_value[1]];//
	temp2 = p[hold_value[0]];

	for(i = 0; i < pert_size - 1; i++)
	{
    	p[hold_value[i + 1]] = temp2;
    	temp2 = temp1;
    	temp1 = p[hold_value[i + 2]];
  	}

  	p[hold_value[0]] = temp2;
	cout <<endl;
}
Last edited on
Topic archived. No new replies allowed.