Robust continuous linear programs
- PDF / 328,366 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 75 Downloads / 216 Views
Robust continuous linear programs Archis Ghate1 Received: 6 October 2019 / Accepted: 23 January 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Continuous linear programs (CLPs) arise in applications such as production/economic planning, continuous-time network flow problems, fluid relaxations of multiclass queueing networks, and control. To the best of the author’s knowledge, this paper proposes the first robust optimization framework for CLPs. The main result of the paper is that the robust counterpart of a CLP is also a CLP. Thus, any computational method for the original problem can be applied to the robust problem. For instance, a recent polynomial-time approximation algorithm applies. Further, if the original problem possesses a so-called separable structure, then the robust problem is also separable. Then existing Simplex-type and other discretization-based solution methods can be applied to the robust problem. The paper also provides a bound on the probability that an optimal solution to the robust counterpart violates a constraint in the original problem. Qualitative properties of this bound are discussed and compared with similar bounds for robust finite-dimensional linear programs. Keywords Infinite-dimensional optimization · Linear programming duality · Parametric uncertainty
1 Introduction Bellman [6] first studied a class of continuous linear programs (CLPs) called bottleneck problems. These were motivated by an economic/production planning application. The word “continuous” here refers to the fact that the variables are indexed by an attribute such as time that varies over an uncountable set as opposed to a countable set. Anderson [1] introduced a “separated” continuous LP (SCLP) model for job-shop scheduling. Roughly speaking, in SCLPs, constraints that include time-integrals of variables do not include instantaneous values of those variables, and vice versa. While exact solution of general CLPs is notoriously difficult, such separation of integral and instantaneous
B 1
Archis Ghate [email protected] University of Washington, Seattle, WA, USA
123
A. Ghate
constraints renders the problems a bit more amenable to analysis and algorithms. A majority of the literature therefore focuses on SCLPs. Pullan [22–27] developed duality theory and algorthms for SCLPs in a series of papers. Pullan’s algorithms were based on solving a sequence of discretizations. Philpott and Craddock [21] also proposed a discretization method for LPs on continuous-time networks. Fleischer and Sethuraman [12] developed a discretizationbased approximation scheme for SCLPs that arise from fluid relaxations of multiclass queueing networks. Luo and Bertsimas [19] combined quadratic programming methods with discretization to solve a more general class of problems called stateconstrained SCLPs. Anderson et al. [3] studied the structure of extreme points for SCLPs. Anderson and Philpott [4] utilized this structure to develop a Simplex-type algorithm for LPs on continuous-time networks without discretization.
Data Loading...