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.
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 .
@cite_4 @cite_7 @cite_8 @cite_9 @cite_21 @cite_1 @cite_17 @cite_0 @cite_19 @cite_15 @cite_10 @cite_20 @cite_11
2164571150 2044046971 2165775468 2083259944
One central issue in practically deploying network coding is the adaptive and economic allocation of network resource. We cast this as an optimization, where the net-utility-the difference between a utility derived from the attainable multicast throughput and the total cost of resource provisioning-is maximized. By employing the MAX of flows characterization of the admissible rate region for multicasting, this paper gives a novel reformulation of the optimization problem, which has a separable structure. The Lagrangian relaxation method is applied to decompose the problem into subproblems involving one destination each. Our specific formulation of the primal problem results in two key properties. First, the resulting subproblem after decomposition amounts to the problem of finding a shortest path from the source to each destination. Second, assuming the net-utility function is strictly concave, our proposed method enables a near-optimal primal variable to be uniquely recovered from a near-optimal dual variable. A numerical robustness analysis of the primal recovery method is also conducted. For ill-conditioned problems that arise, for instance, when the cost functions are linear, we propose to use the proximal method, which solves a sequence of well-conditioned problems obtained from the original problem by adding quadratic regularization terms. Furthermore, the simulation results confirm the numerical robustness of the proposed algorithms. Finally, the proximal method and the dual subgradient method can be naturally extended to provide an effective solution for applications with multiple multicast sessions 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. 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. Abstract A large number of problems in production planning and scheduling, location, transportation, finance, and engineering design require that decisions be made in the presence of uncertainty. Uncertainty, for instance, governs the prices of fuels, the availability of electricity, and the demand for chemicals. A key difficulty in optimization under uncertainty is in dealing with an uncertainty space that is huge and frequently leads to very large-scale optimization models. Decision-making under uncertainty is often further complicated by the presence of integer decision variables to model logical and other discrete decisions in a multi-period or multi-stage setting. This paper reviews theory and methodology that have been developed to cope with the complexity of optimization problems under uncertainty. We discuss and contrast the classical recourse-based stochastic programming, robust stochastic programming, probabilistic (chance-constraint) programming, fuzzy programming, and stochastic dynamic programming. The advantages and shortcomings of these models are reviewed and illustrated through examples. Applications and the state-of-the-art in computations are also reviewed. Finally, we discuss several main areas for future development in this field. These include development of polynomial-time approximation schemes for multi-stage stochastic programs and the application of global optimization algorithms to two-stage and chance-constraint formulations.