Battery storage is a key technology for distributed renewable energy integration. Wider applications of battery storage systems call for smarter and more flexible deployment models to improve their economic viability. Here we propose a hybrid energy storage system (HESS) model that flexibly coordinates both portable energy storage systems (PESSs) and stationary energy storage systems (SESSs) in a grid. PESSs are batteries and power conversion systems loaded on vehicles that travel between grid nodes with price differences to alleviate grid congestion. PESSs can charge/discharge at grid nodes or swap (part of) batteries with SESSs for profit maximization. We introduce a spatiotemporal decision-making framework for HESS including the planning of SESS and the on-demand dispatch of PESS. We propose a two-phase decision-making algorithm (TPDM), where the first phase uses a spatiotemporal cost-effectiveness aggregation method to determine the optimal SESS location; the second phase shapes a low-complexity solution space by arc destroying and repairing. The results show that HESS achieves significant arbitrage benefit improvement in 86.3% of the operating periods through a year compared with SESS and PESS alone. Compared with commercial solver, the proposed TPDM, on average, can reduce the computational time by 95.5% with an optimality of 1.04%.Note to Practitioners—Battery storage and electric vehicles (EVs) play a crucial role in renewable energy integration and in shaping a low-carbon and sustainable energy and transportation systems. To achieve efficient and scalable management of battery storage across energy and transportation systems, we incorporate the portable energy storage (i.e., batteries transported by vehicles) and stationary energy storage (i.e., batteries placed at grids), into a hybrid energy storage system (HESS), and develop efficient planning framework and scheduling algorithms. Specifically, the proposed methods can provide decision supports for the owners of battery assets to determine the optimal SESS location and for the high-quality coordination of battery charging, swapping, and routing in a HESS. Our methods also have potentials in the on-demand applications of battery storage and EVs across energy and transportation systems, such as ancillary services, grid investment deferral, and battery trading and sharing.

We explore the benefits of multivariable branching schemes for linear-programming-based branch-and-bound algorithms for the 0-1 knapsack problem—that is, the benefits of branching on sets of variables rather than on a single variable (the current default in integer-programming solvers). We present examples where multivariable branching has advantages over single-variable branching and partially characterize situations in which this happens. Chvátal shows that for a specific class of 0-1 knapsack instances, a linear-programming-based branch-and-bound algorithm (employing a single-variable branching scheme) must explore exponentially many nodes. We show that for this class of 0-1 knapsack instances, a linear-programming-based branch-and-bound algorithm employing an appropriately chosen multivariable branching scheme explores either three or seven nodes. Finally, we investigate the performance of various multivariable branching schemes for 0-1 knapsack instances computationally and demonstrate their potential; the multivariable branching schemes explored result in smaller search trees (some in search trees that are an order of magnitude smaller), and some also result in shorter solution times. Summary of Contribution: As a powerful modeling tool, mixed-integer programming (MIP) is ubiquitous in Operations Research and is usually solved via the branch-and-bound framework. However, solving MIPs is computationally challenging in general, where branching affects the performance of solvers dramatically. In this paper, we explore the benefits of branching on multiple variables, which can be viewed as a generalization of the standard single-variable branching. We analyze its theoretical behavior on a special instance introduced by Chvátal, which is proved to be hard for single-variable branching. We also partially characterize situations in which branching on multiple variables is superior to its single-variable counterpart. Lastly, we demonstrate its potential in reducing the overall computational time and possible memory usage for storing unexplored nodes through numerical experiments on 0-1 knapsack problems.