<-- Under Construction -->

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 Build variables into the supply constraints:

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

Finally, we change the MeetDemand constraints:

subject to MeetDemand {j in DEMAND_NODES}:
  sum {i in SUPPLY_NODES} Flow[i, j] >= Demand[j];

The final model file is given in cosmic.mod.

The data file cosmic.dat is straight forward.

We can also adapt 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];

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 [[LPRelaxation][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 Node 0+ gives two integer solutions (indicated by *), the final one of which is optimal. There are many methods at work here, including:

1. A relaxation induced neighbourhood search (RINS) heuristic (indicated by the +);
2. A repair heuristic (also indicated by a + and a comment on repair);
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):

The first integer solution (with TotalCost = 226400) is no longer found (as it was the result of the RINS heuristic), but applying cuts still gives an integer solution without any branch-and-bound nodes. 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.| |*FORM FIELD Conclusions*|Conclusions|As with the Brewery Problem, the solution to the Cosmic Computers Problem can be presented in many ways. [[#fig1][Figure 1] gives a graphical solution to the Cosmic Computers Problem.

Figure 1 Solution to the Cosmic Computers Problem

|

<-- Under Construction -->

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 Build variables into the supply constraints:

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

Finally, we change the MeetDemand constraints:

subject to MeetDemand {j in DEMAND_NODES}:
  sum {i in SUPPLY_NODES} Flow[i, j] >= Demand[j];

The final model file is given in cosmic.mod.

The data file cosmic.dat is straight forward.

We can also adapt 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];

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 [[LPRelaxation][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 Node 0+ gives two integer solutions (indicated by *), the final one of which is optimal. There are many methods at work here, including:

1. A relaxation induced neighbourhood search (RINS) heuristic (indicated by the +);
2. A repair heuristic (also indicated by a + and a comment on repair);
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):

The first integer solution (with TotalCost = 226400) is no longer found (as it was the result of the RINS heuristic), but applying cuts still gives an integer solution without any branch-and-bound nodes. 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.| |*FORM FIELD Conclusions*|Conclusions|As with the Brewery Problem, the solution to the Cosmic Computers Problem can be presented in many ways. [[#fig1][Figure 1] gives a graphical solution to the Cosmic Computers Problem.

Figure 1 Solution to the Cosmic Computers Problem

|

What to hand in Hand in your management summary.

EXTRA FOR EXPERTS' TASKS

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

<-- Under Construction -->

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 two-fold:

1. Where to build the plants?
2. Where to ship the computers?

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.

| |*FORM FIELD ComputationalModel*|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 Build variables into the supply constraints:

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

Finally, we change the MeetDemand constraints:

subject to MeetDemand {j in DEMAND_NODES}:
  sum {i in SUPPLY_NODES} Flow[i, j] >= Demand[j];

The final model file is given in cosmic.mod.

The data file cosmic.dat is straight forward.

We can also adapt 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];

| |*FORM FIELD Results*|Results|Using cosmic.run 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 [[LPRelaxation][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 Node 0+ gives two integer solutions (indicated by *), the final one of which is optimal. There are many methods at work here, including:

1. A relaxation induced neighbourhood search (RINS) heuristic (indicated by the +);
2. A repair heuristic (also indicated by a + and a comment on repair);
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):

The first integer solution (with TotalCost = 226400) is no longer found (as it was the result of the RINS heuristic), but applying cuts still gives an integer solution without any branch-and-bound nodes. 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.|

What to hand in Hand in your management summary.

EXTRA FOR EXPERTS' TASKS

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

<-- Under Construction -->

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)? | |*FORM FIELD ProblemFormulation*|ProblemFormulation|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:

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

|

The sum of the three non-zero Build variables is 2.82 (2 dp), but it should be integer. Remove the fractional part by forcing this 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 ???LINK??? drop the Up constraint and branch down:

This solution still has fractional Build variables. We can use another constraint branch to continue searching from this node:

| |*FORM FIELD StudentTasks*|StudentTasks| 1 Solve The Computer Plant Problem. Write a management summary of your solution. Be sure to answer all the questions in the problem description.

What to hand in Hand in your management summary.

EXTRA FOR EXPERTS' TASKS

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

<-- Under Construction -->

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)? | |*FORM FIELD ProblemFormulation*|ProblemFormulation|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:

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

| |*FORM FIELD ComputationalModel*|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 Build variables into the supply constraints:

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

Finally, we change the MeetDemand constraints:

subject to MeetDemand {j in DEMAND_NODES}:
  sum {i in SUPPLY_NODES} Flow[i, j] >= Demand[j];

The final model file is given in cosmic.mod.

The data file cosmic.dat is straight forward.

We can also adapt 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];

|

Validation

To ensure our solution is valid we simply need to check that the Build variables take integer values (either 0 or 1) and that the shipments from the plants to the stores are within the bounds specified by the construction decisions.

The optimal solution shows that Cosmic Computers will build production plants in San Francisco, but not Denver. We can consider the effect of the tax on transportation by using parametric analysis:

param SFCost {DEMAND_NODES};

let {d in DEMAND_NODES} SFCost[d] := Cost['San Francisco', d];

option omit_zero_rows 1;
option omit_zero_cols 1;

for {t in 0.15..0.20 by 0.005} {
  let {d in DEMAND_NODES} Cost['San Francisco', d] := (1 + t) * SFCost[d];
  solve;
  
  printf "Tax rate = %g\%\n", t * 100;
  display Build, Flow;
}

We can perform a similar parametric analysis on BuildCost['Denver'] to find the maximum price that will result in construction in Denver (and hence how much of a tax rebate the Denver mayor would have to offer).

PRESENTATION OF SOLUTION AND ANALYSIS

Your management summary should contain:

1. A brief summary of the problem description;
2. A construction plan for the plants;
3. A transportation plan that describes the shipments from plants to stores;
4. A description of your post-optimal analysis:

• A brief description of the analysis undertaken (and why);
• A summary of the results of your analysis;

IMPLEMENTATION AND ONGOING MONITORING

Before implementation, sensitivity analysis of both the fixed and transportation costs could identify any data that needs to be confirmed before proceeding. This could also identify any problems should construction costs run over budget.

Ongoing monitoring of the transportation costs, production levels (supply) and demands will produce optimal shiiping plans. If the fixed cost at any plant rises significantly, relocation may be considered (this can also take the form of a facility location problem).| |*FORM FIELD ExtraForExperts*|ExtraForExperts|Another form of branch and bound implements branches on constraints that should take integer values. For example, in The Computer Plant 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. Remove the fractional part by forcing this 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 ???LINK??? drop the Up constraint and branch down:

This solution still has fractional Build variables. We can use another constraint branch to continue searching from this node:

| |*FORM FIELD StudentTasks*|StudentTasks| 1 Solve The Computer Plant Problem. Write a management summary of your solution. Be sure to answer all the questions in the problem description.

What to hand in Hand in your management summary.

EXTRA FOR EXPERTS' TASKS

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

<-- Under Construction -->

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

Validation

To ensure our solution is valid we simply need to check that the Build variables take integer values (either 0 or 1) and that the shipments from the plants to the stores are within the bounds specified by the construction decisions.

The optimal solution shows that Cosmic Computers will build production plants in San Francisco, but not Denver. We can consider the effect of the tax on transportation by using parametric analysis:

param SFCost {DEMAND_NODES};

let {d in DEMAND_NODES} SFCost[d] := Cost['San Francisco', d];

option omit_zero_rows 1;
option omit_zero_cols 1;

for {t in 0.15..0.20 by 0.005} {
  let {d in DEMAND_NODES} Cost['San Francisco', d] := (1 + t) * SFCost[d];
  solve;
  
  printf "Tax rate = %g\%\n", t * 100;
  display Build, Flow;
}

We can perform a similar parametric analysis on BuildCost['Denver'] to find the maximum price that will result in construction in Denver (and hence how much of a tax rebate the Denver mayor would have to offer).

PRESENTATION OF SOLUTION AND ANALYSIS

Your management summary should contain:

1. A brief summary of the problem description;
2. A construction plan for the plants;
3. A transportation plan that describes the shipments from plants to stores;
4. A description of your post-optimal analysis:

• A brief description of the analysis undertaken (and why);
• A summary of the results of your analysis;

IMPLEMENTATION AND ONGOING MONITORING

Before implementation, sensitivity analysis of both the fixed and transportation costs could identify any data that needs to be confirmed before proceeding. This could also identify any problems should construction costs run over budget.

Ongoing monitoring of the transportation costs, production levels (supply) and demands will produce optimal shiiping plans. If the fixed cost at any plant rises significantly, relocation may be considered (this can also take the form of a facility location problem).| |*FORM FIELD ExtraForExperts*|ExtraForExperts|Another form of branch and bound implements branches on constraints that should take integer values. For example, in The Computer Plant 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. Remove the fractional part by forcing this 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 ???LINK??? drop the Up constraint and branch down:

This solution still has fractional Build variables. We can use another constraint branch to continue searching from this node:

| |*FORM FIELD StudentTasks*|StudentTasks| 1 Solve The Computer Plant Problem. Write a management summary of your solution. Be sure to answer all the questions in the problem description.

What to hand in Hand in your management summary.

EXTRA FOR EXPERTS' TASKS

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

<-- Under Construction -->

<-- Under Construction -->

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

reset;

model cosmic.mod;
data cosmic.dat;

option solver cplex;

solve;

display Build;
display Flow;

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 ???LINK??? 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 CPLEX setting in AMPL see ???LINK??? ILOG's AMPL CPLEX User Guide .

This shows that Node 0 (the LP relaxation) is solved, then Node 0+ gives two integer solutions (indicated by *), the final one of which is optimal. There are many methods at work here, including:

1. A relaxation induced neighbourhood search (RINS) heuristic (indicated by the +);
2. A repair heuristic (also indicated by a + and a comment on repair);
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 option 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 you changes will not be obvious):

The first integer solution (with TotalCost = 230282) is no longer found (as it was the result of the RINS heuristic), but applying cuts still gives an integer solution without any branch-and-bound nodes. 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 (google "integer programming cut"), 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 varaible. 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):

The Computer Plant Problem has demonstrated many of the "behind the scenes" work that CPLEX does for you. For another example of integer programming in AMPL, see ???LINK??? the Ice Sculptures example . In the ???LINK??? Extra for Experts we will see another technique called constraint branching.| |*FORM FIELD Conclusions*|Conclusions|*POST-OPTIMAL ANALYSIS*

Validation

To ensure our solution is valid we simply need to check that the Build variables take integer values (either 0 or 1) and that the shipments from the plants to the stores are within the bounds specified by the construction decisions.

The optimal solution shows that Cosmic Computers will build production plants in San Francisco, but not Denver. We can consider the effect of the tax on transportation by using parametric analysis:

param SFCost {DEMAND_NODES};

let {d in DEMAND_NODES} SFCost[d] := Cost['San Francisco', d];

option omit_zero_rows 1;
option omit_zero_cols 1;

for {t in 0.15..0.20 by 0.005} {
  let {d in DEMAND_NODES} Cost['San Francisco', d] := (1 + t) * SFCost[d];
  solve;
  
  printf "Tax rate = %g\%\n", t * 100;
  display Build, Flow;
}

We can perform a similar parametric analysis on BuildCost['Denver'] to find the maximum price that will result in construction in Denver (and hence how much of a tax rebate the Denver mayor would have to offer).

PRESENTATION OF SOLUTION AND ANALYSIS

Your management summary should contain:

1. A brief summary of the problem description;
2. A construction plan for the plants;
3. A transportation plan that describes the shipments from plants to stores;
4. A description of your post-optimal analysis:

• A brief description of the analysis undertaken (and why);
• A summary of the results of your analysis;

IMPLEMENTATION AND ONGOING MONITORING

Before implementation, sensitivity analysis of both the fixed and transportation costs could identify any data that needs to be confirmed before proceeding. This could also identify any problems should construction costs run over budget.

Ongoing monitoring of the transportation costs, production levels (supply) and demands will produce optimal shiiping plans. If the fixed cost at any plant rises significantly, relocation may be considered (this can also take the form of a facility location problem).|

<-- Under Construction -->

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

reset;

model cosmic.mod;
data cosmic.dat;

option solver cplex;

solve;

display Build;
display Flow;

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 ???LINK??? 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 CPLEX setting in AMPL see ???LINK??? ILOG's AMPL CPLEX User Guide .

This shows that Node 0 (the LP relaxation) is solved, then Node 0+ gives two integer solutions (indicated by *), the final one of which is optimal. There are many methods at work here, including:

1. A relaxation induced neighbourhood search (RINS) heuristic (indicated by the +);
2. A repair heuristic (also indicated by a + and a comment on repair);
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 option 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 you changes will not be obvious):

The first integer solution (with TotalCost = 230282) is no longer found (as it was the result of the RINS heuristic), but applying cuts still gives an integer solution without any branch-and-bound nodes. 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 (google "integer programming cut"), 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 varaible. 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):

The Computer Plant Problem has demonstrated many of the "behind the scenes" work that CPLEX does for you. For another example of integer programming in AMPL, see ???LINK??? the Ice Sculptures example . In the ???LINK??? Extra for Experts we will see another technique called constraint branching.| |*FORM FIELD Conclusions*|Conclusions|*POST-OPTIMAL ANALYSIS*

Validation

To ensure our solution is valid we simply need to check that the Build variables take integer values (either 0 or 1) and that the shipments from the plants to the stores are within the bounds specified by the construction decisions.

The optimal solution shows that Cosmic Computers will build production plants in San Francisco, but not Denver. We can consider the effect of the tax on transportation by using parametric analysis:

param SFCost {DEMAND_NODES};

let {d in DEMAND_NODES} SFCost[d] := Cost['San Francisco', d];

option omit_zero_rows 1;
option omit_zero_cols 1;

for {t in 0.15..0.20 by 0.005} {
  let {d in DEMAND_NODES} Cost['San Francisco', d] := (1 + t) * SFCost[d];
  solve;
  
  printf "Tax rate = %g\%\n", t * 100;
  display Build, Flow;
}

We can perform a similar parametric analysis on BuildCost['Denver'] to find the maximum price that will result in construction in Denver (and hence how much of a tax rebate the Denver mayor would have to offer).

PRESENTATION OF SOLUTION AND ANALYSIS

Your management summary should contain:

1. A brief summary of the problem description;
2. A construction plan for the plants;
3. A transportation plan that describes the shipments from plants to stores;
4. A description of your post-optimal analysis:

• A brief description of the analysis undertaken (and why);
• A summary of the results of your analysis;

IMPLEMENTATION AND ONGOING MONITORING

Before implementation, sensitivity analysis of both the fixed and transportation costs could identify any data that needs to be confirmed before proceeding. This could also identify any problems should construction costs run over budget.

Ongoing monitoring of the transportation costs, production levels (supply) and demands will produce optimal shiiping plans. If the fixed cost at any plant rises significantly, relocation may be considered (this can also take the form of a facility location problem).|

<-- Under Construction -->

reset;

model cosmic.mod;
data cosmic.dat;

option solver cplex;

solve;

display Build;
display Flow;

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 ???LINK??? 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 CPLEX setting in AMPL see ???LINK??? ILOG's AMPL CPLEX User Guide .

This shows that Node 0 (the LP relaxation) is solved, then Node 0+ gives two integer solutions (indicated by *), the final one of which is optimal. There are many methods at work here, including:

1. A relaxation induced neighbourhood search (RINS) heuristic (indicated by the +);
2. A repair heuristic (also indicated by a + and a comment on repair);
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 option 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 you changes will not be obvious):

The first integer solution (with TotalCost = 230282) is no longer found (as it was the result of the RINS heuristic), but applying cuts still gives an integer solution without any branch-and-bound nodes. 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 (google "integer programming cut"), 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 varaible. 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):

The Computer Plant Problem has demonstrated many of the "behind the scenes" work that CPLEX does for you. For another example of integer programming in AMPL, see ???LINK??? the Ice Sculptures example . In the ???LINK??? Extra for Experts we will see another technique called constraint branching.| |*FORM FIELD Conclusions*|Conclusions|*POST-OPTIMAL ANALYSIS*

Validation

To ensure our solution is valid we simply need to check that the Build variables take integer values (either 0 or 1) and that the shipments from the plants to the stores are within the bounds specified by the construction decisions.

The optimal solution shows that Cosmic Computers will build production plants in San Francisco, but not Denver. We can consider the effect of the tax on transportation by using parametric analysis:

param SFCost {DEMAND_NODES};

let {d in DEMAND_NODES} SFCost[d] := Cost['San Francisco', d];

option omit_zero_rows 1;
option omit_zero_cols 1;

for {t in 0.15..0.20 by 0.005} {
  let {d in DEMAND_NODES} Cost['San Francisco', d] := (1 + t) * SFCost[d];
  solve;
  
  printf "Tax rate = %g\%\n", t * 100;
  display Build, Flow;
}

We can perform a similar parametric analysis on BuildCost['Denver'] to find the maximum price that will result in construction in Denver (and hence how much of a tax rebate the Denver mayor would have to offer).

PRESENTATION OF SOLUTION AND ANALYSIS

Your management summary should contain:

1. A brief summary of the problem description;
2. A construction plan for the plants;
3. A transportation plan that describes the shipments from plants to stores;
4. A description of your post-optimal analysis:

• A brief description of the analysis undertaken (and why);
• A summary of the results of your analysis;

IMPLEMENTATION AND ONGOING MONITORING

Before implementation, sensitivity analysis of both the fixed and transportation costs could identify any data that needs to be confirmed before proceeding. This could also identify any problems should construction costs run over budget.

Ongoing monitoring of the transportation costs, production levels (supply) and demands will produce optimal shiiping plans. If the fixed cost at any plant rises significantly, relocation may be considered (this can also take the form of a facility location problem).|

<-- Under Construction -->

This problem is essentially a ???LINK??? transportation problem, but with ???LINK??? master-slave constraints at the supply nodes. Since we don't want to use all our supply (as we might not build all our plants), let's start with the unbalanced ???LINK??? transportation.mod model file and see what changes we need to make.

1. IDENTIFY THE DECISION VARIABLES

The decisions are two-fold:

1. Where to build the plants?
2. Where to ship the computers?

This is specified by Flow in transportation.mod. We need to add ???LINK??? binary variables to transportation.mod (rename it cosmic.mod) for determining if a plant is built or not:

# Do we build a SUPPLY_NODE or not?
var Build {SUPPLY_NODES} binary default 1;

2. FORMULATE THE OBJECTIVE FUNCTION

We have already incorporated the transportation cost in transportation.mod, now we have to add the fixed (construction + maintenance) cost:

# The cost of building a SUPPLY_NODE
param BuildCost {SUPPLY_NODES};

# The objective is to minimise the total cost (transportation + build)
minimize TotalCost:
  sum {s in SUPPLY_NODES, t in DEMAND_NODES}
    Cost[s, t] * Flow[s, t] +
  sum {s in SUPPLY_NODES} BuildCost[s] * Build[s];

3. FORMULATE THE CONSTRAINTS

The constraints are the same as in transportatioon.mod, except that the supply is determined by the construction (or not) of a plant:

# Flow must not exceed supply
subject to EnoughSupply {s in SUPPLY_NODES}:
  sum {t in DEMAND_NODES} Flow[s, t] <= Supply[s] * Build[s];

4. IDENTIFY THE DATA

The data file cosmic.dat for this problem is the same as the data for a transportation problem (e.g., brewery.dat), except that the fixed cost also needs to be specified:

param           BuildCost :=
'San Francisco'     70000
'Los Angeles'       70000
Phoenix             65000
Denver              70000
 ;

reset;

model cosmic.mod;
data cosmic.dat;

option solver cplex;

solve;

display Build;
display Flow;

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 ???LINK??? 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 CPLEX setting in AMPL see ???LINK??? ILOG's AMPL CPLEX User Guide .

This shows that Node 0 (the LP relaxation) is solved, then Node 0+ gives two integer solutions (indicated by *), the final one of which is optimal. There are many methods at work here, including:

1. A relaxation induced neighbourhood search (RINS) heuristic (indicated by the +);
2. A repair heuristic (also indicated by a + and a comment on repair);
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 option 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 you changes will not be obvious):

The first integer solution (with TotalCost = 230282) is no longer found (as it was the result of the RINS heuristic), but applying cuts still gives an integer solution without any branch-and-bound nodes. 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 (google "integer programming cut"), 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 varaible. 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):

The Computer Plant Problem has demonstrated many of the "behind the scenes" work that CPLEX does for you. For another example of integer programming in AMPL, see ???LINK??? the Ice Sculptures example . In the ???LINK??? Extra for Experts we will see another technique called constraint branching.| |*FORM FIELD Conclusions*|Conclusions|*POST-OPTIMAL ANALYSIS*

Validation

To ensure our solution is valid we simply need to check that the Build variables take integer values (either 0 or 1) and that the shipments from the plants to the stores are within the bounds specified by the construction decisions.

The optimal solution shows that Cosmic Computers will build production plants in San Francisco, but not Denver. We can consider the effect of the tax on transportation by using parametric analysis:

param SFCost {DEMAND_NODES};

let {d in DEMAND_NODES} SFCost[d] := Cost['San Francisco', d];

option omit_zero_rows 1;
option omit_zero_cols 1;

for {t in 0.15..0.20 by 0.005} {
  let {d in DEMAND_NODES} Cost['San Francisco', d] := (1 + t) * SFCost[d];
  solve;
  
  printf "Tax rate = %g\%\n", t * 100;
  display Build, Flow;
}

We can perform a similar parametric analysis on BuildCost['Denver'] to find the maximum price that will result in construction in Denver (and hence how much of a tax rebate the Denver mayor would have to offer).

PRESENTATION OF SOLUTION AND ANALYSIS

Your management summary should contain:

1. A brief summary of the problem description;
2. A construction plan for the plants;
3. A transportation plan that describes the shipments from plants to stores;
4. A description of your post-optimal analysis:

• A brief description of the analysis undertaken (and why);
• A summary of the results of your analysis;

IMPLEMENTATION AND ONGOING MONITORING

Before implementation, sensitivity analysis of both the fixed and transportation costs could identify any data that needs to be confirmed before proceeding. This could also identify any problems should construction costs run over budget.

Ongoing monitoring of the transportation costs, production levels (supply) and demands will produce optimal shiiping plans. If the fixed cost at any plant rises significantly, relocation may be considered (this can also take the form of a facility location problem).| |*FORM FIELD ExtraForExperts*|ExtraForExperts|Another form of branch and bound implements branches on constraints that should take integer values. For example, in The Computer Plant 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. Remove the fractional part by forcing this 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 ???LINK??? drop the Up constraint and branch down:

This solution still has fractional Build variables. We can use another constraint branch to continue searching from this node:

| |*FORM FIELD StudentTasks*|StudentTasks| 1 Solve The Computer Plant Problem. Write a management summary of your solution. Be sure to answer all the questions in the problem description.

What to hand in Hand in your management summary.

EXTRA FOR EXPERTS' TASKS

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

<-- Under Construction -->

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

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.

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

<-- Under Construction -->

<-- Under Construction -->

Operations Research Topics: IntegerProgramming, MasterSlaveConstraints, FacilityLocationProblem

Application Areas: Industrial Planning

Contents

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:

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

Problem Formulation

Computational Model

Results

Conclusions

<-- Under Construction -->

Operations Research Topics: IntegerProgramming, MasterSlaveConstraints, FacilityLocationProblem

Application Areas: Industrial Planning

Contents

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:

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

Consider the Cosmic Computer company who 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:

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

There is a recycling tax being proposed by the San Francisco mayor that would place a tax rate of 15% to 20% of the transportation cost of any computers leaving San Francisco. Cosmic Computers have agreed that the recycling tax is a valid proposition, but are lobbying the mayor to keep it low. If the tax rate is too high they will not build a production plant (and create jobs) in San Francisco. What is the highest tax rate that will result in Cosmic Computers building a production plant in San Francisco?

The Denver mayor is very keen for Cosmic Computers to build a production plant in Denver. He has offered property tax rebates for Cosmic Computers if they build in Denver. What is maximum fixed cost for a production plant in Denver that will result in the construction of the plant?|