Distribution 1: Which Factories and Depots to Supply Which Customers


PROC OPTMODEL Statements and Output

The first several PROC OPTMODEL statements declare index sets and parameters and then read the input data:

proc optmodel;
   set <str,str> ARCS;
   num cost {ARCS};
   read data arc_data into ARCS=[i j] cost;

   set <str> FACTORIES;
   num capacity {FACTORIES};
   read data factory_data into FACTORIES=[factory] capacity;

   set <str> DEPOTS;
   num throughput {DEPOTS};
   read data depot_data into DEPOTS=[depot] throughput;

   set <str> CUSTOMERS;
   num demand {CUSTOMERS};
   read data customer_data into CUSTOMERS=[customer] demand;

The following statements use the UNION set operator to declare the NODES index set, declare the supply parameter with an initial value of 0, and populate supply for both factories and customers:

   set NODES = FACTORIES union DEPOTS union CUSTOMERS;
   num supply {NODES} init 0;
   for {i in FACTORIES} supply[i] = capacity[i];
   for {i in CUSTOMERS} supply[i] = -demand[i];

The following statements declare the variables, constraints, and TotalCost objective:

   var Flow {ARCS} >= 0;

   con Flow_balance_con {i in NODES}:
      sum {<(i),j> in ARCS} Flow[i,j] - sum {<j,(i)> in ARCS} Flow[j,i]
   <= supply[i];

   con Depot_con {i in DEPOTS}:
      sum {<(i),j> in ARCS} Flow[i,j] <= throughput[i];

   min TotalCost = sum {<i,j> in ARCS} cost[i,j] * Flow[i,j];

The following statements call the default linear programming algorithm (which is the dual simplex algorithm), print the positive variables in the resulting optimal solution, and print the left-hand side (.body), right-hand side (.ub), and dual value (.dual) of each constraint:

   put 'Minimizing TotalCost...';
   solve;
   print {<i,j> in ARCS: Flow[i,j].sol > 0} Flow;
   print Flow_balance_con.body Flow_balance_con.ub Flow_balance_con.dual;
   print Depot_con.body Depot_con.ub Depot_con.dual;

Figure 19.2 shows the output when you use the (default) dual simplex algorithm.

Figure 19.2: Output from Dual Simplex Algorithm, Minimizing TotalCost

The OPTMODEL Procedure

Problem Summary
Objective Sense Minimization
Objective Function TotalCost
Objective Type Linear
   
Number of Variables 29
Bounded Above 0
Bounded Below 29
Bounded Below and Above 0
Free 0
Fixed 0
   
Number of Constraints 16
Linear LE (<=) 16
Linear EQ (=) 0
Linear GE (>=) 0
Linear Range 0
   
Constraint Coefficients 75

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Dual Simplex
Objective Function TotalCost
Solution Status Optimal
Objective Value 198500
   
Primal Infeasibility 0
Dual Infeasibility 0
Bound Infeasibility 0
   
Iterations 15
Presolve Time 0.00
Solution Time 0.00

[1] [2] Flow
Birmingham C2 10000
Birmingham C4 35000
Birmingham C5 5000
Brighton Birmingham 50000
Brighton London 55000
Exeter C3 40000
Liverpool C1 50000
Liverpool C6 20000
Liverpool Exeter 40000
London C5 55000

[1] Flow_balance_con.BODY Flow_balance_con.UB Flow_balance_con.DUAL
Birmingham 0 0 -0.3
Brighton 105000 200000 0.0
C1 -50000 -50000 -1.0
C2 -10000 -10000 -1.0
C3 -40000 -40000 -1.0
C4 -35000 -35000 -1.5
C5 -60000 -60000 -1.0
C6 -20000 -20000 -1.0
Exeter 0 0 -0.2
Liverpool 110000 150000 0.0
London 0 0 -0.5
Newcastle 0 0 -0.5

[1] Depot_con.BODY Depot_con.UB Depot_con.DUAL
Birmingham 50000 50000 -0.2
Exeter 40000 40000 -0.6
London 55000 100000 0.0
Newcastle 0 70000 0.0



The following statements call the network simplex linear programming algorithm and print the same solution information as before:

   put 'Minimizing TotalCost by using network simplex...';
   solve with LP / algorithm=ns;
   print {<i,j> in ARCS: Flow[i,j].sol > 0} Flow;
   print Flow_balance_con.body Flow_balance_con.ub Flow_balance_con.dual;
   print Depot_con.body Depot_con.ub Depot_con.dual;

Figure 19.3 shows the output when you use the ALGORITHM=NS option to invoke the network simplex algorithm.

Figure 19.3: Output from Network Simplex Algorithm, Minimizing TotalCost

Problem Summary
Objective Sense Minimization
Objective Function TotalCost
Objective Type Linear
   
Number of Variables 29
Bounded Above 0
Bounded Below 29
Bounded Below and Above 0
Free 0
Fixed 0
   
Number of Constraints 16
Linear LE (<=) 16
Linear EQ (=) 0
Linear GE (>=) 0
Linear Range 0
   
Constraint Coefficients 75

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Network Simplex
Objective Function TotalCost
Solution Status Optimal
Objective Value 198500
   
Primal Infeasibility 0
Dual Infeasibility 0
Bound Infeasibility 0
   
Iterations 15
Iterations2 5
Presolve Time 0.00
Solution Time 0.00

[1] [2] Flow
Birmingham C2 10000
Birmingham C4 35000
Birmingham C5 5000
Brighton Birmingham 50000
Brighton Exeter 40000
Brighton London 55000
Exeter C3 40000
Liverpool C1 50000
Liverpool C6 20000
London C5 55000

[1] Flow_balance_con.BODY Flow_balance_con.UB Flow_balance_con.DUAL
Birmingham 0 0 -0.3
Brighton 145000 200000 0.0
C1 -50000 -50000 -1.0
C2 -10000 -10000 -1.0
C3 -40000 -40000 -1.0
C4 -35000 -35000 -1.5
C5 -60000 -60000 -1.0
C6 -20000 -20000 -1.0
Exeter 0 0 -0.2
Liverpool 70000 150000 0.0
London 0 0 -0.5
Newcastle 0 0 -0.5

[1] Depot_con.BODY Depot_con.UB Depot_con.DUAL
Birmingham 50000 50000 -0.2
Exeter 40000 40000 -0.6
London 55000 100000 0.0
Newcastle 0 70000 0.0



The following statements call the linear programming solver to minimize NonpreferredFlow and print both objectives, the positive variables in the resulting optimal solution, and the flow along nonpreferred arcs:

   set <str,str> PREFERRED_ARCS;
   read data preferred_arc_data into PREFERRED_ARCS=[i j];
   set CUSTOMERS_WITH_PREFERENCES = setof {<i,j> in PREFERRED_ARCS} j;
   min NonpreferredFlow =
      sum {<i,j> in ARCS diff PREFERRED_ARCS: j in CUSTOMERS_WITH_PREFERENCES}
         Flow[i,j];

   put 'Minimizing NonpreferredFlow...';
   solve;
   print TotalCost NonpreferredFlow;
   print {<i,j> in ARCS: Flow[i,j].sol > 0} Flow;
   print
      {<i,j> in ARCS diff PREFERRED_ARCS: j in CUSTOMERS_WITH_PREFERENCES}
         Flow;

Figure 19.4 shows the output from the linear programming solver.

Figure 19.4: Output from Linear Programming Solver, Minimizing NonpreferredFlow

Problem Summary
Objective Sense Minimization
Objective Function NonpreferredFlow
Objective Type Linear
   
Number of Variables 29
Bounded Above 0
Bounded Below 29
Bounded Below and Above 0
Free 0
Fixed 0
   
Number of Constraints 16
Linear LE (<=) 16
Linear EQ (=) 0
Linear GE (>=) 0
Linear Range 0
   
Constraint Coefficients 75

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Dual Simplex
Objective Function NonpreferredFlow
Solution Status Optimal
Objective Value 10000
   
Primal Infeasibility 0
Dual Infeasibility 0
Bound Infeasibility 0
   
Iterations 14
Presolve Time 0.00
Solution Time 0.00

TotalCost NonpreferredFlow
284000 10000

[1] [2] Flow
Birmingham C5 50000
Brighton Birmingham 50000
Brighton Exeter 5000
Brighton London 10000
Exeter C6 20000
Liverpool C1 50000
Liverpool C3 40000
Liverpool C4 35000
Liverpool Exeter 15000
Liverpool Newcastle 10000
London C5 10000
Newcastle C2 10000

[1] [2] Flow
Birmingham C1 0
Birmingham C2 0
Brighton C1 0
Exeter C5 0
Liverpool C6 0
London C2 0
London C5 10000
Newcastle C6 0



The following CON statement declares a constraint that limits NonpreferredFlow to the minimum value found in the previous solve:

   con Objective_cut:
      NonpreferredFlow <= NonpreferredFlow.sol;

The following statements call the linear programming solver to minimize TotalCost with a constrained NonpreferredFlow and print the same solution information as before:

   put 'Minimizing TotalCost with constrained NonpreferredFlow...';
   solve obj TotalCost;
   print TotalCost NonpreferredFlow;
   print {<i,j> in ARCS: Flow[i,j].sol > 0} Flow;
   print
      {<i,j> in ARCS diff PREFERRED_ARCS: j in CUSTOMERS_WITH_PREFERENCES}
         Flow;
quit;

Figure 19.5 shows the output from the linear programming solver. As expected, NonpreferredFlow remains at its minimum value and TotalCost is less than its value from Figure 19.4.

Figure 19.5: Output from Linear Programming Solver, Minimizing TotalCost with Constrained NonpreferredFlow

Problem Summary
Objective Sense Minimization
Objective Function TotalCost
Objective Type Linear
   
Number of Variables 29
Bounded Above 0
Bounded Below 29
Bounded Below and Above 0
Free 0
Fixed 0
   
Number of Constraints 17
Linear LE (<=) 17
Linear EQ (=) 0
Linear GE (>=) 0
Linear Range 0
   
Constraint Coefficients 83

Performance Information
Execution Mode Single-Machine
Number of Threads 1

Solution Summary
Solver LP
Algorithm Dual Simplex
Objective Function TotalCost
Solution Status Optimal
Objective Value 246000
   
Primal Infeasibility 0
Dual Infeasibility 2.220446E-16
Bound Infeasibility 0
   
Iterations 19
Presolve Time 0.00
Solution Time 0.00

TotalCost NonpreferredFlow
246000 10000

[1] [2] Flow
Birmingham C5 50000
Brighton Birmingham 50000
Brighton London 30000
Exeter C3 40000
Liverpool C1 50000
Liverpool C4 35000
Liverpool Exeter 40000
Liverpool Newcastle 10000
London C5 10000
London C6 20000
Newcastle C2 10000

[1] [2] Flow
Birmingham C1 0
Birmingham C2 0
Brighton C1 0
Exeter C5 0
Liverpool C6 0
London C2 0
London C5 10000
Newcastle C6 0