Upper bound procedure

The branch-and-cut algorithm does not always find high-quality solutions for all problem types that we considered in our paper. We, therefore, decided to use the branch-and-cut algorithm to provide lower bounds and to use a simple yet effective upper bound procedure to find feasible solutions. An additional benefit of this approach is that the solver (e.g., CPLEX) used for the branch-and-cut can be set on 'focus on lower bounds', which enhances the quality of the lower bounds.

Our goal is to provide an as simple as possible upper bound procedure that does not require long times to be implemented; so we did not develop heuristics tailored for our problem (e.g., an ALNS). The idea of the upper bound procedure is to use a compact problem formulation in which we only consider promising arcs, that is, for every customer node we only consider the n cheapest outgoing arcs. The resulting MIP is solved with off-the-shelf MIP solvers. This approach is very simple to implement but appeared to be surprisingly effective for the problem types considered in our paper.

For more details on the implementation and the performance of the upper bound procedure (i.e., how many CPU cores are used, how does n increase over time, and when are solutions communicated to the branch-and-cut algorithm), we refer to Sections 5.1 and 6.4 of our paper.

In the remainder of this page, we give some additional notes and we explain how to use our C++ implementation.

Some additional notes

TODO: for some instances, the upper bound procedure finds very good (or even optimal) solutions within seconds. One may consider running the upper bound procedure for a few seconds before the branch-and-cut model is initialized. Hereby a potentially good solution can be used in the pre-processing stage of the solver used for the branch-and-cut algorithm (i.e., possibly allowing to price out some variables).

How to call the procedure in C++

TODO: Explain how to call the procedure, i.e., how to use our C++ code.