- Problem Description
- Problem Formulation
- Computational Model
- Results
- Conclusions
- Extra for Experts
- StudentTasks

Location | Monthly Fixed Cost |
---|---|

San Francisco | $70,000 |

Los Angeles | $70,000 |

Phoenix | $65,000 |

Denver | $70,000 |

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:

1. *Identify the Decision Variables*

The decisions are two-fold: 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.

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 :
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):
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.
## Computational Model

## Results

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.

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.

## 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.

## Extra for Experts

## Student Tasks

- Where to build the plants?
- Where to ship the computers?

2. *Formulate the Objective Function*

3. *Formulate the Constraints*

4. *Identify the data*

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

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};

`Build`

variables into the supply constraints and change the supply constraints since the problem may not be balanced:

The final model file is given in `cosmic.mod`.

The data file `cosmic.dat` is straight forward.

`transportation.run`

by removing all the balancing AMPL commands, e.g., `param difference;`

. We add a different check to `cosmic.run` 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];

Using `cosmic.run` we can solve the Cosmic Computers Problem:

*LP relaxation* using `option relax_integrality 1`

.

`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.

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

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

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

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

`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`

):

*constraint branching*.

**Figure 1** Solution to the Cosmic Computers Problem

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:

`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 3 or 2. First, let's branch up:

`drop` the `Up` constraint and branch down:

`Build`

variables. We can add further constraint branches to continue searching from this node:

- Solve the Cosmic Computers Problem. Write a management summary of your solution.
**What to hand in**Your management summary. -
**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.

I | Attachment | History | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|---|

dat | cosmic.dat | r1 | manage | 0.8 K | 2008-04-23 - 05:10 | MichaelOSullivan | |

mod | cosmic.mod | r3 r2 r1 | manage | 1.5 K | 2008-05-13 - 22:37 | MichaelOSullivan | |

run | cosmic.run | r1 | manage | 0.6 K | 2008-04-23 - 05:11 | MichaelOSullivan |

Topic revision: r26 - 2018-11-23 - TWikiAdminUser

Copyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback