Counting non negative instances of a variable for use in constraint - efficient formulation?

Specific Domains Optimization (Mathematical)
1

This is an optimisation and not JuMP related question, but I thought it worth asking here. I have a constraint in my model which limits the number of non-negative instances of a variable. Specifically, I have a power balance where there is a slack (load shedding) variable, and I limit the number of times that it can be non-zero:

\sum_{g \in G} gen_{g,t} = D_t + ls_t \quad t \in T \\ lsi_t + eps \geq ls_t / D_t \\ \sum_{t \in T} lsi_t \leq LOLE

where lsi_t is a binary variable and eps is a small number to avoid computational issues.

My question is whether there is literature on efficient formulations of the above, similarly to how, say, in unit commitment the formulation with 3 binary variables tends to be more efficient than with only 1. I imagine there must be some operations research literature on the subject, but searching for key words similar to the ones used in the title haven’t proved useful.

Thanks in advance.

2

I’d say that https://or.stackexchange.com/ is a better place to ask.

You can take a look at the literature on Chance Constraints to deal with that problem.

Having worked with that problem, I would recommend not using LOLE constraints and using an expected energy constraint instead.

Shameless sales pitch: you can take a look on [1910.12972] Reliability-Constrained Power System Expansion Planning: A Stochastic Risk-Averse Optimization Approach which discusses a bit that kind of problem and alternatives.

3

There is not much additional structure to work from, but the last constraint is related to the 0,1 knapsack problem.
I can recommend “Integer Programming” by Michele Conforti, Gérard Cornuéjols and Giacomo Zambelli
(https://www.doi.org/10.1007/978-3-319-11008-0) for good information on integer programming formulations.

4

Thank you @joaquimg, I actually read your paper :slight_smile: It was very interesting, and I understand your comment on the expected energy constraint.

However, my interest in LOLE is that it’s the reliability indicator enshrined in EU Legislation now (see here), and I want to investigate whether with storage and renewables a LOLE target is equivalent to an EENS target, or if it, say, favours conventional generation. It is also extremely irritating / difficult to include in an optimisation problem because it introduces binaries.

EDIT: I’ve also asked on Stack Overflow - covering all bases!

5

Thank you @jd-foster, I will take a look to see if I can get any inspiration from there.

6

@gobs Another equivalent formulation worth considering:

D_t z_t \leq \sum_{g \in G} gen_{g,t} \leq D_t \quad \forall t \in T \\ \sum_{t \in T} z_t \, \geq |T| - LOLE \\ z_t \quad \text{binary} \quad \forall t \in T

(where |S| is the cardinality of the set S)

This difference is

  • no intermediate load-shedding variables (but maybe you use it elsewhere in your formulation).
  • the linear programming relaxation requires at least some of the binary variables z_t to be non-zero and/or fractional, and will may change the branch-and-bound tree for better or worse,
  • this might avoid using the eps…
7

Thanks for the suggestion. As I understand it, you made z_t = -lsi_t, which at first glance I don’t see how this would help, but then again I’m not an expert on this.

I think eps would still be required to avoid numerical issues, but perhaps I’m being to pessimistic about how good / intelligent solvers are (I’m using Gurobi).

I will try it out and let you know!