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.
