Nonarc Variables

The NETFLOW Procedure

Nonarc Variables

If the constrained problem to be solved has no nonarc variables, then Q, d, and z do not exist. However, nonarc variables can be used to simplify side constraints. For example, if a sum of flows appears in many constraints, it may be worthwhile to equate this expression with a nonarc variable and use this in the other constraints. By assigning a nonarc variable a nonzero objective function, it is then possible to incur a cost for using resources above some lowest feasible limit. Similarly, a profit (a negative objective function coefficient value) can be made if all available resources are not used.

In some models, nonarc variables are used in constraints to absorb excess resources or supply needed resources. Then, either the excess resource can be used or the needed resource can be supplied to another component of the model.

For example, consider a multicommodity problem of making television sets that have either 19- or 25-inch screens. In their manufacture, 3 and 4 chips, respectively, are used. Production occurs at 2 factories during March and April. The supplier of chips can supply only 2600 chips to factory1 and 3750 chips to factory2 each month. The names of arcs are in the form Prodn_s_m , where n is the factory number, s is the screen size, and m is the month. For example, Prod1_25_Apr is the arc that conveys the number of 25-inch TVs produced in factory 1 during April. You might have to determine similar systematic naming schemes for your application. As described, the constraints are

3 Prod1_19_Mar + 4 Prod1_25_Mar $\le$ 2600
3 Prod2_19_Mar + 4 Prod2_25_Mar $\le$ 3750
3 Prod1_19_Apr + 4 Prod1_25_Apr $\le$ 2600
3 Prod2_19_Apr + 4 Prod2_25_Apr $\le$ 3750

If there are chips that could be obtained for use in March but not used for production in March, why not keep these unused chips until April? Furthermore, if the March excess chips at factory 1 could be used either at factory 1 or factory 2 in April, the model becomes

3 Prod1_19_Mar + 4 Prod1_25_Mar + F1_Unused_Mar = 2600
3 Prod2_19_Mar + 4 Prod2_25_Mar + F2_Unused_Mar = 3750
3 Prod1_19_Apr + 4 Prod1_25_Apr - F1_Kept_Since_Mar = 2600
3 Prod2_19_Apr + 4 Prod2_25_Apr - F2_Kept_Since_Mar = 3750
F1_Unused_Mar + F2_Unused_Mar (continued)
- F1_Kept_Since_Mar - F2_Kept_Since_Mar $\ge$ 0.0

where F1_Kept_Since_Mar is the number of chips used during April at factory1 that were obtained in March at either factory1 or factory2 and F2_Kept_Since_Mar is the number of chips used during April at factory2 that were obtained in March. The last constraint ensures that the number of chips used during April that were obtained in March does not exceed the number of chips not used in March. There may be a cost to hold chips in inventory. This can be modeled having a positive objective function coefficient for the nonarc variables F1_Kept_Since_Mar and F2_Kept_Since_Mar. Moreover, nonarc variable upper bounds represent an upper limit on the number of chips that can be held in inventory between March and April.

See Example 4.4 through Example 4.8 for a series of examples that use this TV problem. The use of nonarc variables as descriped previously is illustrated.

Chapter Contents
Previous
Next
Top