Generation of more paths with BiDirectional algorithm

[MattiaMiolato]

Dear @torressa ,

I am currently working on a branch and price framework and have chosen the BiDirectional algorithm as a column generator. I was wondering if it is possible to obtain not only the best path but a list of the best k-paths. Do you think it can be done?

Thank you for your time

[torressa]

Hi @MattiaMiolato! You can indeed do this, but you will need to make some changes to the source code.

First, you can add int k as a parameter to the Params class and adding this to the BiDirectional setters, e.g. https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/bidirectional.h#L92-L94

In BiDirectional the final path that is given is saved in https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/bidirectional.h#L153

If you were to make this into a std::vector, or maybe a std::multiset, of size k (which can be accessed internally as params_ptr_->k), say ordered by weight, you could then only keep the k best Source-Sink paths.

Adding them either:

1. At the end, during the merging procedure if you planning of using the bi-directional search: https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/bidirectional.cc#L733-L735
2. On the fly if you planning on using a mono-directional search: https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/search.h#L38 Which would also be converted to a std::vector (or std::multiset) of k Labels. Adding to this is currently controlled by: https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/search.h#L92

The idea is the same in both cases, instead of overwriting the current intermediate_label, you would just do an insertion (in the appropriate fashion to keep the order/size limited to k).

Finally, once you have done this, you can at the end retrieve the k-th path by adding an extra argument to the function https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/bidirectional.cc#L41-L43

e.g.

std::vector<int> BiDirectional::getPath(const int & k) const {
  return best_labels_->at(k).partial_path;
}

This will throw an exception if k is out of bounds, assuming for example that best_labels_ is defined as

 std::shared_ptr<std::vector<labelling::Label>> best_labels_; 

[MattiaMiolato]

Thank you for your reply! I think I almost made it, but I still have some trouble. I want to use only the bidirectional search. How do you think I should change the following lines of code? https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/bidirectional.cc#L595-L630

In particular, if I set all the weights equal to 0, the algorithm ends in a couple of minutes without finding/saving a feasible path.

[torressa]

In particular, if I set all the weights equal to 0, the algorithm ends in a couple of minutes without finding/saving a feasible path.

I guess you need a way of adding multiple labels to your vector best_label_. Similar to what you were trying in your fork, in the joinLabels loop. Maybe an auxiliary function like:

void insertLabel(
    std::vector<labelling::Label>* sorted_label_vec,
    const labelling::Label&        label) {
  // Find the first label with a larger weight than `label`
  auto it = std::find_if(
      sorted_label_vec->begin(),
      sorted_label_vec->end(),
      [&label](const labelling::Label& l) { return l.weight > label.weight; });
  if (it != sorted_label_vec->end()) {
    sorted_label_vec->insert(label, it);
  }
  // Maybe also ensure that the size is == `k`, if not just `sorted_label_vec->pop_back()`.
}

Then in your joinLabels around here (no need for the if-statement or std::sort) you can just do:

insertLabel(best_label_.get(), merged_label);

I think I almost made it, but I still have some trouble. I want to use only the bidirectional search. How do you think I should change the following lines of code?

For now, you can just comment out everything except the joinLabels part to make sure that what you are doing makes sense.

If you want src/cc/search.h you can change the intermediate_label to be of the same type as best_label_ (std::shared_ptr<std::vector<labelling::Label>>) and then replace https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/search.h#L92 with

 void replaceIntermediateLabel(const labelling::Label& label) {
    insertLabel(intermediate_label.get(), label);
  }

After this, since intermediate_label and best_label_ are both the same type, in postProcessing, you can just swap the two around. edit This will only work for forward search, backwards one needs to iterate and run labelling::processBwdLabel on each label but don't worry about this.

[MattiaMiolato]

I think I find what's going on. When a new label is initialized it has as weight 0: https://github.com/torressa/cspy/blob/ba8a0593668fc97ad61f73c362e9854473334ff6/src/cc/labelling.h#L26 So, if I set all the weight in the graph equal to 0, every feasible path has total weight equal to 0. Then, this disequality is never verified return l.weight > label.weight; (in insert label). This issue prevents the algorithm from adding new paths.

Now everything is working for me. Thank you again for your support.

[torressa]

Oops, didn't think of that, might make the weights infinity or "nan" so this and other similar things don't happen. Well done in getting this working. May steal this from your fork in the future. I'll close this for now. Feel free to reopen.