Engineering topics
Van Hentenryck, Pascal
Publications and source records attributed to Van Hentenryck, Pascal.
Bucketized Active Sampling for learning ACOPF
Not Available
Asset bundling for hierarchical forecasting of wind power generation
Not Available
Polyhedral Relaxations for Optimal Pump Scheduling of Potable Water Distribution Networks
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.
Capturing Travel Mode Adoption in Designing On-Demand Multimodal Transit Systems
This paper studies how to integrate rider mode preferences into the design of on-demand multimodal transit systems (ODMTSs). It is motivated by a common worry in transit agencies that an ODMTS may be poorly designed if the latent demand, that is, new riders adopting the system, is not captured. This paper proposes a bilevel optimization model to address this challenge, in which the leader problem determines the ODMTS design, and the follower problems identify the most cost efficient and convenient route for riders under the chosen design. The leader model contains a choice model for every potential rider that determines whether the rider adopts the ODMTS given her proposed route. To solve the bilevel optimization model, the paper proposes an exact decomposition method that includes Benders optimal cuts and no-good cuts to ensure the consistency of the rider choices in the leader and follower problems. Moreover, to improve computational efficiency, the paper proposes upper and lower bounds on trip durations for the follower problems, valid inequalities that strengthen the no-good cuts, and approaches to reduce the problem size with problem-specific preprocessing techniques. The proposed method is validated using an extensive computational study on a real data set from the Ann Arbor Area Transportation Authority, the transit agency for the broader Ann Arbor and Ypsilanti region in Michigan. The study considers the impact of a number of factors, including the price of on-demand shuttles, the number of hubs, and access to transit systems criteria. The designed ODMTSs feature high adoption rates and significantly shorter trip durations compared with the existing transit system and highlight the benefits of ensuring access for low-income riders. Finally, the computational study demonstrates the efficiency of the decomposition method for the case study and the benefits of computational enhancements that improve the baseline method by several orders of magnitude. Funding: This research was partly supported by National Science Foundation [Leap HI Proposal NSF-1854684] and the Department of Energy [Research Award 7F-30154].
Grid Optimization Competition on Synthetic and Industrial Power Systems
This paper summarizes a grid optimization (GO) competition effort in the United States to find the best solution strategies for up to interconnect-scale power system networks with around 32,000 buses. The optimization problem is a mixedinteger, non-convex non-linear problem, (MINLP) and includes discrete variables such as unit commitment and line switching, control settings (transformer taps and phase shifters with impedance correction tables), and bus shunts. The case study includes six actual industry grids as well as 16 realistic synthetic grids created by three different dataset teams. The winners are selected and ranked based on scoring criteria, which consider the solution quality (such as objective functions) within time limits. Nine winner teams are selected from 26 competitor teams. The results achieved by different teams are described and the performance of different algorithms on synthetic grids and actual industry grids are compared and analyzed.
Learning optimization proxies for large-scale Security-Constrained Economic Dispatch
Not Available
A linear outer approximation of line losses for DC-based optimal power flow problems
Not Available
Data-driven time series reconstruction for modern power systems research
Not Available
Ridesharing and fleet sizing for On-Demand Multimodal Transit Systems
Not Available
Privacy-preserving obfuscation for distributed power systems
Not Available
Communication-Constrained Expansion Planning for Resilient Distribution Systems
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.
Optimization of Structural Flood Mitigation Strategies
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. Furthermore 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.
Graphical models for optimal power flow
Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured graphical model to the OPF problem. Combining this with an interval discretization of the nodal variables, we develop an approximation algorithm for the OPF problem. Further, we use techniques from constraint programming (CP) to perform interval computations and adaptive bound propagation to obtain practically efficient algorithms. Compared to previous algorithms that solve OPF with optimality guarantees using convex relaxations, our approach is able to work for arbitrary tree-structured distribution networks and handle mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing fashion that is scalable and is suitable for “smart grid” applications like control of distributed energy resources. In conclusion, numerical evaluations on several benchmark networks show that practical OPF problems can be solved effectively using this approach.