The INTPOINT Procedure
-
Overview
-
Getting Started
-
SyntaxFunctional SummaryDictionary of OptionsPROC INTPOINT StatementCAPACITY StatementCOEF StatementCOLUMN StatementCOST StatementDEMAND StatementHEADNODE StatementID StatementLO StatementNAME StatementNODE StatementQUIT StatementRHS StatementROW StatementRUN StatementSUPDEM StatementSUPPLY StatementTAILNODE StatementTYPE StatementVAR Statement
-
DetailsInput Data SetsOutput Data SetsConverting Any PROC INTPOINT Format to an MPS-Format SAS Data SetCase SensitivityLoop ArcsMultiple ArcsFlow and Value BoundsTightening Bounds and Side ConstraintsReasons for InfeasibilityMissing S Supply and Missing D Demand ValuesBalancing Total Supply and Total DemandHow to Make the Data Read of PROC INTPOINT More EfficientStopping Criteria
-
ExamplesProduction, Inventory, Distribution ProblemAltering Arc DataAdding Side ConstraintsUsing Constraints and More Alteration to Arc DataNonarc Variables in the Side ConstraintsSolving an LP Problem with Data in MPS FormatConverting to an MPS-Format SAS Data SetMigration to OPTMODEL: Production, Inventory, Distribution
- References
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 3.10.
Figure 3.10: An Infeasible Network
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.