The INTPOINT Procedure |

Reasons for Infeasibility |

Before optimization commences, PROC INTPOINT tests to ensure that the problem is not infeasible by ensuring that, with respect to supplies, demands, and arc flow bounds, flow conservation can be obeyed at each node:

Let

*IN*be the sum of lower flow bounds of arcs directed toward a node plus the node’s supply. Let*OUT*be the sum of capacities of arcs directed from that node plus the node’s demand. If*IN*exceeds*OUT*, not enough flow can leave the node.Let

*OUT*be the sum of lower flow bounds of arcs directed from a node plus the node’s demand. Let*IN*be the total capacity of arcs directed toward the node plus the node’s supply. If*OUT*exceeds*IN*, not enough flow can arrive at the node.

Reasons why a network problem can be infeasible are similar to those previously mentioned but apply to a set of nodes rather than for an individual node.

Consider the network illustrated in Figure 4.10.

NODE_1----------------->NODE_2 / capac=55 \ / lo=50 \ / \ / \ / \ NODE_3 NODE_4 supply=100 \ / demand=120 \ / \ / \ capac=62 / \ lo=60 / NODE_5----------------->NODE_6

The demand of NODE_4 is 120. That can never be satisfied because the maximal flow through arcs (NODE_1, NODE_2) and (NODE_5, NODE_6) is 117. More specifically, the implicit supply of NODE_2 and NODE_6 is only 117, which is insufficient to satisfy the demand of other nodes (real or implicit) in the network.

Furthermore, the lower flow bounds of arcs (NODE_1, NODE_2) and (NODE_5, NODE_6) are greater than the flow that can reach the tail nodes of these arcs, that, by coincidence, is the total supply of the network. The implicit demand of nodes NODE_1 and NODE_5 is 110, which is greater than the amount of flow that can reach these nodes.

Copyright © SAS Institute, Inc. All Rights Reserved.