text: We consider the robust version of items selection problem, in which the goal is to choose representatives from a family of sets, preserving constraints on the allowed items' combinations. We prove NP-hardness of the deterministic version, and establish polynomially solvable special cases. Next, we consider the robust version in which we aim at minimizing the maximum regret of the solution under interval parameter uncertainty. We show that this problem is hard for the second level of polynomial-time hierarchy. We develop an exact solution algorithm for the robust problem, based on cut generation, and present the results of computational experiments.
  @cite_4: In Introduction, I explain the meaning I give to the qualifier term "robust" and justify my preference for the expression robustness concern rather than robustness analysis, which I feel is likely to be interpreted too narrowly. In Section 2, I discuss this concern in more details and I try to clarify the numerous raisons d'etre of this concern. As a means of examining the multiple facets of robustness concern more comprehensively, I explore the existing research about robustness, attempting to highlight what I see as the three different territories covered by these studies (Section 3). In Section 4, I refer to these territories to illustrate how responses to robustness concern could be even more varied than they currently are. In this perspective, I propose in Section 5 three new measures of robustness. In the last section, I identify several aspects of the problem that should be examined more closely because they could lead to new avenues of research, which could in turn yield new and innovative responses.
  @cite_7: 
  @cite_8: The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min–max and min–max (relative) regret approaches are used for making a selection decision. The arising min–max, min–max regret and min–max relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line.
  @cite_9: We consider the problem of scheduling jobs on parallel identical machines, where only interval bounds of processing times of jobs are known. The optimality criterion of a schedule is the total completion time. In order to cope with the uncertainty, we consider the maximum regret objective and seek a schedule that performs well under all possible instantiations of processing times. We show how to compute the maximum regret, and prove that its minimization is strongly NP-hard.
  @cite_21: 
  @cite_1: 
  @cite_17: 
  @cite_0: 
  @cite_19: We consider the Assignment Problem with interval data, where it is assumed that only upper and lower bounds are known for each cost coefficient. It is required to find a minmax regret assignment. The problem is known to be strongly NP-hard. We present and compare computationally several exact and heuristic methods, including Benders decomposition, using CPLEX, a variable depth neighborhood local search, and two hybrid population-based heuristics. We report results of extensive computational experiments.
  @cite_15: 
  @cite_10: We propose an approach to address data uncertainty for discrete optimization and network flow problems that allows controlling the degree of conservatism of the solution, and is computationally tractable both practically and theoretically. In particular, when both the cost coefficients and the data in the constraints of an integer programming problem are subject to uncertainty, we propose a robust integer programming problem of moderately larger size that allows controlling the degree of conservatism of the solution in terms of probabilistic bounds on constraint violation. When only the cost coefficients are subject to uncertainty and the problem is a 0−1 discrete optimization problem on n variables, then we solve the robust counterpart by solving at most n+1 instances of the original problem. Thus, the robust counterpart of a polynomially solvable 0−1 discrete optimization problem remains polynomially solvable. In particular, robust matching, spanning tree, shortest path, matroid intersection, etc. are polynomially solvable. We also show that the robust counterpart of an NP-hard α-approximable 0−1 discrete optimization problem, remains α-approximable. Finally, we propose an algorithm for robust network flows that solves the robust counterpart by solving a polynomial number of nominal minimum cost flow problems in a modified network.
  @cite_20: Robust optimization is a young and emerging field of research having received a considerable increase of interest over the last decade. In this paper, we argue that the the algorithm engineering methodology fits very well to the field of robust optimization and yields a rewarding new perspective on both the current state of research and open research directions. To this end we go through the algorithm engineering cycle of design and analysis of concepts, development and implementation of algorithms, and theoretical and experimental evaluation. We show that many ideas of algorithm engineering have already been applied in publications on robust optimization. Most work on robust optimization is devoted to analysis of the concepts and the development of algorithms, some papers deal with the evaluation of a particular concept in case studies, and work on comparison of concepts just starts. What is still a drawback in many papers on robustness is the missing link to include the results of the experiments again in the design.
  @cite_11: Min-max and min-max regret criteria are commonly used to define robust solutions. After motivating the use of these criteria, we present general results. Then, we survey complexity results for the min-max and min-max regret versions of some combinatorial optimization problems: shortest path, spanning tree, assignment, min cut, min s-t cut, knapsack. Since most of these problems are NP-hard, we also investigate the approximability of these problems. Furthermore, we present algorithms to solve these problems to optimality.
summary: The basic variant of this problem has been first considered in @cite_8 under the name Representatives Selection Problem, where we are allowed to select one item from each set of alternatives. In order to alleviate the effects of cost uncertainty on decision making, the min-max and min-max regret criteria @cite_11 @cite_17 have been proposed to assess the solution quality. The problem formulations using these criteria belong to the class of robust optimization problems @cite_4 . Such approach appears to be more suitable for large scale design projects than an alternative stochastic optimization approach @cite_1 , when: 1) decision makers do not have sufficient historical data for estimating probability distributions; 2) there is a high factor of risk involved in one-shot decisions, and a precautionary approach is preferred. The robust approach to discrete optimization problems has been applied in many areas of industrial engineering, such as: scheduling and sequencing @cite_9 @cite_0 @cite_21 , network optimization @cite_10 @cite_15 , assignment @cite_19 @cite_7 , and others @cite_20 .