Thread: iterated greedy!!

Hi Daved..
For your first question: I asked my profesor and he told me that it would be no problem removing some columns of the set( half of them would be nice) randomly.That means that the columns in the set not supposed to be in a specific order.(the order depends on the value of -> which column has the best and so we order them)
So, i wrote this code that( for the moment, i don't know if it is correct because i don't know how to use random_shuffle and erase)

Code:

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  );

I tried really to make a function as you advised me, but i couldn't.So i pick this way.I know it's not the best(easier).

For the second thing.If i take k[i] out of the for(j = 0...) loop that is:

Code:

while (!aSol -> is_complete()) {
	  for (int i = 0; i < instance -> n_cols ; i++) {
			  if(aSol -> is_added[i]){
				  k[i] = -1;}
			  
			  else{	
				  for (int j = 0; j < (instance->covers)[i].size(); j++) {
                                                                     int aRow = (instance->covers)[i][j];
                                                                         if (!aSol -> is_covered[aRow]) {
							                        n_covered++;
							                       //is_covered[aRow] = true;
						  }
						  
				  }
		          k[i] = ((instance->covers[i].size()) - (instance -> covers[j].size()))/(instance -> cost[i]);
				  
			  }  
	  }
          aSol -> add_column(GetMax(k,instance->n_cols));
  }

i get 2 errors
for the line

Code:

 for (int j = 0; j < (instance->covers)[i].size(); j++) {

error: using absolete binding at 'j'
and for the line:

Code:

k[i] = ((instance->covers[i].size()) - (instance -> covers[j].size()))/(instance -> cost[i]);

error:name lookup of 'j' changed for new ISO 'for' scoping

I really don't understand what do these 2 errors mean. If i use somehow the n_covered count into the k[i] expression it will be solved??

Since you declared the variable j in the for loop initialization section, it should only be visible in the for loop itself. However, some old compilers made the variable visible throughout the remainder of the block, which is what your code is assuming. Your compiler is complaining about this, and rightly so.

The solution: declare j before the for loop so that it's visible after the for loop.

Code:

int j;
for(j = 0; /* ... */; /* ... */) {

}
/* ... */ covers[j] /* ... */;

No Daved..this is the part i cannot write..In theory i know how it works(ok it's not that difficult)

But i cannot express the term: "The rows that covers the current column - the rows that have been already covered and at the same time are covered by the current column"

i know that simply write

Code:

k[i] = ((instance->covers[i].size()) - (n_covered) /(instance -> cost[i]);

would be wrong. If you can give any hint( not tell me direct the code) i would thank very much.
The last two days i'm working on this subject.( as i told u i'm quite a beginner in programming and although for some people this is easy, for me not)

and when you say>>It shouldn't be using j at all, you mean that i should eliminate totally the for ( j = 0;......) loop??

By the way, n_covered is already defined( as i just used it) like this:

Code:

void Solution::add_column(int i) {

  
  selected_columns.push_back(i);
  obj_value = obj_value + (instance->cost)[i];
  is_added[i] = true;
  for (int j = 0; j < (instance->covers)[i].size(); j++) {
    int aRow = (instance->covers)[i][j];
    if (!is_covered[aRow]) {
      n_covered++;
      is_covered[aRow] = true;
}

and also in the header file Solution.h

As you see in the definition of the Solution, n_covered is a count that it is increasing when a row is not covered. But still as i told u i cannot express in programming language the term
>>the rows that have been already covered and at the same time are covered by the current column"
Ok the previous to be correct from compilation view would be:

Code:

k[i] = ((instance->covers[i].size()) - (aSol -> n_covered) /(instance -> cost[i]));

If i understood well ( i'm not so sure) then it must be like this:

Code:

while (!aSol -> is_complete()) {
        for (int i = 0; i < instance -> n_cols ; i++) {
            if(aSol -> is_added[i]){
				  k[i] = -1;}
			  
			  else{
				  int not_covered = 0;
				  for (int j = 0; j < (instance->covers)[i].size(); j++) {
                       int aRow = (instance->covers)[i][j];
                          if (!aSol -> is_covered[aRow]) {
							  not_covered++;
							  //is_covered[aRow] = true;
						  }
						  
				  }
		          k[i] = (not_covered) /(instance -> cost[i]);
				  
			  }  
	  }
          aSol -> add_column(GetMax(k,instance->n_cols));
		}

Hi everyone.
I don't know how many of you have read this thread (apart from Daved) there are TOO many posts.Anyway, i have a problem( the last one).This last code:

Code:

int not_covered;
  for (int n=1; n <= NumberRuns; 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));
    }
   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  );

gives me a first solution.Not the optimal but quite close to it.BUT it cannot compute another one because of this

Code:

aSol -> selected_columns.erase ( aSol -> selected_columns.begin(),aSol -> selected_columns.begin() + aSol -> selected_columns.size()/2  );

. What this line do, is erase the columns of the solution,WITHOUT erasing the rows that they cover.That's why it cannot compute another solution. I want to erase the half of the columns and the rows that they cover. I thought of writing a function like this one:

Code:

void Solution::add_column(int i) {

  
  selected_columns.push_back(i);
  obj_value = obj_value + (instance->cost)[i];
  is_added[i] = true;
  for (int j = 0; j < (instance->covers)[i].size(); j++) {
    int aRow = (instance->covers)[i][j];
    if (!is_covered[aRow]) {
      n_covered++;
      is_covered[aRow] = true;
     }
  }
}

which will be called let's say rmv_column and it will do the opposite of add_column and then run it in a for loop for the half of the columns of the solution.But i don't know how it woud be the

Code:

 selected_columns.push_back(i);

part and if i should use also the erase function i already have and how..Or if you could suggest me another way,easier..This is the only thing it is left to do.
Please any hint would be really really helpful..