-
for example, the function rmv_columns if it was sth like this:
Code:
void Solution::rmv_column(int i) {
selected_columns.erase(i)
obj_value = obj_value - (instance->cost)[i];
is_added[i] = false;
for (int j = 0; j < (instance->covers)[i].size(); j++) {
int aRow = (instance->covers)[i][j];
is_covered[aRow] = false;
}
}
the part selected_columns.erase(i) is not correct.Just to show.I want to erase that concret column
and then use it in the code like this:
Code:
for ( int i = 0; i < aSol->selected_columns.size()/2; i++){
aSol-> rmv_column(i);
}
u think it would work??
-
Your idea to use selected_columns.erase(i) seems like a good idea to me. How is it working?
One possible problem is that you are erasing from the selected_columns vector at the same time as you are looping through it. This might make your loop code skip over some objects and not remove half of the columns.
Another possible problem, which I think might be worse, is that random_shuffle is shuffling the columns inside selected_columns, but not inside instance->cost, instance->covers, and your other variables. So after calling random_shuffle the columns inside selected_columns don't match the ones in the other variables. I don't know if this is a problem or not, but it might cause you weird output.
-
Ok. i will explain. You have seen my final code.
Code:
start:
int not_covered;
for (int n=1; n <= num_trials; n++){
while (!aSol -> is_complete()) {
for (int i = 0; i < instance -> n_cols ; i++) {
if(aSol -> is_added[i]){
k[i] = -1;}
else{
not_covered = 0;
for (int j = 0; j < (instance->covers)[i].size(); j++) {
int aRow = (instance->covers)[i][j];
if (!aSol -> is_covered[aRow]) {
// cout<<"not covered "<<endl;
not_covered++;
}
}
k[i] = (double) (not_covered)*1000.0/(double) (instance -> cost[i]);
}
}
aSol -> add_column(GetMax(k,instance->n_cols));
}
//cout << " value " << aSol->value() <<" trial " << num_trials << "\ttime " << timer.elapsed_time(Timer::VIRTUAL) << endl;
}
cout << " value " << aSol->value() << endl;
random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );
aSol -> selected_columns.erase ( aSol -> selected_columns.begin(),aSol -> selected_columns.begin() + aSol -> selected_columns.size()/2 );
cout << " value " << aSol->value() << endl;
if (!aSol-> is_complete())
goto start;
What i want to do, is when find a solution does the shuffle( maybe it is not right), erase the half of the columns and repeat until it finds a new solution. Just to check i put these two cout and i see that gives me the same value( as you said also ).So that erase or shuffle or both DO not do anything.
Any suggestion for these??
First: should i skip totally el shuffle?
The first you said i don't understand really well. How it should be?
Ok..If i also comment shuffle it stils give me the same output.That means for some weird reason no erase columns.The selected_columns is defines into void Solution::add_column()
-
I thought you were using rmv_column? I think the rmv_column idea was a better idea. Did you try that?
-
Yes, but i don't know how to write it.As you see above. I don't know how to express the selected_columns.???? part. if i do for example selected_columns.pop_back() it just gives me smaller values ( subtracting the last column of the set and nothing else ). I think it would work but as i said i don't know how to write it -> when i erase a column from the set (selected_columns ) this to have effect in all my variables. You understand me?
This is why not working erase?? You see anything wrong in the code?? the goto part u think it's good?
i really thought that i had it done.. :-(
-
I thought this code looked good:
Code:
void Solution::rmv_column(int i) {
selected_columns.erase(i);
obj_value = obj_value - (instance->cost)[i];
is_added[i] = false;
for (int j = 0; j < (instance->covers)[i].size(); j++) {
int aRow = (instance->covers)[i][j];
is_covered[aRow] = false;
}
}
You need a semi-colon, but otherwise I don't see why it wouldn't work. Did you try it?
>> the goto part u think it's good?
No, I think goto is not a good idea, but if it works, now is not the time to change it. Leave the goto there and focus on the stuff that is not working.
-
I don't know if that expression >>selected_columns.erase(i); is correct. Because i look at the definition of erase and it is not quite like this.Also when i compile it like this i get an error for this: no matching function for call to 'std::vector<int, std::allocator<int> >::erase(int&)'
I tried instead of that this one:
Code:
selected_columns.erase(selected_columns.begin()+ (i-1),selected_columns.begin()+ i);
to erase the column of the position i. I'm not sure if is the same thing.Erase the column from the position i and erase the column i. i compileit and it is correct. But the problem that i told you before remains.Just calculates values which are decreasing..I don't know if is a problem of the loops..
-
You're right. Use this:
Code:
selected_columns.erase(selected_columns.begin()+ i);
-
I really don't know if it works or not. In the first iteration i get a value that it is close to the optimal solution.In the other steps i get smaller and smaller values until one that is the smallest and after this one are repeated.Is this a solution?? i don't know if it's normal or it is because of the algorithm. Wouldn't it be supposed to get better solutions after each step or not? I'm just asking because i don't know really much about algorithms.With this line that you send me it works, but as i just described you.But looking at the void::rmv_column, erasing that column has effect in all the other variables,no? So, typically is correct. Is it a fault of the code(loops or sth)? I would like to know your opinion
And by the way the final code
Code:
int not_covered;
for (int n=1; n <= num_trials; n++){
while (!aSol -> is_complete()) {
for (int i = 0; i < instance -> n_cols ; i++) {
if(aSol -> is_added[i]){
k[i] = -1;}
else{
not_covered = 0;
for (int j = 0; j < (instance->covers)[i].size(); j++) {
int aRow = (instance->covers)[i][j];
if (!aSol -> is_covered[aRow]) {
// cout<<"not covered "<<endl;
not_covered++;
}
}
k[i] = (double) (not_covered)*1000.0/(double) (instance -> cost[i]);
}
}
aSol -> add_column(GetMax(k,instance->n_cols));
}
cout << " value " << aSol->value() <<" trial " << num_trials << "\ttime " << timer.elapsed_time(Timer::VIRTUAL) << endl;
//random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );
//aSol -> selected_columns.erase ( aSol -> selected_columns.begin(),aSol -> selected_columns.begin() + aSol -> selected_columns.size()/2 );
for ( int i = 0; i< aSol->selected_columns.size()/2; i++){
aSol-> rmv_column(i);
}
}
-
also, if you have time to look it.. the algorithm has as inputs -i ( the instances) -t time and -n the number of trials. i have defined all these as:
Code:
void read_parameters(int argc, char **argv)
{
int iarg=1;
while (iarg < argc) {
if (strcmp(argv[iarg],"-i")==0) {
inputFile = argv[++iarg];
}
if (strcmp(argv[iarg],"-t")==0) {
tmax = atoi(argv[++iarg]);
}
if (strcmp(argv[iarg],"-n")==0) {
num_trials = atoi(argv[++iarg]);
}
iarg++;
}
}
But i dont know how to write, make a loop maybe so that in every trial it gives me the value, #of this trial and the time to compute this value. Because if i write to run for example:
./ig.exe -i instances/scp51.txt -t ( this must me the maximum time i want to put for the iteration) -n 5 it gives me sth like this:
Code:
value 289 trial 5 time 0.157
value 256 trial 5 time 0.157
value 239 trial 5 time 0.157
value 228 trial 5 time 0.157
value 220 trial 5 time 0.157
-
>> I would like to know your opinion
I honestly don't know. I don't understand the part of the algorithm that calls for removing half of the columns at random and starting over. Unfortunately I don't have much time right now to look at it, so I'll just have to wish you luck. Good Luck.
-
Ok..if sometime you could look at look at it..
anyway thanx for all again