Case Study: The Cosmic Computers Problem

Submitted: 16 Feb 2008

Operations Research Topics: IntegerProgramming, MasterSlaveConstraints, FacilityLocationProblem

Application Areas: Industrial Planning


Problem Description

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 per-unit 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)?

Return to top

Problem Formulation

This problem is a facility location problem where the master-slave constraints control the existence of supply nodes for a transportation problem.

Traditional transportation problem formulations are as follows:

 \[ \begin{array}{r@{\,}r@{\,}l} \min & \displaystyle \sum_{i \in {\cal S}} \sum_{j \in {\cal D}} c_{ij} & x_{ij} \\ \text{subject to} & \displaystyle \sum_{j \in {\cal D}} & x_{ij} = s_i, i \in {\cal S} \\ & \displaystyle \sum_{i \in {\cal S}} & x_{ij} = d_j, j \in {\cal D} \end{array} \]

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 two-fold:
  1. Where to build the plants?
  2. Where to ship the computers?

The flow variables $x_{ij}, i \in {\cal S}, j \in {\cal D}$ determine where to ship the computers, so we need to add binary variables that govern which of the supply nodes exist, i.e., $z_i \in \{0, 1\}, i \in {\cal S}$ that are 1 if $i$ 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 $C_i, i \in {\cal S}$:
\[ \min \sum_{i \in {\cal S}} \sum_{j \in {\cal D}} c_{ij} x_{ij} + \sum_{i \in {\cal S}} C_i z_i \]

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:
\[ \sum_{j \in {\cal D}} x_{ij} = s_i z_i, i \in {\cal S} \]
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):
\[ \sum_{i \in {\cal S}} x_{ij} \geq d_j, j \in {\cal D} \]

4. Identify the data

The data in this problem is the same as that required for a transportation problem, i.e., ${\cal S}$, ${\cal D}$, $s_i, i \in {\cal S}$, etc except that the fixed costs $C_i, i \in {\cal S}$ also needs to be specified.

Return to top

Computational Model

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):


param Supply {SUPPLY_NODES} >= 0, integer;
param Demand {DEMAND_NODES} >= 0, integer;

param Cost {SUPPLY_NODES, DEMAND_NODES} default 0;

  integer default 0;
  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 Build variables into the supply constraints and change the supply constraints since the problem may not be balanced:

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 by removing all the balancing AMPL commands, e.g., param difference;. We add a different check to that ensures there is enough supply to satisfy the demand (otherwise the problem is infeasible):

check : sum {s in SUPPLY_NODES} Supply[s] >= sum {d in DEMAND_NODES} Demand[d];

Return to top


Using we can solve the Cosmic Computers Problem:


The output shows that CPLEX has not required any branch-and-bound nodes again. Is this problem also naturally integer? We can check by solving the LP relaxation using option relax_integrality 1.


Unfortunately, our problem is not naturally integer. CPLEX performs a lot of "clever tricks" to solve mixed-integer programmes quickly. Let's look at the effect of some of these techniques.

First, we can see what is happening in the branch-and-bound tree by setting the CPLEX options for displaying the branch-and-bound process: mipdisplay 2 gives a moderate amount of information about the process and mipinterval 1 displays this information for every node. For detailed information on setting CPLEX options in AMPL see ILOG's AMPL CPLEX User Guide.


This shows that Node 0 (the LP relaxation) is solved, then an integer solution is found quickly with 6 cuts. There are many methods at work here, including:

  1. A relaxation induced neighbourhood search (RINS) heuristic;
  2. A repair heuristic that tries to from integer solutions from fractional ones;
  3. Application of cuts to the LP relaxation;
  4. Careful selection of variables to branch on.

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 rinsheur -1 and repairtries -1) and see what happens (Note To see the true effect of these changes you will have to make changes to your script file, restart AMPL and run your script again. Otherwise, AMPL will use your old solution and the effect of your changes will not be obvious):


Now the LP relaxation Node 0 is solved, but then cuts are generated (indicated by Node 0+) and after 2 cuts are added an integer solution is found, shown by *. After 9 cuts are generated another integer solution is found (hence another *) and this is the optimal solution. Cuts are linear constraints that are added to the LP relaxation to remove fractional solutions. There is a vast amount of literature on cuts for integer programming (try "integer programming cut" on Google), but we will not delve into it here. Let's turn off all the cuts (CPLEX option mipcuts -1) and see what happens:


Here the optimal integer solution is found at the second node and then the rest of the tree (6 branch-and-bound 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 Build['Denver'] even though this variable is integer in the LP relaxation. Instead of using the default CPLEX selection rules for the branching variable, let's branch on the fractional variable that is closest to integer (CPLEX option varselect -1):


Notice that the branch-and-bound 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.

Return to top


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


Return to top

Extra for Experts

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 non-zero Build variables is 2.82 (2 dp), but it should be integer. We can remove the fractional part by forcing this sum to be either $\geq$ 3 or $\leq$ 2. First, let's branch up:


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 Build variables. We can add further constraint branches to continue searching from this node:


Return to top

Student Tasks

  1. Solve the Cosmic Computers Problem. Write a management summary of your solution.

    What to hand in Your management summary.

  2. Experts Only Complete the branch-and-bound process using constraint branches on fractional sums of the Build variables. Draw your branch-and-bound tree as shown above (in the Extra for Experts section). Be sure to indicate what branches you used. Briefly (1 paragraph) compare your experience with constraint branching to the variable branching used in CPLEX.

    What to hand in Hand in your drawing of your branch-and-bound tree along with your conclusions about the effectiveness of constraint branching compared with variable branching.

Return to top

Topic attachments
I Attachment History Action Size Date Who Comment
Unknown file formatdat cosmic.dat r1 manage 0.8 K 2008-04-23 - 05:10 MichaelOSullivan  
Unknown file formatmod cosmic.mod r3 r2 r1 manage 1.5 K 2008-05-13 - 22:37 MichaelOSullivan  
Unknown file formatrun r1 manage 0.6 K 2008-04-23 - 05:11 MichaelOSullivan  
Edit | Attach | Watch | Print version | History: r26 < r25 < r24 < r23 < r22 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r26 - 2018-11-23 - TWikiAdminUser
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback