CaseStudyForm  

Title  The Cosmic Computers Problem 
DateSubmitted  16 Feb 2008 
CaseStudyType  TeachingCaseStudy 
OperationsResearchTopics  IntegerProgramming, MasterSlaveConstraints, FacilityLocationProblem 
ApplicationAreas  Industrial Planning 
ProblemDescription 
The Cosmic Computer company wish to set up production in America. They are contemplating building production plants in up to 4 locations. Each location has planning restrictions that effectively determine the monthly production possible in each location. The monthly fixed costs of the different locations have been calculated by the accounting department, and are listed below:
 Location  Monthly Fixed Cost   San Francisco  $70,000   Los Angeles  $70,000   Phoenix  $65,000   Denver  $70,000  These plants will supply stores at 4 locations. Predicted demand and perunit transport costs for supplying the 4 production plants to the 4 stores are shown below, along with the quantity each factory can supply:
Where should the company set up their plants to minimise their total costs (fixed plus transportation)?

ProblemFormulation 
This problem is a facility location problem where the masterslave constraints control the existence of supply nodes for a transportation problem.
Traditional transportation problem formulations are as follows: Let's go through the mathematical programming formulation steps and consider what changes we might have to make. 1. Identify the Decision Variables
The decisions are twofold:
The flow variables determine where to ship the computers, so we need to add binary variables that govern which of the supply nodes exist, i.e., that are 1 if exists and 0 otherwise. 2. Formulate the Objective Function
The cost of transporting good through the network is already incorporated into the transportation problem objective, now we have to add the fixed (construction + maintenance) cost :
3. Formulate the Constraints
The constraints are the same as the transportation problem formulation, except that the supply is determined by the construction (or not) of a plant:
and we need to (at least) meet demand, but the formulation no longer needs to be balanced (otherwise we would always build all our construction plants):
4. Identify the data
The data in this problem is the same as that required for a transportation problem, i.e., , , , etc except that the fixed costs also needs to be specified.

ComputationalModel 
Since a transportation problem is embedded within the Cosmic Computers Problem, we will start with the AMPL model file transportation.mod (see The Transportation Problem in AMPL for details):
set SUPPLY_NODES; set DEMAND_NODES; param Supply {SUPPLY_NODES} >= 0, integer; param Demand {DEMAND_NODES} >= 0, integer; param Cost {SUPPLY_NODES, DEMAND_NODES} default 0; param Lower {SUPPLY_NODES, DEMAND_NODES} integer default 0; param Upper {SUPPLY_NODES, DEMAND_NODES} integer default Infinity; var Flow {i in SUPPLY_NODES, j in DEMAND_NODES} >= Lower[i, j], <= Upper[i, j], integer; minimize TotalCost: sum {i in SUPPLY_NODES, j in DEMAND_NODES} Cost[i, j] * Flow[i, j]; subject to UseSupply {i in SUPPLY_NODES}: sum {j in DEMAND_NODES} Flow[i, j] = Supply[i]; subject to MeetDemand {j in DEMAND_NODES}: sum {i in SUPPLY_NODES} Flow[i, j] = Demand[j]; We add new decision variables that decide if we build the production plants or not: var Build {SUPPLY_NODES} binary; We define a new parameter for the fixed cost (of construction + maintenance): param FixedCost {SUPPLY_NODES};
We incorporate the fixed cost into the objective function and the minimize TotalCost: sum {i in SUPPLY_NODES, j in DEMAND_NODES} Cost[i, j] * Flow[i, j] + sum {i in SUPPLY_NODES} FixedCost[i] * Build[i]; subject to UseSupply {i in SUPPLY_NODES}: sum {j in DEMAND_NODES} Flow[i, j] <= Supply[i] * Build[i]; The final model file is given in cosmic.mod. The data file cosmic.dat is straight forward.
We can also adapt check : sum {s in SUPPLY_NODES} Supply[s] >= sum {d in DEMAND_NODES} Demand[d];

Results 
Using cosmic.run we can solve the Cosmic Computers Problem:
The output shows that CPLEX has not required any branchandbound nodes again. Is this problem also naturally integer? We can check by solving the LP relaxation using
Unfortunately, our problem is not naturally integer. CPLEX performs a lot of "clever tricks" to solve mixedinteger programmes quickly. Let's look at the effect of some of these techniques.
First, we can see what is happening in the branchandbound tree by setting the CPLEX options for displaying the branchandbound process:
This shows that
The RINS heuristic looks for a feasible integer solution starting from the LP relaxation solution and the repair heuristic looks for a feasible integer solution from the initial values (here all zero). Let's turn the heuristics off (CPLEX options
Now the LP relaxation
Here the optimal integer solution is found at the second node and then the rest of the tree (6 branchandbound nodes in all) is used to ensure this is the optimum. CPLEX is very careful with its selection of a branching variable. Here, it branches on
Notice that the branchandbound tree is larger (8 nodes as opposed to 6), so this selection strategy did not work as well as the CPLEX default. While solving the Cosmic Computers Problem we have explored many of the "behind the scenes" work that CPLEX does for you. See Integer Programming with AMPL for more examples. In the Extra for Experts we will see another technique called constraint branching. 
Conclusions 
As with the Brewery Problem, the solution to the Cosmic Computers Problem can be presented in many ways. Figure 1 gives a graphical solution to the Cosmic Computers Problem.
Figure 1 Solution to the Cosmic Computers Problem

ExtraForExperts 
Another form of branch and bound implements branches on constraints that should take integer values. For example, in the Cosmic Computers Problem the sum of any subset of Build variables should be integer. Consider the LP relaxation solution:
The sum of the three nonzero
Our solution is integer so we can fathom this node. Now let's drop the Up constraint and branch down:
This solution still has fractional

StudentTasks 

I  Attachment  History  Action  Size  Date  Who  Comment 

dat  cosmic.dat  r1  manage  0.8 K  20080423  05:10  MichaelOSullivan  
mod  cosmic.mod  r3 r2 r1  manage  1.5 K  20080513  22:37  MichaelOSullivan  
run  cosmic.run  r1  manage  0.6 K  20080423  05:11  MichaelOSullivan 