Relaxations for multi-period optimal power flow problems with discrete decision variables

Quentin Gemine, Damien Ernst, Quentin Louveaux, Bertrand CornélussePscc 2014 · DOI

TL;DR

This paper tackles the complex problem of optimizing power flow over multiple time periods when decisions involve discrete choices (like turning equipment on/off). They introduce two novel relaxation techniques, a Lagrangian relaxation and a network flow-based relaxation, to make these problems computationally tractable. The network flow approach shows promise in producing more feasible solutions compared to existing methods.

What Problem Does This Paper Address?

Modern power systems are increasingly complex, involving multi-period operations (due to fluctuating market prices, equipment ramp-up/down times, and flexible load behavior) and discrete decision variables. These factors lead to mixed-integer non-convex mathematical programs, which are notoriously difficult to solve optimally. Examples include managing day-ahead energy markets with "block bids" or optimizing distribution networks to integrate renewable energy sources and customer flexibility. Traditional optimization methods struggle with the non-convexity and the sheer scale of these problems. The authors aim to develop computationally affordable relaxation techniques that can provide good quality solutions (narrow optimality gap and near-feasibility) for these challenging multi-period optimal power flow (OPF) problems.

Methods

The paper proposes two main relaxation strategies:

  • Lagrangian Relaxation (LR): This is an extension of existing LR techniques for static OPF. The core idea is to dualize the non-convex power flow constraints, breaking the problem into two independent subproblems: one for power injections and another for voltage variables. This simplifies the problem but can lead to solutions that violate original constraints.
  • Network Flow Relaxation (NFR): This novel approach reformulates the OPF problem using network flow variables. It linearizes the power flow equations and then uses a reformulation-linearization technique (RLT) to handle the non-convexity by finding the convex envelope of the quadratic terms. This method explicitly incorporates network topology and aims to produce more feasible solutions by accounting for losses.

Both methods are designed to provide lower bounds on the optimal solution, allowing for efficient problem-solving.

Datasets

The authors evaluated their methods on 14 test instances derived from four different network benchmarks (A, B, C, D) sourced from existing literature ([22]-[24]). These benchmarks were combined with two types of cost functions: generation cost minimization and curtailment minimization. The instances were generated for time horizons of 4 and 8 periods.

Key Insights and Ideas

  • Decomposition is Key: The non-convexity of power flow equations and the time-coupling constraints are major hurdles. Decomposing the problem into smaller, more manageable subproblems (e.g., period-specific voltage problems) is a crucial strategy.
  • Network Topology Matters: The network flow relaxation's ability to incorporate network topology into the power subproblem is a significant advantage over purely Lagrangian approaches, leading to more physically realistic solutions.
  • Feasibility is Crucial for B&B: For algorithms like branch-and-bound that seek global optimality, the feasibility of relaxed solutions is as important as the tightness of the lower bound. Solutions that are closer to satisfying the original constraints can significantly speed up the search process.
  • SDP for Bounds: While not the primary relaxation, Semidefinite Programming (SDP) is used as a tool to derive tighter bounds on voltage and power variables, which are then used to improve the RLT relaxation in the NFR approach.

Key Results

  • Comparable Lower Bounds: Both the Lagrangian Relaxation (LR) and the Network Flow Relaxation (NFR) provided comparable lower bounds on the optimal solution across the tested instances.
  • Reduced Infeasibility with NFR: The NFR approach demonstrated significantly less infeasibility in its solutions for the non-convex power flow constraints (8-10) compared to LR. In several cases, NFR produced solutions that were very close to being feasible, while LR solutions sometimes exhibited very high levels of infeasibility.
  • Mixed Performance on Time: Neither relaxation consistently outperformed the other in terms of computational time, with results varying significantly across different instances.

Limitations and Future Work

  • Quality of Lower Bounds (NFR): The authors note that the quality of lower bounds for NFR, particularly for curtailment applications, could be improved. They suspect that the SDP relaxation used to estimate active losses in lines might not be sufficiently informative, thus penalizing the overall relaxation's tightness.
  • Computational Efficiency: Improving the computational speed of NFR is a goal. The authors suggest exploring subnetworks to infer bounds on voltage and link-flow variables, potentially leading to faster convergence. An iterative approach to refine bounds on specific subproblems is also proposed.
  • Merging Relaxations: A promising future direction is to combine the strengths of LR and NFR. Tightening the power subproblem of LR with network flow concepts could potentially improve the convergence of the non-smooth optimization problem in LR and further reduce solution infeasibility.

Summary updated

BibTeX
@inproceedings{gemine2014relaxations,
  author = {Quentin Gemine and Damien Ernst and Quentin Louveaux and Bertrand Cornélusse},
  title = {{Relaxations for multi-period optimal power flow problems with discrete decision variables}},
  booktitle = {Pscc},
  year = {2014},
  doi = {10.1109/pscc.2014.7038396},
}
Figure