lanl-ansi
Issues with chordal SDP bounds on large PGLib-OPF cases in PowerModels.jl
Hello everyone,
I am currently working on the possibilities of accelerating AC-OPF resolution using Chordal relaxations. As far as I am concerned, PowerModels provides a built-in chordal relaxation with SparseSDPWRMPowerModel, we implemented a couple of other equivalent relaxation.
The issue I have is that for small instances (<200 bus), the chordal relaxation (SparseSDPWRMPowerModel and our implementations) are providing really tight lower bounds (5 to 10 smaller gaps that SOC or QC, with the same set up as in https://lanl-ansi.github.io/PowerModels.jl/stable/experiment-results/). But for bigger instances, we have bad results which shouldn't actually happen as the Chordal relaxations are supposedly tighter. (I am using Ipopt optimizer for AC, SOC and QC and Mosek optimizer for SparseSDPWRMP and my formulations)
Does any one as any idea of where the problem could be coming from ?
@BaptisteZoghby thank for your interested in OPF research and posting this issue.
The issue I have is that for small instances (<200 bus), the chordal relaxation (SparseSDPWRMPowerModel and our implementations) are providing really tight lower bounds...
I do wonder if there is a bit of a misunderstanding here. There is not a specific mathematical connection between system size and the strength of the SPD relaxation. It is easy to cook up 3-5 bus examples with very large gaps. These references may be useful, https://arxiv.org/abs/1411.0359 https://arxiv.org/abs/1410.8253
Chordal relaxations are supposedly tighter.
For the SOC relaxation the SDP version is strictly stronger. For the QC it is not necessarily the case, see https://arxiv.org/abs/1502.07847
for bigger instances, we have bad results which shouldn't actually happen as the Chordal relaxations are supposedly tighter. (I am using Ipopt optimizer for AC, SOC and QC and Mosek optimizer for SparseSDPWRMP and my formulations)
Ipopt is the most reliable solver, when it can be used. So I am inclined to belive those results on all instances. You may need to update it with a good linear solver (e.g., HSL MA27) to get it converge quickly on large instances.
For larger instances, I find SDP solvers tend to have numerical issues which impact the convergence criteria. This could be the reason that the SOC relation reports better bounds than an SDP relaxation. I personally would not worry about discrepancies <.1% in the usually cost minimizing objective function, higher levels of accuracy require treating many details of the solvers carefully, and likely don't matter in practice.
It is my belief (and I don't know of any comprehensive study showing this) that the SDP relaxation quality degrades with large system sizes (>500 buses), due to a combination of three effects: (1) the network data becomes more realistic; (2) the network data parameters spans more orders of magnitude; (3) floating point numerics in the SDP solvers become an issue preventing convergence to the required objective tolerance.
Some folks have observed rescaling scaling the objective function can help SDP solvers converge on large instances. I personally think solvers should work reliability out of the box.
Hello @ccoffrin, thank you for your quick and exhaustive response!
I understand there is no fundamental link between system size and SDP tightness. However:
- On the typical pglib “TYP” cases (118_ieee, 14_ieee, 162_ieee, 179_goc, 197_snem, 30_ieee, 39_epri, 60_c, 89_pegase), both the built-in SparseSDPWRMPowerModel and our AMD=false variant deliver very tight lower bounds, consistently outperforming SOC and QC.
- On the larger instances (>500 buses), I observe orders-of-magnitude worse bounds (and occasional solver failures) despite using the same chordal relaxations and Mosek settings. (see the attached screenshot of a benchmark table I have for larger instances)
If I’ve understood correctly, your main points are:
- No theoretical correlation between SDP tightness and network size.
2.SDP is not necessarily the best relaxation - In practice, Mosek’s SDP solver can suffer numerical issues on very large problems
A few follow-up questions:
- Could particular sparsity patterns or topologies make chordal SDP struggle on some cases?
- Have you found any Mosek settings (or alternative solvers) that improve convergence on >500-bus networks?
- Should I try to use the Nesta cases to benchmark my formulations more accurately (PGLib OPF is not sufficient ?)
Thanks again for your insights
Hello @ccoffrin, thank you for your quick and exhaustive response!
I understand there is no fundamental link between system size and SDP tightness. However:
- On the typical pglib “TYP” cases (118_ieee, 14_ieee, 162_ieee, 179_goc, 197_snem, 30_ieee, 39_epri, 60_c, 89_pegase), both the built-in SparseSDPWRMPowerModel and our AMD=false variant deliver very tight lower bounds, consistently outperforming SOC and QC.
- On the larger instances (>500 buses), I observe orders-of-magnitude worse bounds (and occasional solver failures) despite using the same chordal relaxations and Mosek settings. (see the attached screenshot of a benchmark table I have for larger instances)
If I’ve understood correctly, your main points are:
- No theoretical correlation between SDP tightness and network size. 2.SDP is not necessarily the best relaxation
- In practice, Mosek’s SDP solver can suffer numerical issues on very large problems
A few follow-up questions:
- Could particular sparsity patterns or topologies make chordal SDP struggle on some cases?
- Have you found any Mosek settings (or alternative solvers) that improve convergence on >500-bus networks?
- Should I try to use the Nesta cases to benchmark my formulations more accurately (PGLib OPF is not sufficient ?)
Thanks again for your insights
Note that in the attached table the AMD False formulation is the same as SparseSDPWRM + I feel I am not understanding everything correctly here so please let me know if anything seems wrong.
Could particular sparsity patterns or topologies make chordal SDP struggle on some cases?
I am not aware of specific details that may cause this. I have anecdotally observed that denser SDP matrices seem to be more numerically challenging.
Have you found any Mosek settings (or alternative solvers) that improve convergence on >500-bus networks?
No not particularly. In my mind Daniel Molzahn is the leading expert on getting SDP methods to work on OPF problems. I suggest you reach out to him.
Should I try to use the Nesta cases to benchmark my formulations more accurately (PGLib OPF is not sufficient ?)
No. PGLib-OPF is the successor to NESTA. I only referenced the NESTA paper because it has a good discussion about a lack of tightness of the SDP relaxation on a 3-bus network.
Note that in the attached table the AMD False formulation is the same as SparseSDPWRM + I feel I am not understanding everything correctly here so please let me know if anything seems wrong.
I have experienced these types of results my self and don't know how to fix them. Solver limitations were often a blocking point in my experiments.