Thread: iterated greedy!!

>> This i don't really understand
This is what I was trying to explain earlier. You cannot add a column to the solution more than once, right? So in your example, in your first step you see that column 1 has the highest value for k. So you add column 1 to the solution. The next time through, you don't want to add column 1 to the solution again, so you should not calculate k for it. It should be ignored in the calculation.

>>You needthe column index that has the largest value, not the actual value, right?
For example if k[1] is the biggest i will add column 1 to the set.

>>Ok, so you should probably be passing k to the GetMax function, not k[j], right?
Yes, you are right.

Look at the code above.I hope that i have understand :-)

Code:

while (!aSol->is_complete()) {
  for (i=0; i< instance->n_cols; i++) {     
         k[i] = (covers[i].size() - i) / c[i];// i think this is wrong

   //If current column has not already been added to the solution:  I really don't know how to    do this. I have to write new code, define is_added for example boolean funtion??

}
         GetMax(k, covers[i].size() ); // not counting columns already added to the solution??
         aSol->add_column(i);
      
}

I think i'm more confused.... You can see that i'm really a beginner and it is quite difficult.And this is only a part...If u can me a hint more..Already u have help me very much

I think you are actually close, and it seems you are understanding pretty well.

>> k[i] = (covers[i].size() - i) / c[i];// i think this is wrong
Ok, now I realize why this is wrong. The 'i' that I colored red is not the i from the loop. You need a new variable. When I was suggesting the two loops, the red 'i' was from the outer loop, but now that we removed the outer loop, we need a new variable to replace the red 'i'.

Here is where I am confused. In your first post, and later in your example, you said that the ????? in the formula stands for the rows that have been covered. But in your example your first step was:

Code:

k_1 = 2/1    k_2 = 2/3    k_3 = 1/2

So k_1 was largest. Now in the second step you say that you subtract the rows that have been covered. Does that mean your matrix looks like this:

Code:

     1   0   0
     0   1   1
     1   1   0

Or like this:

Code:

     1   0   0
     0   1   1
     1   1   0

where green is covered and ignored and black is not. If you meant the first one, I guess it is much more difficult, and I am sorry I was confused. I will wait for you to tell me which one before I confuse things more about this issue. You should remove the i and we'll try again to solve your original problem.



While you are still trying to figure out the ?????, another thing to work on would be to fix GetMax so that it returns the column, not the nBiggest value. You will need a new variable in that function to remember what the column index is for biggest value.

Then you need to use the return value of the GetMax function and pass that value to the add_column function, because the result of GetMax will be the column you want to add to the solution. I hope that makes sense.

Yeah it makes sense. I was thinking that you were subtracting 1 because one column had been covered, but you had been subtracting 1 because of the 2 rows that were covered, only one was covered by the current column. Either way your example was working. But it doesn't matter now. I understand.

Have you gotten anywhere on fixing GetMax?

Yes. I have modified the code as follows:

Code:

int GetMax( int nIn[], int nMax ){

   assert(nMax > 0);
   int MaxIndex = 0;
   for ( int i = 1; i < nMax; i++){
	   if (nIn[i] > nIn[MaxIndex]){
         MaxIndex = i;
	   }
   }
         
   return MaxIndex ;
   
}

which gives me the index of the greatest value. It works for a simple programme.

And then i use it like this in the following code(This is as far i get by now):

Code:

Solution* aSol = new Solution(instance);
  
  SC_instance* covers;
  Solution* selected_columns;
  int k[instance->n_cols];
  while (!aSol -> is_complete()) {
	  for (int i = 0; i < instance -> n_cols ; i++) {
		  //If column i has not already been added to the solution

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

	  
		  aSol -> add_column(GetMax(k,instance->n_cols));
  }

  
   random_shuffle (aSol -> selected_columns.begin(), aSol -> selected_columns.end() );

.

Then i must randomly delete let's say the half of the columns and repeat for the half of te set the procedure. But one at the time.!!!

What do u think??

So, there are 3 things left.

1) the ?????? term
2)how to express >> //If column i has not already been added to the solution
3)remove half of the columns of the solution we obtain and repeat the first step, this time for
a partial solution and not for the empty set we had at the beginning.

If you have any idea for these, u would help me VERY much..I'm totally lost

See my edited post above.

if i change k into double there are 2 errors

Code:

1)
k[i] = (instance->covers[i].size())/(instance-> cost[i]);  : error: invalid types 'double[int]' for array subscript

2)
aSol -> add_column(GetMax(k,instance->n_cols));  error: cannot convert 'double' to 'double*' for argument '1' to 'int' GetMax(double*, int)'

What am i doing wrong?? Things getting worse.
i also changed

Code:

double GetMax( double nIn[], int nMax ){

   assert(nMax > 0);
   int MaxIndex = 0;
   for ( int i = 1; i < nMax; i++){
	   if (nIn[i] > nIn[MaxIndex]){
         MaxIndex = i;
	   }
   }
         
   return MaxIndex ;
   
}

Try and understand my reasoning for suggesting the change. Switch everything back to int, and then re-read what I wrote (the full explanation) and see if you understand what I'm saying. If you understand it, then you should be able to make the change correctly. If you are having trouble understanding what I meant, ask specific questions about it here.

>> you can set the k[i] value to 0.0 or -1.0 when i is a column that has been covered
Sorry. I meant:

"you can set the k[i] value to 0.0 or -1.0 when i is a column that has been added to the solution."

>> double k[4000];
This seems fine. What warning does it give? The error you posted above looks like you used double k; instead of double k[4000];.

In GetMax you changed the nIn array to a double array. That is good, because that is the array that represents the values in k. So why did you change the return value? What is the return value supposed to represent?

Hey, ireally want to thank you.This is very important subject for me. Without your advises i dont know...and i like it like this..not giving me a code directly..

thanx