Bidirectional connection becomes unbounded

[Mastomaki]

It seems to me that a bidirectional connection becomes unbounded with some common settings.

To Reproduce For connection between node_a and node_b: Set connection__to_node and connection__from_node both for node_a and node_b. Set fix_ratio_out_in_connection_flow to both directions, at most 1 and one direction strictly smaller than 1. Set connection_capacity to some values. Set balance_type_none for node_b.

The connection is then free to consume flow from node_b, unlimited by its capacity.

Expected behavior One would expect it to be limited by the capacity.

Desktop (please complete the following information):

• Which SpineOpt version? Master from Jun 15th.

[clizbe]

@Mastomaki Are you still having a problem with this? @DillonJ Could you check that this is an issue?

[hannesfelipe]

I think I have the same or a similar issue. I have a connection between a balanced and unbalanced node with a fix_ratio_out_in_connection_flow of 1 and a capacity of 1000 for both, connection__to_node and connection__from_node. Additionally, I have some negative costs (as income) for the realised flow. As far as the costs increase, the model becomes unbound (with a small cost the model is still optimal).

[DillonJ]

@hannesfelipe, @Mastomaki, if as described, you have fix_ratio_out_in_connection_flow defined in both directions and capacities on at least one side - this should not happen. I wonder can you provide the model where this is happening and we can take a look?

[Mastomaki]

Hello Jody,

Here you can find an example.

spinedb.zip

As mentioned by @hannesfelipe , the negative cost makes it unbounded.

Jussi

[hannesfelipe]

@Mastomaki thanks for sharing an example.

[Mastomaki]

I wonder if the objective function (connection flow cost) should be changed so that it considers the what is actually coming out of the connection (or going in), not the internal flows in the connection?

[DillonJ]

I've had a look and it looks like a bug. @manuelma I'm wondering if the connection_capacities on the 4 relationships are being assigned to the correct connection flow variables?

[DillonJ]

The reason is that we apply the connection capacities to the sum of the flows when we should really be applying the capacities to the flows indvidually. These are the generated constraints:

connection_flow_capacity(connection = c_elemar, node = n_elec, direction = from_node, stochastic_path = SpineInterface.Object[parent], t = 2019-01-01T00:00~>2019-01-01T01:00) : 
    + connection_flow[c_elemar, n_elec, from_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] 
    - connection_flow[c_elemar, n_elec, to_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] 
        <= 500
 connection_flow_capacity(connection = c_elemar, node = n_elecmarket, direction = from_node, stochastic_path = SpineInterface.Object[parent], t = 2019-01-01T00:00~>2019-01-01T01:00) : 
    + connection_flow[c_elemar, n_elecmarket, from_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] 
    - connection_flow[c_elemar, n_elecmarket, to_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] 
        <= 500
 connection_flow_capacity(connection = c_elemar, node = n_elec, direction = to_node, stochastic_path = SpineInterface.Object[parent], t = 2019-01-01T00:00~>2019-01-01T01:00) :
    - connection_flow[c_elemar, n_elec, from_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] 
    + connection_flow[c_elemar, n_elec, to_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] 
        <= 500
 connection_flow_capacity(connection = c_elemar, node = n_elecmarket, direction = to_node, stochastic_path = SpineInterface.Object[parent], t = 2019-01-01T00:00~>2019-01-01T01:00) :
    - connection_flow[c_elemar, n_elecmarket, from_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] 
    + connection_flow[c_elemar, n_elecmarket, to_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] 
        <= 500

[Mastomaki]

Yes, that's what I understood too. The connection capacity is applied to the net flow where the backwards direction flow has been subtracted.

[g-moralesespana]

A tighter constraint to write would be:

'connection_flow_capacity(connection = c_elemar, node = n_elec, direction = from_node, stochastic_path = SpineInterface.Object[parent], t = 2019-01-01T00:00~>2019-01-01T01:00) :

• connection_flow[c_elemar, n_elec, from_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] + connection_flow[c_elemar, n_elec, to_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] <= 500'

I think that would solve the problem.

[nnhjy]

Fixed in PR #895 using the suggestion.

A tighter constraint to write would be:

'connection_flow_capacity(connection = c_elemar, node = n_elec, direction = from_node, stochastic_path = SpineInterface.Object[parent], t = 2019-01-01T00:00~>2019-01-01T01:00) : + connection_flow[c_elemar, n_elec, from_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] + connection_flow[c_elemar, n_elec, to_node, parent, 2019-01-01T00:00~>2019-01-01T01:00] <= 500'

I think that would solve the problem.

Some observations for future improvement: Symmetric constraints will be created when the capacity parameter is used in both connection__from_node and connection__to_node for the same pair of connection and node. This leads to:

1. If the capacity value is the same, the symmetric constraints are duplicated.
2. If each direction gets a different capacity, then only the constraint with the smaller capacity becomes effective. This makes the other constraint redundant as well.

In such cases, setting different capacities per direction becomes meaningless. If we want to enable the connection to have different capacities in opposite directions, we would need to reformulate the constraint.

[Mastomaki]

We certainly need different capacity in opposite directions!

Another option is to write the constraint individually for directions :to_node and :from_node.

[DillonJ]

We certainly need different capacity in opposite directions!

Another option is to write the constraint individually for directions :to_node and :from_node.

Yeah, I agree - we definitely need different capacities in each direction, our current models need this functionality

[g-moralesespana]

The solution is indeed a capacity for every direction, so assuming the flow in one direction is "in" and in the opposite direction is "out", then it is jut:

in <=InMax
out<=OutMax

If there is no investment, a better set of constraints would be: in/InMax + out/OutMax <=1 where this constraint imposes (some) mutual exclusivity, i.e., if the flow in one direction is at the maximum, then thee flow in the other direction is forced to be zero.

[nnhjy]

I was considering it in a very similar way. The problem of in/InMax + out/OutMax <=1 is when either InMax or OutMax is 0, which could happen when the user wants to block one direction.

A similar option could be:

cap[from_node] * flow[to_node] + cap[to_node] * flow[from_node] <= cap[from_node] * cap[to_node]        (1)
flow[to_node] <= cap[to_node]            (2)
flow[from_node] <= cap[from_node]        (3)

(1) is similar to what @g-moralesespana proposes while allowing for cap=0. But still, when, e.g. cap[from_node]=0 and cap[from_node] != 0, an extra (2) to bound flow[to_node], likewise for cap[to_node]=0.

Besides, if e.g. cap[from_node] is the default None (nothing), i.e. unlimited connection capacity in that direction, (2) is used for flow[to_node].

Note that no strict rule to enforce the two opposite flows being mutually exclusive.

Compared with the standard approach

z1 + z2 <=1        (1)           
flow[to_node] <= cap[to_node] * z1           (2)
flow[from_node] <= cap[from_node] * z2       (3)

where z1, z2 \in [0, 1], and when set binary, the two flows can be completely excluded from each other. The extra variables z1 and z2 are always required. This could be cumbersome especially for the linear-only cases where mutual exclusion is less important, especially compared with the former way. Yet in the case where simultaneous bidirectional flows are strictly forbidden, the binary z seems needed in both ways. Or perhaps this will not happen for connection, for it is not supposed to "generate" like a unit?

[g-moralesespana]

@nnhjy good point about one of the capacities being zero. If one of the capacities is zero, then we could only use:

flow[to_node] <= cap[to_node]            (2)
flow[from_node] <= cap[from_node]        (3)

and if both capacities are different than zero, (2) and (3) can be replaced by flow[to_node]/cap[to_node] + flow[from_node]/cap[from_node] <= 1 (1)

And, indeed, introducing binary variables solves the problem for MIPs, and the solution above solves it for LPs.

[nnhjy]

Indeed, it would be easier to handle the logic under the dividing format that excludes any cap[to\from_node]=0.

Another good news is, as SpineOpt assumes the bidirectional capacity being associated with the same instance of a connection, the equation (1) of whichever form can involve investment. The implementation can be:

v_flow[to_node] / p_cap[to_node] + v_flow[from_node] / p_cap[from_node] 
<= v_available_number_of_the_connection         (1)
if exist p_cap[to_node], p_cap[from_node] > 0

where the v_available_number_of_the_connection includes the existing number (parameter) and invested number (variable) of the connection. Note thep_cap` denotes the parameter for "unit capacity".

Then, only when the condition for (1) cannot be fulfilled would the model generate the following constraints:

flow[to_node] <= p_cap[to_node] * v_available_number_of_the_connection           (2)
if exist p_cap[to_node]

flow[from_node] <= p_cap[from_node] * v_available_number_of_the_connection       (3)
if exist p_cap[from_node]

Bear in mind that a p_cap can be undefined, meaning an infinite capacity, for which no capacity constraint on the flow is needed.

I can implement this LP method if it is good to go.

[manuelma]

Also affects connection_intact_flow_capacity it seems?

[manuelma]

Unfortunately this is making execution time longer for models with a lot of bidirectional connections. It seems to me that at the moment we generate all three constraints, instead of generating either (1) or (2, 3) depending on the value of the capacities. So we are duplicating constraints, and I don't know if solving time is improved at all.

The solution is not simple though, because ideally we'd generate only one constraint and switch the terms depending on the value of the capacities - that way the constraint can update itself as the model rolls. This is because the automatic model update only updates coefficients, but can't replace one constraint by another at the moment.

So it looks like we need to be careful before implementing what in theory seems to be a 'better' constraint, and really understand the impact it has in SpineOpt - it is not a simple model.

Will try to fix somehow.

[nnhjy]

The same issue was also mentioned in PR #926. At that time, I was wondering whether we should open a new issue since the very problem of the unbounded connection has been fixed. Thanks @manuelma for bringing this up! I'd be willing to help improve this.

[clizbe]

Yes I think it's a good idea to close this issue and start a new one for the speed.

[manuelma]

I fixed this via https://github.com/spine-tools/SpineOpt.jl/pull/994