iterated greedy!!

>> I still have doubts about why u say i shouldn't shuffle the set before i erase the half of it.
I'm not saying you should not shuffle. I am asking you a question that you have not yet answered. If you can answer the question, then I can try to give my opinion about whether random_shuffle is a good idea or not. If it is working for you now and you are ok with it, then that is fine. If it is not working for you, then answer this question: "Is it ok that the order of the data inside aSol->selected_columns changes? Are the columns in aSol->selected_columns supposed to be in a specific order?"

Now, for your posted code, it is very hard to read mostly because the indentation is all messed up. It will help you to fix the indentation (if it looks that bad on your editor), and it will help me too.

The only big thing I see wrong in that code is the k[i] = part. You need to re-do that entire equation. I think you implemented the n_covered count correctly. That is good. But you need to figure out how to use that in the calculation of k[i]. You also need to move the calculation of k[i] out of the for (int j = 0... loop, it should be done after you finish calculating n_covered.

Does that make sense? I really think it would have helped if you had tried to follow my suggestions earlier, but I understand that each person does things in their own way. Hopefully this will help you understand the few small changes you have left to do.

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] /* ... */;

Yes dwks..that works
Thanx

Code:

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

Unfortunately, this line of code is wrong. The fix isn't to put j outside the loop, the fix is to fix that line of code. It shouldn't be using j at all.

Have you figured out how to use the value of n_covered in the equation to calculate k[i]?


As for the random_shuffle part, that is fine. "removing some columns of the set( half of them would be nice) randomly" is not the same as randomly shuffling the order of the columns, but if you think this is ok then I won't worry about it.

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

That's closer.

What does n_covered represent? Feel free to use spanish to explain it if that is easier.

>> when you say>>It shouldn't be using j at all, you mean that i should eliminate totally the for ( j = 0;......) loop??
No. The for (int j = 0; ....) loop was good, it is exactly what I think should work to calculate n_covered. I just mean that you should not use j in the k[i] = ... line of code.

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

My response was before I saw your edit.

I do not think you should be using the same n_covered as you have inside add_column.

The variable you call n_covered that you are using in post #47 should be an int variable that starts at 0 just before the for (int j = 0....) loop. It should be counting:

"the rows that have not been already covered and at the same time are covered by the current column".

That is exactly what it is doing in the code in post #47:

Code:

for (int j = 0; j < (instance->covers)[i].size(); j++) { // (1)
    int aRow = (instance->covers)[i][j];
    if (!aSol -> is_covered[aRow]) {// (2)
        n_covered++; // (3)

That code goes for each row that the current column covers (1). It checks to see if the row is covered by a column already added to the solution (2). If it is not, then it increments n_covered (3).

That is exactly what you want. Now you just have to use that value in the calculation of k.

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

I just deleted my previous message.

I think you've got it. And I am especially glad that you got it without having to read that message. Well done.

Now go see if it works.

>>the number of rows covered by the current column but not by any other column added to the solution" divided by the cost. Isn't that right?
Exactly..

so by using

Code:

k[i] = (not_covered) /(instance -> cost[i]);

we get what we want,no??

Ok. i'll try in action!!

Just want to really really thank one more time..
If it wasn't you to guide me, i simply wouldn't have done it :-)

No sabia que hablas espanol

>> Just want to really really thank one more time.
I'm glad to help.

>> No sabia que hablas espanol
I don't, at least I haven't tried to in years. I just wanted you to try to explain it in your native language as a tool to help you understand, even if I didn't understand what you wrote. Writing or speaking what I am trying to do in English usually helps me understand it better so I can do it right, so I was thinking the same might work for you.

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..