Search

The classic pump scheduling or optimal water flow (OWF) problem for water distribution networks (WDNs) minimizes the cost of power consumption for a given WDN over a fixed time horizon. In its exact form, the OWF is a computationally challenging mixed-integer nonlinear program (MINLP). It is complicated by nonlinear equality constraints that model network physics, discrete variables that model operational controls, and intertemporal constraints that model changes to storage devices. To address the computational challenges of the OWF, this paper develops tight polyhedral relaxations of the original MINLP, derives novel valid inequalities (or cuts) using duality theory, and implements novel optimization-based bound tightening and cut generation procedures. The efficacy of each new method is rigorously evaluated by measuring empirical improvements in OWF primal and dual bounds over 45 literature instances. The evaluation suggests that our relaxation improvements, model strengthening techniques, and a thoughtfully selected polyhedral relaxation partitioning scheme can substantially improve OWF primal and dual bounds, especially when compared with similar relaxation-based techniques that do not leverage these new methods. History: Accepted by David Alderson, Area Editor for Network Optimization: Algorithms & Applications. Funding: This work was supported by the U.S. Department of Energy (DOE) Advanced Grid Modeling project, Coordinated Planning and Operation of Water and Power Infrastructures for Increased Resilience and Reliability. Incorporation of the PolyhedralRelaxations Julia package was supported by Los Alamos National Laboratory's Directed Research and Development program under the project Fast, Linear Programming-Based Algorithms with Solution Quality Guarantees for Nonlinear Optimal Control Problems [Grant 20220006ER]. All work at Los Alamos National Laboratory was conducted under the auspices of the National Nuclear Security Administration of the U.S. DOE, Contract No. 89233218CNA000001. This work was also authored in part by the National Renewable Energy Laboratory, operated by the Alliance for Sustainable Energy, LLC, for the U.S. DOE, Contract No. DE-AC36-08GO28308. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0233) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0233). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Recent increases in gas-fired power generation have engendered increased interdependencies between natural gas and power transmission systems. These interdependencies have amplified existing vulnerabilities in gas and power grids, where disruptions can require the curtailment of load in one or both systems. Although typically operated independently, coordination of these systems during severe disruptions can allow for targeted delivery to lifeline services, including gas delivery for residential heating and power delivery for critical facilities. To address the challenge of estimating maximum joint network capacities under such disruptions, we consider the task of determining feasible steady-state operating points for severely damaged systems while ensuring the maximal delivery of gas and power loads simultaneously, represented mathematically as the nonconvex joint Maximal Load Delivery (MLD) problem. To increase its tractability, we present a mixed-integer convex relaxation of the MLD problem. Then, to demonstrate the relaxation's effectiveness in determining bounds on network capacities, exact and relaxed MLD formulations are compared across various multi-contingency scenarios on nine joint networks ranging in size from 25 to 1191 nodes. The relaxation-based methodology is observed to accurately and efficiently estimate the impacts of severe joint network disruptions, often converging to the relaxed MLD problem's globally optimal solution within ten seconds. [ABSTRACT FROM AUTHOR]

In recent years, there has been an increasing need to understand the complex interdependencies between critical infrastructure systems, for example, electric power, natural gas, and potable water. Whereas open-source and commercial tools for the independent simulation of these systems are well established, frameworks for cosimulation with other systems are nascent and tools for co-optimization are scarce—the major challenge being the hidden combinatorics that arise when connecting multiple-infrastructure system models. Building toward a comprehensive solution for modeling interdependent infrastructure systems, this work presents InfrastructureModels, an extensible, open-source mathematical programming framework for co-optimizing multiple interdependent infrastructures. This work provides new insights into methods and programming abstractions that make state-of-the-art independent infrastructure models composable with minimal additional effort. To that end, this paper presents the design of the InfrastructureModels framework, documents key components of the software's implementation, and demonstrates its effectiveness with three case studies on canonical co-optimization tasks arising in interdependent infrastructure systems. History: Accepted by Ted Ralphs, Area Editor for Software Tools. Funding: The work was funded by Los Alamos National Laboratory's Directed Research and Development project "The Optimization of Machine Learning: Imposing Requirements on Artificial Intelligence" and the U.S. Department of Energy's Office of Electricity Advanced Grid Modeling projects "Joint Power System and Natural Gas Pipeline Optimal Expansion Planning" and "Coordinated Planning and Operation of Water and Power Infrastructures for Increased Resilience and Reliability." This work was carried out under the U.S. DOE contract no. [DE-AC52-06NA25396]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0118) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0118). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Around the globe, electric power networks are transforming into complex cyber–physical energy systems (CPES) due to the accelerating integration of both information and communication technologies (ICT) and distributed energy resources. While this integration improves power grid operations, the growing number of Internet-of-Things (IoT) controllers and high-wattage appliances being connected to the electric grid is creating new attack vectors, largely inherited from the IoT ecosystem, that could lead to disruptions and potentially energy market manipulation via coordinated load-altering attacks (LAAs). In this article, we explore the feasibility and effects of a realistic LAA targeted at IoT high-wattage loads connected at the distribution system level, designed to manipulate local energy markets and perform energy storage (ES) arbitrage. Realistic integrated transmission and distribution (T&D) systems are used to demonstrate the effects that LAAs have on locational marginal prices at the transmission level and in distribution systems adjacent to the targeted network. [ABSTRACT FROM AUTHOR]

Severe geomagnetic disturbances (GMDs) increase the magnitude of the electric field on the Earth’s surface (E-field) and drive geomagnetically-induced currents (GICs) along the transmission lines in electric grids. These additional currents can pose severe risks, such as current distortions, transformer saturation and increased reactive power losses, each of which can lead to system unreliability. Several mitigation actions (e.g., changing grid topology) exist that can reduce the harmful GIC effects on the grids. Making such decisions can be challenging, however, because the magnitude and direction of the E-field are uncertain and non-stationary. In this paper, we model uncertain E-fields using the distributionally robust optimization (DRO) approach that determines optimal transmission grid operations such that the worst-case expectation of the system cost is minimized. We also capture the effect of GICs on the nonlinear AC power flow equations. For solution approaches, we develop an accelerated column-and-constraint generation (CCG) algorithm by exploiting a special structure of the support set of uncertain parameters representing the E-field. Extensive numerical experiments based on “epri-21” and “uiuc-150” systems, designed for GMD studies, demonstrate (i) the computational performance of the accelerated CCG algorithm, (ii) the superior performance of distributionally robust grid operations that satisfy nonlinear, nonconvex AC power flow equations and GIC constraints, in comparison with standard stochastic programming-based methods during the out-of-sample testing. [ABSTRACT FROM AUTHOR]

We formulate a nonlinear optimal control problem for intraday operation of a natural gas pipeline network that includes storage reservoirs. The dynamics of compressible gas flow through pipes, compressors, reservoirs, and wells are considered. In particular, a reservoir is modeled as a rigid, hollow container that stores gas under isothermal conditions and uniform density, and a well is modeled as a vertical pipe. For each pipe, flow dynamics are described by a coupled partial differential equation (PDE) system in density and mass flux variables, with momentum dissipation modeled using the Darcy–Wiesbach friction approximation. Compressors are modeled as scaling up the pressure of gas between the inlet and outlet. The governing equations for all network components are spatially discretized and assembled into a nonlinear differential-algebraic equation (DAE) system, which synthesizes above-ground pipeline and subsurface reservoir dynamics into a single reduced-order model. We seek to maximize an objective function that quantifies economic profit and network efficiency subject to the flow equations and inequalities that represent operating limitations. The problem is solved using a primal–dual interior point solver, and the solutions are validated in computational experiments and simulations on several pipeline test networks to demonstrate the effectiveness of the proposed methodology. [ABSTRACT FROM AUTHOR]

The majority of overland transport needs for crude petroleum and refined petroleum products are met using pipelines. Numerous studies have developed optimization methods for design of these systems in order to minimize construction costs while meeting capacity requirements. Here, we formulate problems to optimize the operations of existing single liquid commodity pipeline systems subject to physical flow and pump engineering constraints. The objectives are to maximize the economic value created for users of the system and to minimize operating costs. We present a general computational method for this class of continuous, non‐convex nonlinear programs, and examine the use of pump operating settings and flow allocations as decision variables. The approach is applied to compute optimal operating regimes and perform engineering economic sensitivity analyses for a case study of a crude oil pipeline developed using publicly available data. [ABSTRACT FROM AUTHOR]

Distributed generation and remotely controlled switches have emerged as important technologies to improve the resiliency of distribution grids against extreme weather-related disturbances. Therefore it becomes important to study how best to place them on the grid in order to meet a resiliency criteria, while minimizing costs and capturing their dependencies on the associated communication systems that sustain their distributed operations. This paper introduces the Optimal Resilient Design Problem for Distribution and Communication Systems (ORDPDC) to address this need. The ORDPDC is formulated as a two-stage stochastic mixed-integer program that captures the physical laws of distribution systems, the communication connectivity of the smart grid components, and a set of scenarios that specifies which components are affected by potential disasters. The paper proposes an exact branch-and-price algorithm for the ORDPDC that features a strong lower bound and a variety of acceleration schemes to address degeneracy. The ORDPDC model and branch-and-price algorithm were evaluated on a variety of test cases with varying disaster intensities and network topologies. The results demonstrate the significant impact of the network topologies on the expansion plans and costs, as well as the computational benefits of the proposed approach. [ABSTRACT FROM AUTHOR]

In this work, we develop an adaptive, multivariate partitioning algorithm for solving nonconvex, Mixed-Integer Nonlinear Programs (MINLPs) with polynomial functions to global optimality. In particular, we present an iterative algorithm that exploits piecewise, convex relaxation approaches via disjunctive formulations to solve MINLPs that is different than conventional spatial branch-and-bound approaches. The algorithm partitions the domains of variables in an adaptive and non-uniform manner at every iteration to focus on productive areas of the search space. Furthermore, domain reduction techniques based on sequential, optimization-based bound-tightening and piecewise relaxation techniques, as a part of a presolve step, are integrated into the main algorithm. Finally, we demonstrate the effectiveness of the algorithm on well-known benchmark problems (including Pooling and Blending instances) from MINLPLib and compare our algorithm with state-of-the-art global optimization solvers. With our novel approach, we solve several large-scale instances, some of which are not solvable by state-of-the-art solvers. We also succeed in reducing the best known optimality gap for a hard, generalized pooling problem instance. [ABSTRACT FROM AUTHOR]

This work considers the task of finding an ac-feasible operating point of a severely damaged transmission network while ensuring that a maximal amount of active power loads can be delivered. This AC maximal load delivery (AC-MLD) task is a nonconvex nonlinear optimization problem that is incredibly challenging to solve on large-scale transmission system data sets. This work demonstrates that convex relaxations of the AC-MLD problem provide a reliable and scalable method for finding high-quality bounds on the amount of active power that can be delivered in the AC-MLD problem. To demonstrate their effectiveness, the solution methods proposed in this work are rigorously evaluated on 1000 $N$ - $k$ scenarios on seven power networks ranging in size from 70 to 6000 buses. The most effective relaxation of the AC-MLD problem converges in less than 20 seconds on commodity computing hardware for all 7000 of the scenarios considered. [ABSTRACT FROM AUTHOR]

The dynamics of flooding are primarily influenced by the shape, height, and roughness (friction) of the underlying topography. For this reason, mechanisms to mitigate floods frequently employ structural measures that either modify topographic elevation, for example, through the placement of levees and sandbags, or increase roughness, for example, through revegetation projects. However, the configuration of these measures is typically decided in an ad hoc manner, limiting their overall effectiveness. The advent of high‐performance surface‐water modeling software and improvements in black‐box optimization suggest that a more principled design methodology may be possible. This paper proposes a new computational approach to the problem of designing structural mitigation strategies under physical and budgetary constraints. It presents the development of a problem discretization amenable to simulation‐based, derivative‐free optimization. However, meta‐heuristics alone are found to be insufficient for obtaining quality solutions in a reasonable amount of time. As a result, this paper proposes novel numerical and physics‐based procedures to improve convergence to a high‐quality mitigation. The efficiency of the approach is demonstrated on hypothetical dam break scenarios of varying complexity under various mitigation budget constraints. In particular, experimental results show that, on average, the final proposed algorithm results in a 65% improvement in solution quality compared to a direct implementation. Key Points: The structural optimal flood mitigation problem is introducedA problem discretization amenable to derivative-free optimization is developedBenefits of constraining the problem with additional physics-based restrictions are shown [ABSTRACT FROM AUTHOR]

The growing dependence of electric power systems on gas-fired generators to balance fluctuating and intermittent production by renewable energy sources has increased the variation and volume of flows withdrawn from natural gas transmission pipelines. Adapting pipeline operations to maintain efficiency and security under these dynamic conditions requires optimization methods that account for substantial intraday transients and can rapidly compute solutions in reaction to generator re-dispatch. Here, we present a computationally efficient method for minimizing gas compression costs under dynamic conditions where deliveries to customers are described by time-dependent mass flows. The optimization method uses a simplified representation of gas flow physics, provides a choice of discretization schemes in time and space, and exploits a two-stage approach to minimize energy costs and ensure smooth and physically meaningful solutions. The resulting large-scale NLPs are solved using an interior point method. The optimization scheme is validated by comparing the solutions with an integration of the dynamic equations using an adaptive timestepping differential equation solver, as well as a different, recently proposed optimal control scheme. The comparison shows that solutions to the discretized problem are feasible for the continuous problem and also practical from an operational standpoint. The results also indicate that our scheme produces at least an order of magnitude reduction in computation time relative to the state of the art and scales to large gas transmission networks with more than 6,000 kilometers of total pipeline. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0821. [ABSTRACT FROM AUTHOR]

Generalizing both mixed-integer linear optimization and convex optimization, mixed-integer convex optimization possesses broad modeling power but has seen relatively few advances in general-purpose solvers in recent years. In this paper, we intend to provide a broadly accessible introduction to our recent work in developing algorithms and software for this problem class. Our approach is based on constructing polyhedral outer approximations of the convex constraints, resulting in a global solution by solving a finite number of mixed-integer linear and continuous convex subproblems. The key advance we present is to strengthen the polyhedral approximations by constructing them in a higher-dimensional space. In order to automate this extended formulation we rely on the algebraic modeling technique of disciplined convex programming (DCP), and for generality and ease of implementation we use conic representations of the convex constraints. Although our framework requires a manual translation of existing models into DCP form, after performing this transformation on the MINLPLIB2 benchmark library we were able to solve a number of unsolved instances and on many other instances achieve superior performance compared with state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro. [ABSTRACT FROM AUTHOR]

In recent years, there have been increasing concerns about how geomagnetic disturbances (GMDs) impact electrical power systems. Geomagnetically induced currents (GICs) can saturate transformers, induce hot spot heating, and increase reactive power losses. These effects can potentially cause catastrophic damage to transformers and severely impact the ability of a power system to deliver power. To address this problem, we develop a model of GIC impacts to power systems that includes 1) GIC thermal capacity of transformers as a function of normal alternating current (AC), and 2) reactive power losses as a function of GIC. We use this model to derive an optimization problem that protects power systems from GIC impacts through line switching, generator redispatch, and load shedding. We employ state-of-the-art convex relaxations of AC power flow equations to lower bound the objective. We demonstrate the approach on a modified RTS96 system and the UIUC 150-bus system and show that line switching is an effective means to mitigate GIC impacts. We also provide a sensitivity analysis of optimal switching decisions with respect to GMD direction. [ABSTRACT FROM PUBLISHER]

Energy supply in rural and off-grid communities has traditionally relied on diesel-based microgrids, due to limited access. But global environmental concerns are pushing for the transformation of these systems into renewable-based microgrids. This transition to more complex systems with a mix of dispatchable and nondispatchable resources requires new planning tools that ensure the security of supply. This paper presents a novel mixed-integer linear optimization model that determines optimal technology mix, size, placement, and associated dispatch for a multi-energy microgrid. The model satisfies microgrid's electrical and heat transfer network limitations by integrating linear power flow and heat transfer equations. It captures the efficiency gains from waste heat recovery through combined heat and power technologies, by modeling the interplay between electrical and heat sources. To ensure a secure design against generator outages, the optimization maintains sufficient reserve capacity in the system, which is dynamically allocated based on system operating conditions. Several case studies on an isolated microgrid model, developed based on a real microgrid in Alaska, illustrate how the proposed model works. The results show the effectiveness of the model and are used to discuss various aspects of the optimization solution. [ABSTRACT FROM PUBLISHER]

This article considers a probabilistic generalization of the N‐k failure‐identification problem in power transmission networks, where the probability of failure of each component in the network is known a priori and the goal of the problem is to find a set of k components that maximizes disruption to the system loads weighted by the probability of simultaneous failure of the k components. The resulting problem is formulated as a bilevel mixed‐integer nonlinear program. Convex relaxations, linear approximations, and heuristics are developed to obtain feasible solutions that are close to the optimum. A general cutting‐plane algorithm is proposed to solve the convex relaxation and linear approximations of the N‐k problem. Extensive numerical results corroborate the effectiveness of the proposed algorithms on small‐, medium‐, and large‐scale test instances; the test instances include the IEEE 14‐bus system, the IEEE single‐area and three‐area RTS96 systems, the IEEE 118‐bus system, the WECC 240‐bus test system, the 1354‐bus PEGASE system, and the 2383‐bus Polish winter‐peak test system. [ABSTRACT FROM AUTHOR]

This paper introduces a statistical classifier that quickly locates line outages in a power system utilizing only time series phasor measurement data sampled during the system's transient response to the outage. The presented classifier is a linear multinomial regression model that is trained by solving a maximum likelihood optimization problem using synthetic data. The synthetic data is produced through dynamic simulations which are initialized by random samples of a forecast load/generation distribution. Real time computation of the proposed classifier is minimal and therefore the classifier is capable of locating a line outage before steady state is reached, allowing for quick corrective action in response to an outage. In addition, the output of the classifier fits into a statistical framework that is easily accessible. Specific line outages are identified as being difficult to localize and future improvements to the classifier are proposed. [ABSTRACT FROM PUBLISHER]

Despite their potential catastrophic impact, transients are often ignored or presented ad hoc when designing water distribution systems. To address this problem, we introduce a new piece-wise function fitting model that is integrated with mixed integer programming to optimally place and size surge tanks for transient control. The key features of the algorithm are a model-driven discretization of the search space, a linear approximation nonsmooth system response surface to transients, and a mixed integer linear programming optimization. Results indicate that high quality solutions can be obtained within a reasonable number of function evaluations and demonstrate the computational effectiveness of the approach through two case studies. The work investigates one type of surge control devices (closed surge tank) for a specified set of transient events. The performance of the algorithm relies on the assumption that there exists a smooth relationship between the objective function and tank size. Results indicate the potential of the approach for the optimal surge control design in water systems. [ABSTRACT FROM AUTHOR]

Phasor measurement units (PMUs) are increasingly important for monitoring the state of an electrical power grid and quickly detecting topology changes caused by events such as lines going down or large loads being dropped. Phasors are complex-valued measurements of voltage and current at various points of generation and consumption. If a line goes down or a load is removed, power flows change throughout the grid according to known physical laws, and the probability distribution of phasor measurements changes accordingly. This paper develops a method to estimate the current topology of a power grid from phasor measurements and considers the design goal of placing PMUs at strategic points in a distribution system to achieve good sensitivity to single-line outages. From a vector of phasor measurements, probabilities are computed corresponding to the scenario that all power lines are operational and to alternate scenarios in which each line goes down individually. These probabilities are functions of the joint distributions of phasor measurements under each possible scenario, obtained through Monte Carlo simulations with random load profiles. We use log-spline densities to estimate marginal distributions of phasor measurements and fold these into a multivariate Gaussian copula to capture important correlations. Sensitivity to outages varies according to which line goes down and where PMUs are placed on the grid. A greedy search algorithm is demonstrated for placing PMUs at locations that provide good sensitivity to single-line outages. Published 2014. This article is a U.S. Government work and is in the public domain in the USA. [ABSTRACT FROM AUTHOR]

Recent years have seen increased interest in the design and deployment of smart grid devices and control algorithms. Each of these smart communicating devices represents a potential access point for an intruder spurring research into intruder prevention and detection. However, no security measures are complete, and intruding attackers will compromise smart grid devices leading to the attacker and the system operator interacting via the grid and its control systems. The outcome of these machine-mediated human-human interactions will depend on the design of the physical and control systems mediating the interactions. If these outcomes can be predicted via simulation, they can be used as a tool for designing attack-resilient grids and control systems. However, accurate predictions require good models of not just the physical and control systems, but also of the human decision making. In this manuscript, we present an approach to develop such tools, i.e., models of the decisions of the cyber-physical intruder who is attacking the systems and the system operator who is defending it, and demonstrate its usefulness for design. [ABSTRACT FROM PUBLISHER]

Power grid operators decide where and how much power to generate based on the current topology and demands of the network. The topology can change as safety devices trigger (connecting or disconnecting parts of the network) or as lines go down. Often, the operator cannot observe these events directly, but instead has contemporary measurements and historical information about a subset of the line flows and bus (node) properties. This information can be used in conjunction with a computational model to infer the topology of the network. We present a Bayesian approach to topological inference that considers a bank of possible topologies. The solution provides a probability for each member in the model bank. The approach has two important features. First, we build a statistical approximation, or emulator, to the computational model, which is too computationally expensive to run a large number of times. Second, we use the emulator in an importance sampling scheme to estimate the probabilities. The resulting algorithm is fast enough to use in real time and very accurate. This article has online supplementary materials. [ABSTRACT FROM AUTHOR]

NMDA-type glutamate receptors mediate both trophic and excitotoxic signalling in CNS neurons. We have previously shown that blocking NMDAR- post-synaptic density-95 ( PSD95) interactions provides significant protection from excitotoxicity and in vivo ischaemia; however, the mechanism of neuroprotection is unclear. Here, we report that blocking PSD-95 interactions with the Tat- NR2B9c peptide enhances a Ca2 + -dependent protective pathway converging on cAMP Response Element binding protein ( CREB) activation. We provide evidence that Tat- NR2B9c neuroprotection from oxygen glucose deprivation and NMDA toxicity occurs in parallel with the activation of calmodulin kinase signalling and is dependent on a sustained phosphorylation of the CREB transcription factor and its activator Ca MKIV. Tat- NR2B9c-dependent neuroprotection and CREB phosphorylation are blocked by coapplication of CaM kinase ( KN93 and STO-609) or CREB ( KG-501) inhibitors, and by si RNA knockdown of Ca MKIV. These results are mirrored in vivo in a rat model of permanent focal ischaemia. Tat- NR2B9c application significantly reduces infarct size and causes a selective and sustained elevation in Ca MKIV phosphorylation; effects which are blocked by coadministration of KN93. Thus, calcium-dependent nuclear signalling via Ca MKIV and CREB is critical for neuroprotection via NMDAR- PSD95 blockade, both in vitro and in vivo. This study highlights the importance of maintaining neuronal function following ischaemic injury. Future stroke research should target neurotrophic and pro-survival signal pathways in the development of novel neuroprotective strategies. [ABSTRACT FROM AUTHOR]

This paper considers online stochastic combinatorial optimization problems where uncertainties, i.e., which requests come and when, are characterized by distributions that can be sampled and where time constraints severely limit the number of offline optimizations which can be performed at decision time and/or in between decisions. It proposes online stochastic algorithms that combine the frameworks of online and stochastic optimization. Online stochastic algorithms differ from traditional a priori methods such as stochastic programming and Markov Decision Processes by focusing on the instance data that is revealed over time. The paper proposes three main algorithms: expectation E, consensus C, and regret R. They all make online decisions by approximating, for each decision, the solution to a multi-stage stochastic program using an exterior sampling method and a polynomial number of samples. The algorithms were evaluated experimentally and theoretically. The experimental results were obtained on three applications of different nature: packet scheduling, multiple vehicle routing with time windows, and multiple vehicle dispatching. The theoretical results show that, under assumptions which seem to hold on these, and other, applications, algorithm E has an expected constant loss compared to the offline optimal solution. Algorithm R reduces the number of optimizations by a factor | R|, where R is the number of requests, and has an expected ρ(1+ o(1)) loss when the regret gives a ρ-approximation to the offline problem. [ABSTRACT FROM AUTHOR]

This paper considers online stochastic reservation problems, where requests come online and must be dynamically allocated to limited resources in order to maximize profit. Multi-knapsack problems with or without overbooking are examples of such online stochastic reservations. The paper studies how to adapt the online stochastic framework and the consensus and regret algorithms proposed earlier to online stochastic reservation systems. On the theoretical side, it presents a constant sub-optimality approximation of multi-knapsack problems, leading to a regret algorithm that evaluates each scenario with a single mathematical programming optimization followed by a small number of dynamic programs for one-dimensional knapsacks. It also proposes several integer programming models for handling cancellations and proves their equivalence. On the experimental side, the paper demonstrates the effectiveness of the regret algorithm on multi-knapsack problems (with and without overbooking) based on the benchmarks proposed earlier. [ABSTRACT FROM AUTHOR]