RR-DB-GK22-2

On this page, instances for the the Recoverable selection problem under discrete budgeted 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. Moreover, we use C_i as the first-stage cost of item i, c_i as the second-stage nominal value of item i ∈ [n] and d_i for the second-stage  deviation of item i. Also we refer to the parameter controlling how many items might deviate to its upper bound in the second-stage as Г. Furthermore, we use a recovery factor, called ∆, that means at least ∆ items of the first-stage solution must remain in the second-stage solution.

Method Description: For all i ∈ [n], we choose C_i  iid uniformly from {1, . . . , 100},set c_i = 100 – C_i and choose d_i from {c_i , . . . , 100}.

Here the instance set consists of three different folders with different problem size. There are problems with n=100, p=25 and Γ, ∆ ∈ {5, 10, 15, 20} in the first folder, problems with n=100, p=50 and Γ, ∆ ∈ {10, 20, 30, 40} in the second one and problems with n=100, p=75 and Γ, ∆ ∈ {15, 30, 45, 60} in the third one. For each problem size, we generate 50 instances, thus each folder has 800 instances. The instance files are named as “instance–n–p–Γ-∆-9-x”, where x represents the number of instance (1 ≤ x ≤ 50). In addition, each instance file contains four lines. The first line represents n, p and Γ the second line forms C_i for i ∈ [n] and the third and fourth lines show c_i and d_i for i ∈ [n], respectively.

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.

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.