3
$\begingroup$

At a particular mode, there are 2 inflow arcs, a and b, and two or more outflow arcs, which is kept to 3 for this example, i.e., c, d and e

The first requirement is that only one of the two inflow arcs must be selected. Having said this, I am having difficulties modeling the following, as it differs from conventional flow conservation problems:

  1. If arc a is selected, either one of the three outflow arcs must be selected, i.e, there is freedom to select any outflow arc.

  2. On the other hand, should arc b be selected, only one of arcs d, e can be selected as outflow.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Introduce binary variables $x_a,\dots,x_e,$ with each variable taking value 1 if the corresponding arc is used. To limit yourself to a single input, add the constraint $$x_a + x_b = 1$$ (or $x_a + x_b \le 1$ if it is possible to select neither input). To force selection of exactly one output arc, add $$x_c + x_d + x_e = 1.$$ Finally, to enforce your rule about the connect between input choice and output choice, just add $$x_c \le x_a,$$ which lets you choose arc c only if arc a is chosen.

You will presumably have separate variables for the flow across each arc. If $y_.$ denotes the flow variables, you need to connect them to the selection variables with constraints of the form $$y_i \le M_i x_i$$ where $i$ is one of the arcs and $M_i$ is an upper bound on the possible flow across arc $i$ if that arc is used.

Improve this answer
$\endgroup$
7
  • $\begingroup$ dear prof rubin, I understand that x_c<=x_a is a logical implication such the if x_c=1 implies x_a=1. But there seems to be a disconnect between x_a and x_d and x_e, and x_b and x_d and x_e, i.e., a flow conservation constraint linking them. $\endgroup$
    – Mike
    Jul 21, 2022 at 16:13
  • $\begingroup$ According to your problem statement, arcs d and e are eligible to be selected regardless of whether you chose a or b, so there is no need to constrain them. Flow conservation will presumably be a separate constraint involving the $y$ variables (sum of flows in equals sum of flows out). $\endgroup$
    – prubin ♦
    Jul 21, 2022 at 16:15
  • $\begingroup$ x is only used in my formulation as a binary variable indicating a unit flow. Thus can I take that y_i<=M_i*x_i is unnecessary in my case? $\endgroup$
    – Mike
    Jul 21, 2022 at 16:16
  • $\begingroup$ Hence, I think I would need to invoke flow conservation constraints involving all x_i. $\endgroup$
    – Mike
    Jul 21, 2022 at 16:18
  • $\begingroup$ In that case, if you must have a unit flow incoming then the first two equations in my answer ensure flow conservation (one unit comes in, one unit goes out). If it is possible that nothing comes in (and hence nothing goes out), change the RHS of the second equation from 1 to $x_a + x_b.$ $\endgroup$
    – prubin ♦
    Jul 21, 2022 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.