1,721,057 research outputs found
Finite Adaptability in Multistage Linear Optimization
No full textIn multistage problems, decisions are implemented sequentially, and thus may depend on past realizations of the uncertainty. Examples of such problems abound in applications of stochastic control and operations research; yet, where robust optimization has made great progress in providing a tractable formulation for a broad class of single-stage optimization problems with uncertainty, multistage problems present significant tractability challenges. In this paper we consider an adaptability model designed with discrete second stage variables in mind. We propose a hierarchy of increasing adaptability that bridges the gap between the static robust formulation, and the fully adaptable formulation. We study the geometry, complexity, formulations, algorithms, examples and computational results for finite adaptability. In contrast to the model of affine adaptability proposed in, our proposed framework can accommodate discrete variables. In terms of performance for continuous linear optimization, the two frameworks are complementary, in the sense that we provide examples that the proposed framework provides stronger solutions and vice versa. We prove a positive tractability result in the regime where we expect finite adaptability to perform well, and illustrate this claim with an application to Air Traffic Control.Lincoln LaboratoryNational Science Foundation (U.S.) (Grant EFRI-0735905)National Science Foundation (U.S.) (Grant CNS-0721532)National Science Foundation (U.S.) (Grant CNS-0831580)United States. Defense Threat Reduction Agency (Grant HDTRA1-08-0029
Optimizing over coherent risk measures and non-convexities: a robust mixed integer optimization approach
No full textRecently, coherent risk measure minimization was formulated as robust optimization and the correspondence between coherent risk measures and uncertainty sets of robust optimization was investigated. We study minimizing coherent risk measures under a norm equality constraint with the use of robust optimization formulation. Not only existing coherent risk measures but also a new coherent risk measure is investigated by setting a new uncertainty set. The norm equality constraint itself has a practical meaning or plays a role to prevent a meaningless solution, the zero vector, in the context of portfolio optimization or binary classification in machine learning, respectively. For such advantages, the convexity is sacrificed in the formulation. However, we show a condition for an input of our problem which guarantees that the nonconvex constraint is convexified without changing the optimality of the problem. If the input does not satisfy the condition, we propose to solve a mixed integer optimization problem by using the ℓ[subscript 1] or ℓ[subscript ∞]-norm. The numerical experiments show that our approach has good performance for portfolio optimization and binary classification and also imply its flexibility of modelling that makes it possible to deal with various coherent risk measures
A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization
No full textIn this paper, we study the performance of static solutions for two-stage adjustable robust linear optimization problems with uncertain constraint and objective coefficients and give a tight characterization of the adaptivity gap. Computing an optimal adjustable robust optimization problem is often intractable since it requires to compute a solution for all possible realizations of uncertain parameters (Feige et al. in Lect Notes Comput Sci 4513:439–453, 2007). On the other hand, a static solution is a single (here and now) solution that is feasible for all possible realizations of the uncertain parameters and can be computed efficiently for most dynamic optimization problems. We show that for a fairly general class of uncertainty sets, a static solution is optimal for the two-stage adjustable robust linear packing problems. This is highly surprising in view of the usual perception about the conservativeness of static solutions. Furthermore, when a static solution is not optimal for the adjustable robust problem, we give a tight approximation bound on the performance of the static solution that is related to a measure of non-convexity of a transformation of the uncertainty set. We also show that our bound is at least as good (and in many case significantly better) as the bound given by the symmetry of the uncertainty set (Bertsimas and Goyal in Math Methods Oper Res 77(3):323–343, 2013; Bertsimas et al. in Math Oper Res 36(1):24–54, 2011)
Multistage Air Traffic Flow Management under Capacity Uncertainty: A Robust and Adaptive Optimization Approach
Full text linkIn this paper, we study the first application of robust and adaptive optimization in the Air Traffic Flow Management (ATFM) problem. The existing models for network-wide ATFM assume deterministic capacity estimates across airports and sectors without taking into account the uncertainty in capacities induced by weather. We introduce a weather-front based approach to model the uncertainty inherent in airspace capacity estimates resulting from the impact of a small number of weather fronts moving across the National Airspace (NAS). The key advantage of our uncertainty set construction is the low-dimensionality (uncertainty in only two parameters govern the overall uncertainty set for each airspace element). We formulate the consequent ATFM problem under capacity uncertainty within the robust and adaptive optimization framework and propose tractable solution methodologies. Our theoretical contributions are as follows: i) we propose a polyhedral description of the convex hull of the discrete uncertainty set; ii) we prove the equivalence of the robust problem to a modified instance of the deterministic problem; and iii) we solve optimally the LP relaxation of the adaptive problem using piece-wise affine policies where the number of pieces in an optimal policy are governed by the number of extreme points in the uncertainty set. A particularly attractive feature is that for most practically encountered instances, an affine policy suffices to solve the adaptive problem optimally. Finally, we report empirical results from the proposed models on real world flight schedules augmented with simulated weather fronts that illuminate the merits of our proposal. The key insights from our computational results are: i) the robust problem inherits all the attractive properties of the deterministic problem (e.g., superior integrality properties and fast computational times); and ii) the price of robustness and adaptability is typically small.National Science Foundation (U.S.) (NSF Grant EFRI-0735905
Binary decision rules for multistage adaptive mixed-integer optimization
No full textDecision rules provide a flexible toolbox for solving computationally demanding, multistage adaptive optimization problems. There is a plethora of real-valued decision rules that are highly scalable and achieve good quality solutions. On the other hand, existing binary decision rule structures tend to produce good quality solutions at the expense of limited scalability and are typically confined to worst-case optimization problems. To address these issues, we first propose a linearly parameterised binary decision rule structure and derive the exact reformulation of the decision rule problem. In the cases where the resulting optimization problem grows exponentially with respect to the problem data, we provide a systematic methodology that trades-off scalability and optimality, resulting to practical binary decision rules. We also apply the proposed binary decision rules to the class of problems with random-recourse and show that they share similar complexity as the fixed-recourse problems. Our numerical results demonstrate the effectiveness of the proposed binary decision rules and show that they are (i) highly scalable and (ii) provide high quality solutions. Keywords: Adaptive optimization, Binary decision rules, Mixed-integer optimizatio
On the performance of affine policies for two-stage adaptive optimization: a geometric perspective
No full textWe consider two-stage adjustable robust linear optimization problems with uncertain right hand side b belonging to a convex and compact uncertainty set U. We provide an a priori approximation bound on the ratio of the optimal affine (in b) solution to the optimal adjustable solution that depends on two fundamental geometric properties of U: (a) the “symmetry” and (b) the “simplex dilation factor” of the uncertainty set U and provides deeper insight on the power of affine policies for this class of problems. The bound improves upon a priori bounds obtained for robust and affine policies proposed in the literature. We also find that the proposed a priori bound is quite close to a posteriori bounds computed in specific instances of an inventory control problem, illustrating that the proposed bound is informative
On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems
No full textWe consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right-hand side of the constraints is uncertain and belongs to a symmetric uncertainty set (such as hypercube, ellipsoid or norm ball) and the probability measure is also symmetric, then the cost of the optimal fixed solution to the corresponding robust problem is at most twice the optimal expected cost of the two-stage stochastic problem. Furthermore, we show that the bound is tight for symmetric uncertainty sets and can be arbitrarily large if the uncertainty set is not symmetric. We refer to the ratio of the optimal cost of the robust problem and the optimal cost of the two-stage stochastic problem as the stochasticity gap. We also extend the bound on the stochasticity gap for another class of uncertainty sets referred to as positive.
If both the objective coefficients and right-hand side are uncertain, we show that the stochasticity gap can be arbitrarily large even if the uncertainty set and the probability measure are both symmetric. However, we prove that the adaptability gap (ratio of optimal cost of the robust problem and the optimal cost of a two-stage fully adaptable problem) is at most four even if both the objective coefficients and the right-hand side of the constraints are uncertain and belong to a symmetric uncertainty set. The bound holds for the class of positive uncertainty sets as well. Moreover, if the uncertainty set is a hypercube (special case of a symmetric set), the adaptability gap is one under an even more general model of uncertainty where the constraint coefficients are also uncertain.National Science Foundation (U.S.) (NSF Grant DMI-0556106)National Science Foundation (U.S.) (NSF Grant EFRI-0735905
An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems
No full textOur interest lies in solving sum of squares (SOS) relaxations of large-scale unconstrained polynomial optimization problems. Because interior-point methods for solving these problems are severely limited by the large-scale, we are motivated to explore efficient implementations of an accelerated first-order method to solve this class of problems. By exploiting special structural properties of this problem class, we greatly reduce the computational cost of the first-order method at each iteration. We report promising computational results as well as a curious observation about the behaviour of the first-order method for the SOS relaxations of the unconstrained polynomial optimization problem.United States. Air Force Office of Scientific Research (Grant No. FA9550-08-1-0350)United States. Air Force Office of Scientific Research (AFOSR Grant No. FA9550-11-1-0141)Singapore-MIT Allianc
Least quantile regression via modern optimization
Full text linkWe address the Least Quantile of Squares (LQS) (and in particular the Least Median of Squares) regression problem using modern optimization methods. We propose a Mixed Integer Optimization (MIO) formulation of the LQS problem which allows us to find a provably global optimal solution for the LQS problem. Our MIO framework has the appealing characteristic that if we terminate the algorithm early, we obtain a solution with a guarantee on its sub-optimality. We also propose continuous optimization methods based on first-order subdifferential methods, sequential linear optimization and hybrid combinations of them to obtain near optimal solutions to the LQS problem. The MIO algorithm is found to benefit significantly from high quality solutions delivered by our continuous optimization based methods. We further show that the MIO approach leads to (a) an optimal solution for any dataset, where the data-points (y[subscript i],x[subscript i])’s are not necessarily in general position, (b) a simple proof of the breakdown point of the LQS objective value that holds for any dataset and (c) an extension to situations where there are polyhedral constraints on the regression coefficient vector. We report computational results with both synthetic and real-world datasets showing that the MIO algorithm with warm starts from the continuous optimization methods solve small (n = 100) and medium (n = 500) size problems to provable optimality in under two hours, and outperform all publicly available methods for large-scale (n = 10,000) LQS problems
Design of Near Optimal Decision Rules in Multistage Adaptive Mixed-Integer Optimization
Full text linkIn recent years, decision rules have been established as the preferred solution method for addressing computationally demanding, multistage adaptive optimization problems. Despite their success, existing decision rules (a) are typically constrained by their a priori design and (b) do not incorporate in their modeling adaptive binary decisions. To address these problems, we first derive the structure for optimal decision rules involving continuous and binary variables as piecewise linear and piecewise constant functions, respectively. We then propose a methodology for the optimal design of such decision rules that have a finite number of pieces and solve the problem robustly using mixed-integer optimization. We demonstrate the effectiveness of the proposed methods in the context of two multistage inventory control problems. We provide global lower bounds and show that our approach is (i) practically tractable and (ii) provides high quality solutions that outperform alternative methods
- …
