Search

We propose a transformer architecture for time series forecasting with a focus on time series tokenisation and apply it to a real-world prediction problem from the pricing domain. Our architecture aims to learn effective representations at many scales across all available data simultaneously. The model contains a number of novel modules: a differentiated form of time series patching which employs multiple resolutions, a multiple-resolution module for time-varying known variables, a mixer-based module for capturing cross-series information, and a novel output head with favourable scaling to account for the increased number of tokens. We present an application of this model to a real world prediction problem faced by the markdown team at a very large retailer. On the experiments conducted our model outperforms in-house models and the selected existing deep learning architectures.

Decision-focused learning has emerged as a promising approach for decision making under uncertainty by training the upstream predictive aspect of the pipeline with respect to the quality of the downstream decisions. Most existing work has focused on single stage problems. Many real-world decision problems are more appropriately modelled using multistage optimisation as contextual information such as prices or demand is revealed over time and decisions now have a bearing on future decisions. We propose decision-focused forecasting, a multiple-implicitlayer model which in its training accounts for the intertemporal decision effects of forecasts using differentiable optimisation. The recursive model reflects a fully differentiable multistage optimisation approach. We present an analysis of the gradients produced by this model showing the adjustments made to account for the state-path caused by forecasting. We demonstrate an application of the model to an energy storage arbitrage task and report that our model outperforms existing approaches., Comment: Under review. Preprint

We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices $xx^{\mathrm{H}}$, where the elements of $x \in \mathbb{C}^n$ are $m$th unit roots. These polytopes have applications in ${\text{MAX-3-CUT}}$, digital communication technology, angular synchronization and more generally, complex quadratic programming. For ${m=2}$, the complex cut polytope corresponds to the well-known cut polytope. We generalize valid cuts for this polytope to cuts for any complex cut polytope with finite $m>2$ and provide a framework to compare them. Further, we consider a second semidefinite lifting of the complex cut polytope for $m=\infty$. This lifting is proven to be equivalent to other complex Lasserre-type liftings of the same order proposed in the literature, while being of smaller size. We also prove that a second semidefinite lifting of the complex cut polytope for $n = m=3$ is exact. Our theoretical findings are supported by numerical experiments on various optimization problems., Comment: 29 pages (including references) + 6 pages appendix

Decision-focused learning is a promising development for contextual optimisation. It enables us to train prediction models that reflect the contextual sensitivity structure of the problem. However, there have been limited attempts to extend this paradigm to robust optimisation. We propose a double implicit layer model for training prediction models with respect to robust decision loss in uncertain convex quadratically constrained quadratic programs (QCQP). The first layer solves a deterministic version of the problem, the second layer evaluates the worst case realisation for an uncertainty set centred on the observation given the decisions obtained from the first layer. This enables us to learn model parameterisations that lead to robust decisions while only solving a simpler deterministic problem at test time. Additionally, instead of having to solve a robust counterpart we solve two smaller and potentially easier problems in training. The second layer (worst case problem) can be seen as a regularisation approach for predict-and-optimise by fitting to a neighbourhood of problems instead of just a point observation. We motivate relaxations of the worst-case problem in cases of uncertainty sets that would otherwise lead to trust region problems, and leverage various relaxations to deal with uncertain constraints. Both layers are typically strictly convex in this problem setting and thus have meaningful gradients almost everywhere. We demonstrate an application of this model on simulated experiments. The method is an effective regularisation tool for decision-focused learning for uncertain convex QCQPs., Comment: Under submission at CPAIOR 2024

With the increasing effects of climate change, the urgency to step away from fossil fuels is greater than ever before. Electric vehicles (EVs) are one way to diminish these effects, but their widespread adoption is often limited by the insufficient availability of charging stations. In this work, our goal is to expand the infrastructure of EV charging stations, in order to provide a better quality of service in terms of user satisfaction (and availability of charging stations). Specifically, our focus is directed towards urban areas. We first propose a model for the assignment of EV charging demand to stations, framing it as a maximum flow problem. This model is the basis for the evaluation of user satisfaction with a given charging infrastructure. Secondly, we incorporate the maximum flow model into a mixed-integer linear program, where decisions on the opening of new stations and on the expansion of their capacity through additional outlets is accounted for. We showcase our methodology for the city of Montreal, demonstrating the scalability of our approach to handle real-world scenarios. We conclude that considering both spacial and temporal variations in charging demand is meaningful when solving realistic instances.

We present a new model for finding the optimal placement of electric vehicle charging stations across a multi-period time frame so as to maximise electric vehicle adoption. Via the use of advanced discrete choice models and user classes, this work allows for a granular modelling of user attributes and their preferences in regard to charging station characteristics. Instead of embedding an analytical probability model in the formulation, we adopt a simulation approach and pre-compute error terms for each option available to users for a given number of scenarios. This results in a bilevel optimisation model that is, however, intractable for all but the simplest instances. Using the pre-computed error terms to calculate the users covered by each charging station allows for a maximum covering model, for which solutions can be found more efficiently than for the bilevel formulation. The maximum covering formulation remains intractable in some instances, so we propose rolling horizon, greedy, and GRASP heuristics to obtain good quality solutions more efficiently. Extensive computational results are provided, which compare the maximum covering formulation with the current state-of-the-art, both for exact solutions and the heuristic methods. Keywords: Electric vehicle charging stations, facility location, integer programming, discrete choice models, maximum covering, Comment: v3. Accepted-as manuscript. Minor alterations, including a link to the data instances. v2.Major revision, but core results unchanged; Revised models, but Greedy and GRASP are still best methods. Merging and reduction of the section for bilevel model. New sections with additional computational results. Minor notation changes and sentence clarifications

Near-optimality robustness extends multilevel optimization with a limited deviation of a lower level from its optimal solution, anticipated by higher levels. We analyze the complexity of near-optimal robust multilevel problems, where near-optimal robustness is modelled through additional adversarial decision-makers. Near-optimal robust versions of multilevel problems are shown to remain in the same complexity class as the problem without near-optimality robustness under general conditions.

This paper introduces the algorithmic design and implementation of Tulip, an open-source interior-point solver for linear optimization. It implements a regularized homogeneous interior-point algorithm with multiple centrality corrections, and therefore handles unbounded and infeasible problems. The solver is written in Julia, thus allowing for a flexible and efficient implementation: Tulip's algorithmic framework is fully disentangled from linear algebra implementations and from a model's arithmetic. In particular, this allows to seamlessly integrate specialized routines for structured problems. Extensive computational results are reported. We find that Tulip is competitive with open-source interior-point solvers on the H. Mittelmann's benchmark of barrier linear programming solvers. Furthermore, we design specialized linear algebra routines for structured master problems in the context of Dantzig-Wolfe decomposition. These routines yield a tenfold speedup on large and dense instances that arise in power systems operation and two-stage stochastic programming, thereby outperforming state-of-the-art commercial interior point method solvers. Finally, we illustrate Tulip's ability to use different levels of arithmetic precision by solving problems in extended precision.

Energy storage and demand-side response will play an increasingly important role in the future electricity system. We extend previous results on a single energy storage unit to the management of two energy storage units cooperating for the purpose of price arbitrage. We consider a deterministic dynamic programming model for the cooperative problem, which accounts for market impact. We develop the Lagrangian theory and present a new algorithm to identify pairs of strategies. While we are not able to prove that the algorithm provides optimal strategies, we give strong numerical evidence in favour of it. Furthermore, the Lagrangian approach makes it possible to identify decision and forecast horizons, the latter being a time beyond which it is not necessary to look in order to determine the present optimal action. In practice, this allows for real-time reoptimization, with both horizons being of the order of days. Index Terms-control, two storage units, arbitrage, pricemaker, market impact, energy, Lagrangian., Comment: 6 pages, 1 figure. Conference paper accepted to The 16th International Conference on Probabilistic Methods Applied to Power Systems (PMAPS 2020)

Bilevel optimization problems embed the optimality of a subproblem as a constraint of another optimization problem. We introduce the concept of near-optimality robustness for bilevel optimization, protecting the upper-level solution feasibility from limited deviations from the optimal solution at the lower level. General properties and necessary conditions for the existence of solutions are derived for near-optimal robust versions of general bilevel optimization problems. A duality-based solution method is defined when the lower level is convex, leveraging the methodology from the robust and bilevel literature. Numerical results assess the efficiency of exact and heuristic methods and the impact of valid inequalities on the solution time.

The classical alternating current optimal power flow problem is highly nonconvex and generally hard to solve. Convex relaxations, in particular semidefinite, second-order cone, convex quadratic, and linear relaxations, have recently attracted significant interest. The semidefinite relaxation is the strongest among them and is exact for many cases. However, the computational efficiency for solving large-scale semidefinite optimization is lower than for second-order cone optimization. We propose a conic relaxation obtained by combining semidefinite optimization with the reformulation-linearization technique, commonly known as RLT. The proposed relaxation is stronger than the second-order cone relaxation and nearly as tight as the standard semidefinite relaxation. Computational experiments using standard test cases with up to 6515 buses show that the time to solve the new conic relaxation is up to one order of magnitude lower than for the chordal relaxation, a semidefinite relaxation technique that exploits the sparsity of power networks.

Many optimization problems in power transmission networks can be formulated as polynomial problems with complex variables. A polynomial optimization problem with complex variables consists in optimizing a real-valued polynomial whose variables and coefficients are complex numbers subject to some complex polynomial equality or inequality constraints. These problems are usually directly converted to real variables, either using the polar form or the rectangular form. In this work, we propose a Julia module allowing the representation of polynomial problems in their original complex formulation. This module is applied to power systems optimization and its generic design enables the description of several variants of power system problems. Results for the Optimal Power Flow in Alternating Current problem and for the Preventive-Security Constrained Optimal Power Flow problem are presented.

Computational speed and global optimality are key needs for practical algorithms for the optimal power flow problem. Two convex relaxations offer a favorable trade-off between the standard second-order cone and the standard semidefinite relaxations for large-scale meshed networks in terms of optimality gap and computation time: the tight-and-cheap relaxation (TCR) and the quadratic convex relaxation (QCR). We compare these relaxations on 60 PGLib-OPF test cases with up to 1,354 buses under three operating conditions and show that TCR dominates QCR on all 20 typical (TYP) test cases, on 18 out of 20 active power increase (API), and 12 out of 20 small angle difference (SAD). Selected state-of-the-art conic relaxations are implemented in the new MATLAB-based package CONICOPF available on GitHub.

The optimal reactive power dispatch (ORPD) problem is an alternating current optimal power flow (ACOPF) problem where discrete control devices for regulating the reactive power, such as shunt elements and tap changers, are considered. The ORPD problem is modelled as a mixed-integer nonlinear optimization problem and its complexity is increased compared to the ACOPF problem, which is highly nonconvex and generally hard to solve. Recently, convex relaxations of the ACOPF problem have attracted a significant interest since they can lead to global optimality. We propose a tight conic relaxation of the ORPD problem and show that a round-off technique applied with this relaxation leads to near-global optimal solutions with very small guaranteed optimality gaps, unlike with the nonconvex continuous relaxation. We report computational results on selected MATPOWER test cases with up to 3375 buses.

Time-and-Level-of-Use (TLOU) is a recently proposed pricing policy for energy, extending Time-of-Use with the addition of a capacity that users can book for a given time frame, reducing their expected energy cost if they respect this self-determined capacity limit. We introduce a variant of the TLOU defined in the literature, aligned with the supplier interest to prevent unplanned over-consumption. The optimal price-setting problem of TLOU is defined as a bilevel, bi-objective problem anticipating user choices in the supplier decision. An efficient resolution scheme is developed, based on the specific discrete structure of the lower-level user problem. Computational experiments using consumption distributions estimated from historical data illustrate the effectiveness of the proposed framework.