# iterated greedy!!

Printable View

Show 80 post(s) from this thread on one page
Page 2 of 5 First 12345 Last
• 12-06-2006
Daved
>> 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.
• 12-06-2006
joan
>>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
• 12-06-2006
Daved
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.
• 12-06-2006
joan
Daved, from what i understand that u said it is the first case!!

>>But in your example your first step was:

Exactly, in the first step the ????? is 0 because no row is covered yet.

That's why in the second step k_2 is 1/3 the column 2 covers 2 rows( the second and the third ) but the third is ALREADY COVERED BY the column1 so we don't calucalate it to find k.

Does that make sense?? I hope i have cleared thing now
• 12-07-2006
Daved
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?
• 12-07-2006
joan
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??
• 12-07-2006
Daved
GetMax looks good. Even better than how I was thinking of doing it.

Question: Can the values ever be negative? The reason I ask is because GetMax looks through all the values in k, even the ones for columns that have already been covered. So If negative numbers are not allowed, you can set the k[i] value to 0.0 or -1.0 when i is a column that has been covered. That way GetMax will never select that column, because -1 will never be the max.

Another small change: You have declared k as an array of integers. That should be an array of double. In programming, 1/3 is 0 if you are working with integers. 2/3 is also 0. There are no decimal or fractional parts with integers. So your k values will be truncated which would be bad. So If you change k to an array of double (and change GetMax to take an array of double) then you will not get that error and 1/3 will be 0.3333 and 2/3 will be 0.6667 and you will be able to find the correct max.

So you still have to:

a) Update the k array to be an array of double.
b) Identify if a column has already been covered so you don't calculate k for that column.
c) Figure out how to calculate ?????.
d) 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.

For a) see above.
For b), perhaps an extra map (or set) that stores the indexes of the columns you have already added to the solution.
Obviously c) is the hard part (which is what you asked about in the beginning). Sorry. I haven't had time to really come up with anything. Hopefully you have been thinking about it as well.
For d) I think more work needs to be done for that. The random_shuffle and then erase the second half technique would work, but would shuffle the columns, and I'm not sure you want to change the order of the remaining columns.
• 12-07-2006
joan
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
• 12-07-2006
Daved
See my edited post above.
• 12-07-2006
joan
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 ;   }```
• 12-07-2006
Daved
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.
• 12-07-2006
joan
>>you can set the k[i] value to 0.0 or -1.0 when i is a column that has been covered
The rows are covered by the columns, not the columns.I don't know if it was a mistake or u didn't understand.Anyway i understand what u are trying to say for changing k to double and it is correct, but really i don't know how.All i did so far after the changes i showed u is to declare
Code:

` double k[4000];`
and it comes up a warning like the above.And i don't want to change any member of any other class, because i have been given them.I haven't write them.
I understand why u don't want to give me directly a code but...anyway
• 12-07-2006
Daved
>> 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?
• 12-07-2006
joan
the warning is:
Code:

`aSol -> add_column(GetMax(k,instance->n_cols));  warning: passing 'double' for converting 1 of void Solution::add_column(int)'`
The code of the solution is
Code:

```void Solution::add_column(int i) {     selected_columns.push_back(i);   obj_value = obj_value + (instance->cost)[i];   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;       is_added[i] = true; } } }```
For the second question i did that: as u see i added the map is_added when we add a column.I also inculded it to the header file as
Code:

` map<int,bool> is_added;`
A little change.I didn't want to do, cause these are ready given.Maybe things get worse

And then into the main programme as:
Code:

```Solution* aSol = new Solution(instance); double k[5000];   while (!aSol -> is_complete()) {           for (int i = 0; i < instance -> n_cols ; i++) {                   if (!aSol -> is_added[i]){                                     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() );```
How do you see that?

what do u mean i changed the return value? the return value represents the corresponding index of the biggest element(column in this case) of the set with the columns we add
• 12-07-2006
joan
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
Show 80 post(s) from this thread on one page
Page 2 of 5 First 12345 Last