iterated greedy!!

Ok, ithink i have to be more specific. In my previous thread there is a description of the problem.Suppose the code:

the first step is:

Code:

---

for (i=0; i< instance->n_cols; i++) {
k[i] = (covers[i].size() / c[i]
}

---

The second step:

Code:

---

for (i=1; i< instance->n_cols; i++) {   
     
      k[i] = (covers[i].size() - ?????) / c[i]
}

---

vectors to use(members of a class) :

Code:

---

map<int,vector<int> > covered_by;// columns that cover a row
map<int,vector<int> > covers; //  rows that covers a column
map<int,bool> is_covered; // if a row is covered

---

What i'm looking for is that (?????) term which indicates the number of rows that have been covered( and there are also covered by this column) and how can i determine the # of steps. Then i have to pick up the max of k[i] and add the corresponding column to a set. I hope that i'm a bit more clear now.

Thanx!

How do you determine the ????? value? Does it increase every time? Can you give a small example of actual values step by step and show what each piece of data would be at each step?

Ok.. Here a small example:

Suppose the matrix :

Code:

---

    1  0  0
    0  1  1
    1  1  0

---

The first column(from the left) has cost 1.The second 3 and the third 2. Then we can see that the first column covers rows 1 and 3. the second column covers rows 2 and 3, and the third column covers only the row 2. So as it is defined

Code:

---

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

---

We pick the column with the biggest k (in this case the column 1) and we put it in a set S={1}.

Code:

---

In the second step we have the columns 2 and 3.  We do the same:

k_2 = 1/3(subtract the row that has already been covered)  k_3 = 1/2. We pick the column again with the biggest k and put it in the S, so we have S={1,3}. And we finish.All the rows are covered.

---

This is a very simple example. Just to see how it works

Can you just keep a counter variable and increment it every time you cover a row?

The previous code i had posted was wrong.This one is right.
How will i use this counter? In the k[] expression??

I hope that u have understand how the algorithm works.At least this part

I would do a nested for loop. The outer loop runs from 0 to less than the number of columns. Each time through the outer loop you find the column with the biggest k out of whatever columns are left. To do that, you set the new value for k for all columns that are left (this is what happens in the inner loop). While you do it you remember which one had the highest value. When the inner loop finishes, you mark the one with the highest k as being set so it won't be looked at the next time the inner loop is run.

So the ????? in that situation will just be the index of the outer loop, since the outer loop is removing columns one at a time. What you have to do is add code to remember which k is the highest each time the entire inner loop is completed, and then mark that column so that it won't be included the next time through. I'm guessing that is what the is_covered map is for.

First Daved thanx for the help,because i'm really desperate. But as a beginer in c++ i haven't really understand very well.Also my english is not very good(i'm spanish).Could u write me one or two lines.?
I have written a GetMax() function which calculates the max number of a given vector.As i have understand the outer loop will be

Code:

---

for (i=0; i< instance->n_cols; i++)

---

the inner loop how it will be??. From what u said k will be like

Code:

---

k[i] = (covers[i].size() - i) / c[i]

---

??

thanx again

>> the inner loop how it will be
I think you had it in your code in the first post before you edited it. It will run through all of the columns. Make sure you give it a different index name other than i so there is no confusion. So if you used j, then you are correct, the inside of the inner loop would include the line:

Code:

---

k[j] = (covers[j].size() - i) / c[j];

---

However, you only want to do that if k[j] has not been officially set yet. So you should check your is_covered map to see if the value for j in the map is true. If it is, then I think you should skip that line of code. In your example, you skip column 1 in the second step because it had the biggest k in the first step, that is basically what you have to do here.

I don't want to give you all of the code because I don't want to do any part of your project for you, but I will continue to try to explain what I think you should be doing. Just be clear about what you understand and what you don't.

What do you mean by skip that line?? which line? i didn't skip it. I just put it in the set S which will be the solution.

k[i] or k[j] what ever, is a measure to choose the best column to put in the S.

Maybe i was not very clear before.

The inner loop will run from j=0 until the number of rows,no? And if yes it will be wrong, because k refers to the columns.

I think..i'm not sure

ok..i didn't see that u had write columns for the inner loop.
Sorry!!

But still k is not the set. and i cannot skip that line..it is the basic criterion to choose the best column

>> What do you mean by skip that line?? which line? i didn't skip it. I just put it in the set S which will be the solution.

Exactly. In your example, you put column 1 in the set S in the first step. Then in the second step, you said, "In the second step we have the columns 2 and 3. We do the same". You don't use column 1 in the second step because it has already been put into S. That is what I mean by skip. In step 2, column 1 cannot have the biggest k because you already used it for the first step.

It would be helpful if you posted your entire loop as is, without cutting it up or editing it. Just copy and paste the entire piece of code that you have right now that runs these loops. That will make it easier for me to understand what you have done and how you are doing it.

Ok..But i haven't write all the algorithm yet. I'm working in this part..After your advise it would be:

Code:

---


Solution* aSol = new Solution(instance);// it is just a solution
// i initialize all the values to zero and the solution also ( the solution would be the set )

while (!aSol->is_complete()) {
  for (i=0; i< instance->n_cols; i++) {
    for (j=0; j< instance->n_cols; i++){
        k[j] = (covers[j].size() - i) / c[j];
        GetMax(k[j], covers[j].size() );
        aSol->add_column(j);
      }
    }
}

---

It would be sth like that

Ok, first, my suggestion for the outer for loop was meant to do exactly what your code while (!aSol->is_complete()) does. You didn't post that originally so I suggested you add the for loop, but since you already have that in there you only need one. So you can remove the outer for loop now.

>> for (j=0; j< instance->n_cols; i++){
Second, in that line above you forgot to change the i++ to j++. I don't care whether you switch it back to i or to j, just make sure they are all correct. I might suggest this instead just to be clearer:

Code:

---

for (current_col=0; current_col< instance->n_cols; current_col++){

---

Third, what does the GetMax function do exactly? Can you post it? I think that you are not using it correctly.

In that code, you are calling add_column for every column in the inner loop. I think you only want to add 1 column, the one with the biggest k. So my pseudocode might be:

- 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

Does that make sense?

the code of GetMax is:

Code:

---

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

  int nBiggest = nIn[0] ;
  for ( int i = 1; i < nMax; i++)
      if (nBiggest > nIn[i])
        nBiggest = nIn[i] ;

  return nBiggest ;
}

---

>>Second, in that line above you forgot to change the i++ to j++.

In the inner loop you say? I think i changed it.

So you suggest to take out the outer loop. Ok, the pseudo-code makes sense to me.But in this case k how it would be?

Yes u are right. I should write add_column outside of the loop.It was mistake

>>Find the column with the largest value in k, not counting columns already added to the solution.
This i don't really understand

Ok, so you should probably be passing k to the GetMax function, not k[j], right? That would make sense if you call GetMax outside the for loop, then use whatever column had the max as the column you pass to add_column.

One issue that you might have is that GetMax is returning the largest value. You needthe column index that has the largest value, not the actual value, right?

Post your latest code as you make changes so we can make sure we understand each other.

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

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

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

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.

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

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

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

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

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

Quote:

---

- 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 i have understand what u are trying to say.

But really, i don't know how to make the function( what parameters to use, etc..).It is quite complicated.

One question: the >> rows that have already been covered by columns added to the solution would be this count increments every time the row is not in the is_covered map??

and second, i would use the same index i ?? i will try to make an inner loop

i have write this code, but i have many errors. I will try to figuer out what's goin on. If any time you are online and see it, say to me what u see wrong!! As you see below i have mess a little up things.Here u are:

Code:

---

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++;
                                                              }
                                                 
                                  }
                          k[i] = ((instance->covers[i].size()) - (instance -> covered_by[j][i].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 );

---

i get 2 errors(also for erase,but this will look after) for the line

Code:

---

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

---

1) request for member 'size' ......
2)name lookup of 'j' changed for new ISO 'for' scoping

and one error for the line

Code:

---

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

---

1)using obsolete binding at 'j'

Maybe i didn't understand that well.Also i don't know what do these errors mean.. :-(

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

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

for example, the function rmv_columns if it was sth like this:

Code:

---

void Solution::rmv_column(int i) {


        selected_columns.erase(i)
    obj_value = obj_value - (instance->cost)[i];
        is_added[i] = false;
    for (int j = 0; j < (instance->covers)[i].size(); j++) {
        int aRow = (instance->covers)[i][j];
          is_covered[aRow] = false;
        }
}

---

the part selected_columns.erase(i) is not correct.Just to show.I want to erase that concret column

and then use it in the code like this:

Code:

---

for ( int i = 0; i < aSol->selected_columns.size()/2; i++){
        aSol-> rmv_column(i);
}

---

u think it would work??

Your idea to use selected_columns.erase(i) seems like a good idea to me. How is it working?

One possible problem is that you are erasing from the selected_columns vector at the same time as you are looping through it. This might make your loop code skip over some objects and not remove half of the columns.

Another possible problem, which I think might be worse, is that random_shuffle is shuffling the columns inside selected_columns, but not inside instance->cost, instance->covers, and your other variables. So after calling random_shuffle the columns inside selected_columns don't match the ones in the other variables. I don't know if this is a problem or not, but it might cause you weird output.

Ok. i will explain. You have seen my final code.

Code:

---

start:
 
  int not_covered;
  for (int n=1; n <= num_trials; 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));
         
        }
         
          //cout << " value " << aSol->value() <<" trial " << num_trials << "\ttime " << timer.elapsed_time(Timer::VIRTUAL) << endl;
}
  cout << " value " << aSol->value() << endl; 
  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  );
  cout << " value " << aSol->value() << endl;
  if (!aSol-> is_complete())
  goto start;

---

What i want to do, is when find a solution does the shuffle( maybe it is not right), erase the half of the columns and repeat until it finds a new solution. Just to check i put these two cout and i see that gives me the same value( as you said also ).So that erase or shuffle or both DO not do anything.

Any suggestion for these??
First: should i skip totally el shuffle?
The first you said i don't understand really well. How it should be?

Ok..If i also comment shuffle it stils give me the same output.That means for some weird reason no erase columns.The selected_columns is defines into void Solution::add_column()

I thought you were using rmv_column? I think the rmv_column idea was a better idea. Did you try that?

Yes, but i don't know how to write it.As you see above. I don't know how to express the selected_columns.???? part. if i do for example selected_columns.pop_back() it just gives me smaller values ( subtracting the last column of the set and nothing else ). I think it would work but as i said i don't know how to write it -> when i erase a column from the set (selected_columns ) this to have effect in all my variables. You understand me?
This is why not working erase?? You see anything wrong in the code?? the goto part u think it's good?
i really thought that i had it done.. :-(

I thought this code looked good:

Code:

---

void Solution::rmv_column(int i) {


        selected_columns.erase(i);
    obj_value = obj_value - (instance->cost)[i];
        is_added[i] = false;
    for (int j = 0; j < (instance->covers)[i].size(); j++) {
        int aRow = (instance->covers)[i][j];
          is_covered[aRow] = false;
        }
}

---

You need a semi-colon, but otherwise I don't see why it wouldn't work. Did you try it?

>> the goto part u think it's good?
No, I think goto is not a good idea, but if it works, now is not the time to change it. Leave the goto there and focus on the stuff that is not working.

I don't know if that expression >>selected_columns.erase(i); is correct. Because i look at the definition of erase and it is not quite like this.Also when i compile it like this i get an error for this: no matching function for call to 'std::vector<int, std::allocator<int> >::erase(int&)'

I tried instead of that this one:

Code:

---

selected_columns.erase(selected_columns.begin()+ (i-1),selected_columns.begin()+ i);

---

to erase the column of the position i. I'm not sure if is the same thing.Erase the column from the position i and erase the column i. i compileit and it is correct. But the problem that i told you before remains.Just calculates values which are decreasing..I don't know if is a problem of the loops..

You're right. Use this:

Code:

---

selected_columns.erase(selected_columns.begin()+ i);

---

I really don't know if it works or not. In the first iteration i get a value that it is close to the optimal solution.In the other steps i get smaller and smaller values until one that is the smallest and after this one are repeated.Is this a solution?? i don't know if it's normal or it is because of the algorithm. Wouldn't it be supposed to get better solutions after each step or not? I'm just asking because i don't know really much about algorithms.With this line that you send me it works, but as i just described you.But looking at the void::rmv_column, erasing that column has effect in all the other variables,no? So, typically is correct. Is it a fault of the code(loops or sth)? I would like to know your opinion
And by the way the final code

Code:

---

int not_covered;
  for (int n=1; n <= num_trials; 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));
         
        }
         
      cout << " value " << aSol->value() <<" trial " << num_trials << "\ttime " << timer.elapsed_time(Timer::VIRTUAL) << endl;

 
  //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  );
  for ( int i = 0; i< aSol->selected_columns.size()/2; i++){
          aSol-> rmv_column(i);
  }
  }

---

also, if you have time to look it.. the algorithm has as inputs -i ( the instances) -t time and -n the number of trials. i have defined all these as:

Code:

---

void read_parameters(int argc, char **argv)
{
  int iarg=1;

  while (iarg < argc) {
    if (strcmp(argv[iarg],"-i")==0) {
      inputFile = argv[++iarg];
    }
    if (strcmp(argv[iarg],"-t")==0) {
      tmax = atoi(argv[++iarg]);
    }
    if (strcmp(argv[iarg],"-n")==0) {
      num_trials = atoi(argv[++iarg]);
        }
    iarg++;
  }
}

---

But i dont know how to write, make a loop maybe so that in every trial it gives me the value, #of this trial and the time to compute this value. Because if i write to run for example:

./ig.exe -i instances/scp51.txt -t ( this must me the maximum time i want to put for the iteration) -n 5 it gives me sth like this:

Code:

---

value 289      trial 5          time  0.157
value 256      trial 5          time  0.157
value 239      trial 5          time  0.157
value 228      trial 5          time  0.157
value 220      trial 5          time  0.157

---

>> I would like to know your opinion
I honestly don't know. I don't understand the part of the algorithm that calls for removing half of the columns at random and starting over. Unfortunately I don't have much time right now to look at it, so I'll just have to wish you luck. Good Luck.

Ok..if sometime you could look at look at it..

anyway thanx for all again