This code provides a minimalist python+gurobi based implementation for computing tight bounds on AC-OPF test cases in the matpower format. Formally, the algorithm computes the "minimal continuous constraint relaxation network" of the AC-OPF problem. Namely, the finds new bounds on the bus voltage magnitudes and the line phase angle differences (i.e. pad) that do not remove any feasible solution to AC-OPF constraints. The method is independent of the objective function under consideration and is applicable with a wide range of power system applications using the operational constraint from the AC-OPF problem.

Details on the theory and correctness of the algorithm can be found in this paper. The method is based on the Quadratic Convex (QC) relaxation of AC power flows, and includes the "lifted nonlinear cuts" from this report.

The primary entry point is the "compute-bounds.py" scipt. It can be run in place without installation. However, it does require gurobi to be installed so that it can imported as a python library, i.e. "import gurobipy". See gurobi for detailed installation instructions.

The standard way to use this script is to provide a matpower case file as follows,

compute-bounds.py case.m

This will solve 2(n+l) QC relaxations in a number of rounds, where n is the number nodes in the network and l is the number of lines. Note that each round may take several minutes for cases with over 100 buses. The progress of each round is summarized by an "ITER_DATA" line. Once a fixpoint is reached (i.e. no further tightening can be made) the script completes by printing out tables of the updated voltage and angle bounds as well as a summary data in a "SMRY_DATA" line.

The default computation can be modified using command line arguments. For example, "--large" can be used for increasing numerical stability on cases with over 1000 buses and "-output" can be used to see more details of the computation. Use "--help" to see a complete list of options.

The paper that proposed this algorithm observed that bound tightening was a powerful pre-processing step for solving AC-OPF problems. Notably, this bound tightening procedure can make the Convex Quadratic (QC) relaxation stronger than the well-known Semi-Definite Relaxation (SDP). This is appealing becouse quadratic programming solvers, such as gurobi, are more scalable and reliable than SDP solvers.

Running this script can consume a significant amount of time for cases with over 100 buses. However, it is important to note that this is a single threaded implementation of a highly parallelizable computation. The "parallel time" field in the summary output suggests the runtime of the algorithm with maximum parallelization. The ideal parallel runtime is less than 5 minutes on all publicly available test cases.

Community-driven development and enhancement of this script are welcome and encouraged. Please fork this repository and share your contributions to the master with pull requests.

Although this code was developed by Carleton Coffrin, the theory behind this algorithm was done in collaboration with Hassan L. Hijazi, and Pascal Van Hentenryck.

If you find this code useful in your work please cite this paper,

@Inbook{Coffrin2015,
  author="Coffrin, Carleton
    and Hijazi, Hassan L.
    and Van Hentenryck, Pascal",
  editor="Pesant, Gilles",
  title="Strengthening Convex Relaxations with Bound Tightening for Power Network Optimization",
  bookTitle="Principles and Practice of Constraint Programming: 21st International Conference, CP 2015, Cork, Ireland, August 31 -- September 4, 2015, Proceedings",
  year="2015",
  publisher="Springer International Publishing",
  pages="39--57",
  isbn="978-3-319-23219-5",
  doi="10.1007/978-3-319-23219-5_4",
  url="http://dx.doi.org/10.1007/978-3-319-23219-5_4"
}

MIT, see LICENSE file for the details.