Description

On this page, instances for the the Recoverable selection problem under discrete uncertainty set could be found. In addition, information with regard to the size of instances provided as well as an overall description of the considered method of instance generation is available. For more general purposes, the instance generator software is also accessible through a link to our github repository. Finally, if more detail about theory or application of this method is desired, the main publication introducing this method could also be reached.

It must be noticed that in order to refer to the parameters of the robust selection problem, we use n for the number of items, p for the number of items we need to choose, N for the number of scenarios and ∆ for the recovery factor. Moreover, we use Ci to present the first-stage cost of item i and cij to show the second-stage cost of item i in scenario j.

Method Description: In this method, first an uncertainty set is generated using the following method:

For all i ∈ [n], with 50% probability we choose Ci from {1, . . . , 100} and with 50% probability we set Ci = 50. Then, for all i ∈ [n] and j ∈ [N], if Ci = 50 with 50% probability we choose cij from {1, . . . , 10} and with 50%  probability we choose cij from {91, . . . , 100}; else, we choose cij from {Ci 5, . . . , C i + 5} and set negative values to be equal to zero.

Now, a new second-stage uncertainty set is generated by adjusting the nominal second-stage costs, using an optimization model, as follows: each cost coefficient can vary with respect to a parameter called budget (b). In addition, the summation of cost coefficients in new scenarios must be the same as the summation of cost coefficients in respective nominal scenarios.

Instance Format

The instance set here consists of three datasets. In dataset1, we consider the cases when N = n = 50, p = 25, ∆ ∈ {13, 20} and N = n = 100, p = 50, ∆ ∈ {25, 40}. In dataset2, we fix n = N = 50, but change p and ∆, using p = 25, ∆ ∈ {13, 20}, p = 30, ∆ ∈ {15, 25}, and p = 40, ∆ ∈ {20, 30}. Finally, in dataset3, we fix n = 50 and p = 25, but change N ∈ {40, 50, 60} and ∆ ∈ {13, 20}. It must be noticed that we consider b = 1, 2 or 5 for each instance. Then, for each parameter choice, we generate 50 instances. Thus there are 600 instances in dataset1, 900 instances in dataset2 and 900 instances in dataset3. These instances are named as “instance-n-p-N-∆-221600b-x” where x represents the number of instance (1 x 50). In addition, each instance file contains N+2 lines. The first line represents n, p, N and ∆ the second line represents the first stage scenario (including n item costs) and the remaining lines forms N given second stage scenarios.

Generator Software

Although it is a good idea to have a library of instances for the robust optimization problems, it is not possible to upload all possible combination of problem parameters on a website. Alternatively, the generator software could be accessed so that any instance size could be generated. Therefore, it is possible to access a C++11 code which is used as the generator software. Moreover, for the optimization part of the code, C++11 is linked to CPLEX.20.10.

Reference

This page has been created based on the information provided in the following paper:

  • Goerigk, M., & Khosravi, M. (2022). Benchmarking Problems for Robust Discrete Optimization. arXiv preprint arXiv:2201.04985.