MM-B-GK22-UH-ADD

On this page, instances for the the Min-Max selection problem under 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 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 or the number of items we need to choose. Moreover, we use c_i as the nominal value of item i ∈ [n], d_i for its deviation and also Г for the parameter controlling how many items might deviate to its upper bound.

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

For all i ∈ [n], we choose both c_i , d_i uniformly as an integer number from {1, . . . , 100}.

Now, three new uncertainty sets are generated. We use an optimization model to adjust only the nominal values in the first uncertainty set, the deviation in the second uncertainty set and both the nominal values and deviation in the third uncertainty set. In every method nominal value and deviation can vary with respect to a parameter called budget (b). Here we consider b is a parameter which can be added to the mentioned values.

Here the instance set consists of three folders named “change-c”, “change-d” and “change-cd”. In each folder problems with n = 40 when p = 20 and Γ ∈ {5, 10, 15, 20} is considered. It also must be noticed that with used b = 1, 2, 5, 10 and 20 for the adjustment of scenarios. For each problem size, we generate 50 instances. Thus each folder in the instance set contains 1000 instances. The instance files are named as “instance–n–p–Γ-1-0-600-b–x” for changed-c, “instance–n–p–Γ-2-0-600-b–x” for changed-d and “instance–n–p–Γ-3-0-600-b–x” for changed-cd, where x represents the number of instance (1 ≤ x ≤ 50). In addition, each instance file contains three lines. The first line represents n, p and Γ the second and third 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. Moreover, for the optimization part of the code, C++11 is linked to CPLEX.20.10.

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.