Thread: iterated greedy!!

>> what do u mean i changed the return value?
You changed the return value of the GetMax function from int to double.

>> the return value represents the corresponding index of the biggest element(column in this case) of the set with the columns we add
Right, and what type is used for the index (column in this case)? int or double?

>> the warning is:
That warning will be fixed when you fix the return type of GetMax.


>> i added the map is_added when we add a column.I also inculded it to the header file
>> A little change.I didn't want to do, cause these are ready given.

You don't have to add is_added to the header. You can just add it to the main program code. Instead of adding the column to this map inside of add_column, you can just add the column to the map in the main program after the code aSol->add_column(GetMax(k,instance->n_cols));.


>> if (!aSol -> is_added[i]){
Good. This will still work if you declare the is_added map next to the k array instead of in the header.


So, for the steps a), b), c) and d) I had above, here is where you are from what I see:

a) You have to fix the return type of GetMax as I mentioned above. This will fix the warning as well. I hope you are allowed to change the GetMax function from the assignment.

b) You did good by using the is_added map. You have to remove that from the header since you are not supposed to change the header, and declare it inside the main program code.
You are only half done, though. You also have to prevent the GetMax function from accidentally choosing a column that has already been added. I already gave one idea for how to do this: if is_added[i] is true, then set k[i] to -1. That way it will never be Max. This will only work if the numbers are always positive numbers.

c) Still have to do.
d) Still have to do.

You are right..i changed by accident the return value of GetMax. Now, it works fine, without warning. Yes, i'm allowed to change it..This is a function i wrote.
There is no restriction(i hope its the right word) to change the headers.I didn't want to, in case i would have problems.

OK!! now i have to work with c and d

Great.

Did you finish the second half of b)?

Yes..
Here is the code by now

Code:

Solution* aSol = new Solution(instance);
  
  SC_instance* covers;
  Solution* selected_columns;
  double k[5000];
  while (!aSol -> is_complete()) {
	  for (int i = 0; i < instance -> n_cols ; i++) {
		  if (!aSol -> is_added[i]){
			  if(aSol -> is_added[i] = true ){
				  k[i] = -1;
			  }
			  else{

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

I compile it without error or warning

Ooops. Look at it again. Here it is with easier to read indentation

Code:

if (!aSol -> is_added[i]){
	if(aSol -> is_added[i] = true ){
		k[i] = -1;
	}
	else{	  
		k[i] = (instance->covers[i].size())/(instance -> cost[i]);
	}
}

Look at those first two lines.

Ok..I think that this is the right

Code:

Solution* aSol = new Solution(instance);
  
  SC_instance* covers;
  Solution* selected_columns;
  double k[5000];
  while (!aSol -> is_complete()) {
	  for (int i = 0; i < instance -> n_cols ; i++) {
			  if(aSol -> is_added[i] = true ){
				  k[i] = -1;}
			  
			  else{

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

It is the first time i work with this..removing randomly elements from an array..I keep searching in internet but i haven't really found what i want ( not exactly, even more or less).

My first attempt is this one

Code:

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

   delete ( aSol -> selected_columns.size() / 2 );

i get an error for the second line:
type 'usigned int' argument given to 'delete', expected pointer..

I dont'know if i'm at the right way.You suggest me to use another command of delete. If no, how would u suggest me to use it?

>> Ok..I think that this is the right
Almost. There is a typo (= should be ==). I would just remove the entire "= true" part and leave it as

Code:

if(aSol -> is_added[i]){

And I just noticed that the call to add_column is inside the for loop. It should be after the for loop, because you only want to add a column after you calculate all the k values, and the k values are all calculated by the for loop.

>> You suggest me to use another command of delete. If no, how would u suggest me to use it?
You would use erase, not delete, but before you use that method you have to answer this question:

Is it ok that random_shuffle changes the order of the data inside aSol->selected_columns?





Anyway, here are my ideas to help you with part c).

I would create a new function. This function would be called to calculate k for a given index i. This will make it a little less confusing to read and fix the code. So your code above would look like this:

Code:

  double k[5000];
  while (!aSol -> is_complete()) {
	  for (int i = 0; i < instance -> n_cols ; i++) {
			  if(aSol -> is_added[i]){
				  k[i] = -1;
			  }
			  else{
				  k[i] = CalculateKValue(instance, i);
			  }
	  }
	  aSol -> add_column(GetMax(k,instance->n_cols));
}

So in that function you have to calculate k. The value k is calculated as the number of rows that are covered by the current column, minus the number of rows that have already been covered by columns added to the solution, dividing all of that by the cost. So, I would loop through instance->covers[i], and check each row in that vector to see if it is in the is_covered map. If it is, then skip it, otherwise increment your count. Then divide all of that by the cost when you are done.

See if you understand what I'm saying, and if you think that will work. Don't write any code yet (except maybe an empty function). Start by writing out in pseudo code how that CalculateKValue function would work. If you can do that, then it will be easy to translate it into code. When I say pseudo code, I mean like I did earlier like this:

- While solution is not complete:
- - For current_column = 0 to num columns:
- - - If current column has not already been added to the solution:
- - - - Calculate k for current column and assign it to k[current_col].
- - - End If
- - End For
- - Find the column with the largest value in k, not counting columns already added to the solution.
- - Add that column to the solution.
- End while

I will try to understand it good and then see if it works..

Only sth that is the key.When you say >> minus the number of rows that have already been covered by columns added to the solution.

Not any rows in general..Rows that have been already covered by columns added to the solution AND at the same time are covered by the current column. I hope that u mean that, because u didn't write. If u don't then is different what u say..

Thanx

That is what I meant.

Ok..i think the mistake is that the term

Code:

 (instance -> covered_by[j][i].size())

indicates the number of columns that cover the j row.So i cannot make this..It has no sense.

I will try to find the right term

Look at this code. Compiling it i get no error(well it's sth). Except for the errors i get for the erase function. I don't really understand if it works. Please, if you can, tell me so. Please..
here it is:

Code:

Solution* aSol = new Solution(instance);
  
  //SC_instance* covers;
  Solution* selected_columns;
  Solution* n_covered;
  Solution* is_covered;

  double k[5000];
  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));
  }

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

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

Daved, if you are online at some point, please check this code. How does it seem to you?

I have to give this project on Monday. I have finished with the rest of the code ( erase and repeat again for the half of the columns)..I still have doubts about why u say i shouldn't shuffle the set before i erase the half of it.

Anyway, if u can please have a look

Thanx a lot for everything