Decomposition methods for Wasserstein-based data-driven distributionally robust problems

We study decomposition methods for two-stage data-driven Wasserstein-based DROs with right-hand-sided uncertainty and rectangular support. We propose a novel finite reformulation that explores the rectangular uncertainty support to develop and test five new different decomposition schemes: Column-Constraint Generation, Single-cut and Multi-cut Benders, as well as Regularized Single-cut and Multi-cut Benders. We compare the efficiency of the proposed methods for a unit commitment problem with 14 and 54 thermal generators whose uncertainty vector differs from a 24 to 240-dimensional array.     

Using the WOWA operator in robust discrete optimization problems

In this paper a class of discrete optimization problems with uncertain costs is discussed. The uncertainty is modeled by introducing a scenario set containing a finite number of cost scenarios. A probability distribution over the set of scenarios is available. In order to choose a solution the weighted OWA criterion (WOWA) is applied. This criterion allows decision makers to take into account both probabilities for scenarios and the degree of pessimism/optimism. In this paper the complexity of the considered class of discrete optimization problems is described and some exact and approximation algorithms for solving it are proposed. Applications to the selection and the assignment problems, together with results of computational tests are shown.     

On robust optimization of two-stage systems

Robust-optimization models belong to a special class of stochastic programs, where the traditional expected cost minimization objective is replaced by one that explicitly addresses cost variability. This paper explores robust optimization in the context of two-stage planning systems. We show that, under arbitrary measures for variability, the robust optimization approach might lead to suboptimal solutions to the second-stage planning problem. As a result, the variability of the second-stage costs may be underestimated, thereby defeating the intended purpose of the model. We propose sufficient conditions on the variability measure to remedy this problem. Under the proposed conditions, a robust optimization model can be efficiently solved using a variant of the L-shaped decomposition algorithm for traditional stochastic linear programs. We apply the proposed framework to standard stochastic-programming test problems and to an application that arises in auctioning excess electric power. Mathematics Subject Classification (1991):90C15, 90C33, 90B50, 90A09, 90A43Supported in part by NSF Grants DMI-0099726 and DMI-0133943     

A two-stage fuzzy robust integer programming approach for capacity planning of environmental management systems

In this study, a two-stage fuzzy robust integer programming (TFRIP) method has been developed for planning environmental management systems under uncertainty. This approach integrates techniques of robust programming and two-stage stochastic programming within a mixed integer linear programming framework. It can facilitate dynamic analysis of capacity-expansion planning for waste management facilities within a multi-stage context. In the modeling formulation, uncertainties can be presented in terms of both possibilistic and probabilistic distributions, such that robustness of the optimization process could be enhanced. In its solution process, the fuzzy decision space is delimited into a more robust one by specifying the uncertainties through dimensional enlargement of the original fuzzy constraints. The TFRIP method is applied to a case study of long-term waste-management planning under uncertainty. The generated solutions for continuous and binary variables can provide desired waste-flow-allocation and capacity-expansion plans with a minimized system cost and a maximized system feasibility.     

Efficient Kriging-based robust optimization of unconstrained problems

A novel methodology, based on Kriging and expected improvement, is proposed for applying robust optimization on unconstrained problems affected by implementation error. A modified expected improvement measure which reflects the need for robust instead of nominal optimization is used to provide new sampling point locations. A new sample is added at each iteration by finding the location at which the modified expected improvement measure is maximum. By means of this process, the algorithm iteratively progresses towards the robust optimum. It is demonstrated that the algorithm performs significantly better than current techniques for robust optimization using response surface modeling.     

An inexact bundle variant suited to column generation

We give a bundle method for constrained convex optimization. Instead of using penalty functions, it shifts iterates towards feasibility, by way of a Slater point, assumed to be known. Besides, the method accepts an oracle delivering function and subgradient values with unknown accuracy. Our approach is motivated by a number of applications in column generation, in which constraints are positively homogeneous—so that zero is a natural Slater point—and an exact oracle may be time consuming. Finally, our convergence analysis employs arguments which have been little used so far in the bundle community. The method is illustrated on a number of cutting-stock problems. Research supported by INRIA New Investigation Grant “Convex Optimization and Dantzig–Wolfe Decomposition”.     

An algorithm to solve polyhedral convex set optimization problems

An algorithm which computes a solution of a set optimization problem is provided. The graph of the objective map is assumed to be given by finitely many linear inequalities. A solution is understood to be a set of points in the domain satisfying two conditions: the attainment of the infimum and minimality with respect to a set relation. In the first phase of the algorithm, a linear vector optimization problem, called the vectorial relaxation, is solved. The resulting pre-solution yields the attainment of the infimum but, in general, not minimality. In the second phase of the algorithm, minimality is established by solving certain linear programs in combination with vertex enumeration of some values of the objective map.     

A robust optimization model for multi-product two-stage capacitated production planning under uncertainty

Production planning (PP) is one of the most important issues carried out in manufacturing environments which seeks efficient planning, scheduling and coordination of all production activities that optimizes the company’s objectives. In this paper, we studied a two-stage real world capacitated production system with lead time and setup decisions in which some parameters such as production costs and customer demand are uncertain. A robust optimization model is developed to formulate the problem in which minimization of the total costs including the setup costs, production costs, labor costs, inventory costs, and workforce changing costs is considered as performance measure. The robust approach is used to reduce the effects of fluctuations of the uncertain parameters with regards to all the possible future scenarios. A mixed-integer programming (MIP) model is developed to formulate the related robust production planning problem. In fact the robust proposed model is presented to generate an initial robust schedule. The performance of this schedule could be improved against of any possible occurrences of uncertain parameters. A case from an Iran refrigerator factory is studied and the characteristics of factory and its products are discussed. The computational results display the robustness and effectiveness of the model and highlight the importance of using robust optimization approach in generating more robust production plans in the uncertain environments. The tradeoff between solution robustness and model robustness is also analyzed.     

How to solve a semi-infinite optimization problem

After an introduction to main ideas of semi-infinite optimization, this article surveys recent developments in theory and numerical methods for standard and generalized semi-infinite optimization problems. Particular attention is paid to connections with mathematical programs with complementarity constraints, lower level Wolfe duality, semi-smooth approaches, as well as branch and bound techniques in adaptive convexification procedures. A section on recent genericity results includes a discussion of the symmetry effect in generalized semi-infinite optimization.     

A discussion on the conservatism of robust linear optimization problems

In 2004, Bertsimas and Sim proposed a robust approach that can control the degree of conservatism by applying a limitation Γ to the maximum number of parameters that are allowed to change. However, the robust approach can become extremely conservative even when Γ is relatively small. In this paper, we provide a theoretical analysis to explain why this extreme conservatism occurs. We further point out that the robust approach does not reach an extremely conservative state when Γ is less than k, where k is the number of nonzero components of the optimal solution of the extremely conservative robust approach. This research also shows that care must be taken when adjusting the value of Γ to control the degree of conservatism because the approach may result in greater conservatism than was intended. We subsequently apply our analysis to additive combinatorial optimization problems. Finally, we illustrate our results on numerical simulations.     

A robust robust optimization result

We study the loss in objective value when an inaccurate objective is optimized instead of the true one, and show that “on average” this loss is very small, for an arbitrary compact feasible region.     

Note: An algorithm to solve polyhedral convex set optimization problems

We provide a counterexample to the remark in Löhne and Schrage [An algorithm to solve polyhedral convex set optimization problems, Optimization 62 (2013), pp. 131-141] that every solution of a polyhedral convex set optimization problem is a pre-solution. A correct statement is that every solution of a polyhedral convex set optimization problem obtained by the algorithm SetOpt is a pre-solution. We also show that every finite infimizer and hence every solution of a polyhedral convex set optimization problem contains a pre-solution.     

An active set method for solving linearly constrained nonsmooth optimization problems

An algorithm for solving linearly constrained optimization problems is proposed. The search direction is computed by a bundle principle and the constraints are treated through an active set strategy. Difficulties that arise when the objective function is nonsmooth, require a clever choice of a constraint to relax. A certain nondegeneracy assumption is necessary to obtain convergence. Most of this research was performed when the author was with I.N.R.I.A. (Domaine de Voluceau-Rocquencourt, B.P. 105, 78153 Le Chesnay Cédex, France). This research was supported in part by the National Science Foundation, Grants No. DMC-84-51515 and OIR-85-00108.     

Recent advances in robust optimization: An overview

This paper provides an overview of developments in robust optimization since 2007. It seeks to give a representative picture of the research topics most explored in recent years, highlight common themes in the investigations of independent research teams and highlight the contributions of rising as well as established researchers both to the theory of robust optimization and its practice. With respect to the theory of robust optimization, this paper reviews recent results on the cases without and with recourse, i.e., the static and dynamic settings, as well as the connection with stochastic optimization and risk theory, the concept of distributionally robust optimization, and findings in robust nonlinear optimization. With respect to the practice of robust optimization, we consider a broad spectrum of applications, in particular inventory and logistics, finance, revenue management, but also queueing networks, machine learning, energy systems and the public good. Key developments in the period from 2007 to present include: (i) an extensive body of work on robust decision-making under uncertainty with uncertain distributions, i.e., “robustifying” stochastic optimization, (ii) a greater connection with decision sciences by linking uncertainty sets to risk theory, (iii) further results on nonlinear optimization and sequential decision-making and (iv) besides more work on established families of examples such as robust inventory and revenue management, the addition to the robust optimization literature of new application areas, especially energy systems and the public good.     

Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems

Semidefinite relaxations of certain combinatorial optimization problems lead to approximation algorithms with performance guarantees. For large-scale problems, it may not be computationally feasible to solve the semidefinite relaxations to optimality. In this paper, we investigate the effect on the performance guarantees of an approximate solution to the semidefinite relaxation for MaxCut, Max2Sat, and Max3Sat. We show that it is possible to make simple modifications to the approximate solutions and obtain performance guarantees that depend linearly on the most negative eigenvalue of the approximate solution, the size of the problem, and the duality gap. In every case, we recover the original performance guarantees in the limit as the solution approaches the optimal solution to the semidefinite relaxation.     

Ambiguous chance constrained problems and robust optimization

In this paper we study ambiguous chance constrained problems where the distributions of the random parameters in the problem are themselves uncertain. We focus primarily on the special case where the uncertainty set of the distributions is of the form where ρ_p denotes the Prohorov metric. The ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according to the central measure The main contribution of this paper is to show that the robust sampled problem is a good approximation for the ambiguous chance constrained problem with a high probability. This result is established using the Strassen-Dudley Representation Theorem that states that when the distributions of two random variables are close in the Prohorov metric one can construct a coupling of the random variables such that the samples are close with a high probability. We also show that the robust sampled problem can be solved efficiently both in theory and in practice. Research partially supported by NSF grant CCR-00-09972. Research partially supported by NSF grants CCR-00-09972, DMS-01-04282, and ONR grant N000140310514.     

A robust optimization approach to wine grape harvesting scheduling

Optimization models are increasingly being used in agricultural planning. However, the inherent uncertainties present in agriculture make it difficult. In recent years, robust optimization has emerged as a methodology that allows dealing with uncertainty in optimization models, even when probabilistic knowledge of the phenomenon is incomplete. In this paper, we consider a wine grape harvesting scheduling optimization problem subject to several uncertainties, such as the actual productivity that can be achieved when harvesting. We study how effective robust optimization is solving this problem in practice. We develop alternative robust models and show results for some test problems obtained from actual wine industry problems.     

Distributionally robust discrete optimization with Entropic Value-at-Risk

We study the discrete optimization problem under the distributionally robust framework. We optimize the Entropic Value-at-Risk, which is a coherent risk measure and is also known as Bernstein approximation for the chance constraint. We propose an efficient approximation algorithm to resolve the problem via solving a sequence of nominal problems. The computational results show that the number of nominal problems required to be solved is small under various distributional information sets.     

Efficient robust optimization for robust control with constraints

This paper proposes an efficient computational technique for the optimal control of linear discrete-time systems subject to bounded disturbances with mixed linear constraints on the states and inputs. The problem of computing an optimal state feedback control policy, given the current state, is non-convex. A recent breakthrough has been the application of robust optimization techniques to reparameterize this problem as a convex program. While the reparameterized problem is theoretically tractable, the number of variables is quadratic in the number of stages or horizon length N and has no apparent exploitable structure, leading to computational time of per iteration of an interior-point method. We focus on the case when the disturbance set is ∞-norm bounded or the linear map of a hypercube, and the cost function involves the minimization of a quadratic cost. Here we make use of state variables to regain a sparse problem structure that is related to the structure of the original problem, that is, the policy optimization problem may be decomposed into a set of coupled finite horizon control problems. This decomposition can then be formulated as a highly structured quadratic program, solvable by primal-dual interior-point methods in which each iteration requires time. This cubic iteration time can be guaranteed using a Riccati-based block factorization technique, which is standard in discrete-time optimal control. Numerical results are presented, using a standard sparse primal-dual interior point solver, that illustrate the efficiency of this approach.     

可分离凸优化问题的非精确平行分裂算法

针对一类可分离凸优化问题提出了一种非精确平行分裂算法.该算法充分利用了所求解问题的可分离结构,并对子问题进行非精确求解.在适当的条件下,证明了所提出的非精确平行分裂算法的全局收敛性,初步的数值实验说明了算法有效性.