Previous Page

|

Next Page

Nonarc Variables

If the constrained problem to be solved has no nonarc variables, then , , and 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 factory 1 and 3750 chips to factory 2 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

Prod1_19_Mar Prod1_25_Mar 2600
Prod2_19_Mar Prod2_25_Mar 3750
Prod1_19_Apr Prod1_25_Apr 2600
Prod2_19_Apr Prod2_25_Apr 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

Prod1_19_Mar Prod1_25_Mar F1_Unused_Mar
Prod2_19_Mar Prod2_25_Mar F2_Unused_Mar
Prod1_19_Apr Prod1_25_Apr - F1_Kept_Since_Mar
Prod2_19_Apr Prod2_25_Apr - F2_Kept_Since_Mar
F1_Unused_Mar F2_Unused_Mar (continued)
- F1_Kept_Since_Mar - F2_Kept_Since_Mar 0.0

where F1_Kept_Since_Mar is the number of chips used during April at factory 1 that were obtained in March at either factory 1 or factory 2 and F2_Kept_Since_Mar is the number of chips used during April at factory 2 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 5.4 through Example 5.8 for a series of examples that use this TV problem. The use of nonarc variables as described previously is illustrated.