Consider the Fixed Charge Network Flow instance displayed below (see Section 11.6).

Numbers on arcs are fixed charges fij. All variable costs cij = 0.

(a) Formulate the instance as in 11.31 using decision variables xij ! flow on arc (i, j), and yij = 1 if xi, j 7 0 and = 0 otherwise.

(b) Identify by inspection an optimal solution to the full ILP model of (a).

(c) Identify by inspection an optimal solution to the LP relaxation of the model in (a).

(d) Now Develop an extended formulation of the instance which artificially divides flows into two separate flow networks.
The first in decision variables xij 112 should define constraints for flows from source 1 to first demand 3. The other in xij 122 should define constraints on flows from source 1 to second demand 4. A common set of y-variables for the fixed costs should be subject to pairs of switching constraints for every arc (i, j) as xij 112 … 1demand at 32yij, and xij 122 … 1demand at 42yij

(e) Explain why the new formulation of (d)
is a correct representation of the given fixed-charge instance.

(f) Use class optimization software to solve the LP relaxation of the new version in (d).
Then compare with results in

(b) and (c), and comment.

Transcribed Image Text:

supply=2 26 demand =1 3 20 1 2 15 15 10 26 4 demand =1