Deck 6: Integer Linear Programming

Question 1

A company wants to select 1 project from a set of 4 possible projects. Which of the following constraints ensures that only 1 will be selected?

A) X₁ + X₂ + X₃ + X₄ = 1
B) X₁ + X₂ + X₃ + X₄ $\le$ 1
C) X₁ + X₂ + X₃ + X₄ $\ge$ 1
D) X₁ + X₂ + X₃ + X₄ $\ge$ 0

Answer 1

X₁ + X₂ + X₃ + X₄ = 1

Question 2

How is the integer tolerance factor set in the Risk Solver Platform (RSP)?

A) By adding a constraint for the decision variables who's RHS is the desired suboptimality level.
B) By choosing the optimal option in the RSP Options dialog box.
C) By choosing the 100% Precision field in the RSP Options dialog box.
D) By entering the desired tolerance factor value in the Integer Tolerance field of RSP.

Answer 2

D

Question 3

What does the Risk Solver Platform (RSP) default integer tolerance factor of 0 accomplish?

A) Stops B & B after 100% of all solutions are examined.
B) Stops B & B when any feasible ILP solution is 0% from the current ILP solution.
C) Stops B & B when the true optimal integer solution has been found.
D) Stops B & B when no more than 0% of the changing cells have integer values.

Answer 3

C

Question 4

How is an LP problem changed into an ILP problem?

A) by adding constraints that the decision variables be non-negative.
B) by adding integrality conditions.
C) by adding discontinuity constraints.
D) by making the RHS values integer.

Question 5

Which of the following are potential pitfalls of using a non-zero integer tolerance factor in the Risk Solver Platform (RSP)?

A) No assurance the returned solution is optimal.
B) No assurance the returned solution is integer.
C) The true optimal solution may be worse than the returned solution.
D) There are no pitfalls to consider since the Solver will obtain solutions quicker.

Question 6

Which of the following is not a benefit of using binary variables?

A) With only 2 values, Solver can work faster.
B) Binary variables are useful in selection problems.
C) Binary variables can replace some IF() conditions.
D) Binary variables can enforce logical conditions.

Question 7

The objective function value for the ILP problem can never

A) be as good as the optimal solution to its LP relaxation.
B) be as poor as the optimal solution to its LP relaxation.
C) be worse than the optimal solution to its LP relaxation.
D) be better than the optimal solution to its LP relaxation.

Question 8

In the B & B algorithm, B & B stands for

A) Brooks and Baker
B) Best Bound
C) Best Branch
D) Branch and Bound

Question 9

Consider the constraint X₃ + X₄ + X₅ + X₆ + X₇ $\ge$ 27
Representing Air Express' Monday minimum worker requirement. Why was a " $\ge$ " used versus an "="?

A) The " $\ge$ " is needed to accommodate workers held over from Sunday.
B) Solver only accepts " $\ge$ " constraints.
C) The " $\ge$ " is less restrictive.
D) The "=" will always produce an infeasible constraint.

Question 10

A company wants to select no more than 2 projects from a set of 4 possible projects. Which of the following constraints ensures that no more than 2 will be selected?

A) X₁ + X₂ + X₃ + X₄ = 2
B) X₁ + X₂ + X₃ + X₄ $\le$ 2
C) X₁ + X₂ + X₃ + X₄ $\ge$ 2
D) X₁ + X₂ + X₃ + X₄ $\ge$ 0

Question 11

How are binary variables specified in the Risk Solver Platform (RSP)?

A) By replacing RHS values in constraints with 0 or 1.
B) By specifying changing cells as INTEGER and as non-negative.
C) By specifying changing cells as BINARY in the Variable Type/Bound area of RSP.
D) By selecting Assume Binary Model in the RSP Options dialog box.

Question 12

How are general integrality requirements indicated in the Excel Risk Solver Platform (RSP)?

A) Specifying the INT option for the appropriate changing cells.
B) Specifying the INT option for the constraint rows.
C) Adding additional RHS values to constraints.
D) Choosing the BIN setting in the Value field in the Solver Parameters dialog box.

Question 13

An ILP problem has 5 binary decision variables. How many possible integer solutions are there to this problem?

A) 5
B) 10
C) 25
D) 32

Question 14

For minimization problems, the optimal objective function value to the LP relaxation provides what for the optimal objective function value of the ILP problem?

A) An upper bound.
B) A lower bound.
C) An alternative optimal solution.
D) An additional constraint for the ILP problem.

Question 15

Variables, which are not required to assume strictly integer values are referred to as

A) strictly non-integer.
B) continuous.
C) discrete.
D) infinite.

Question 16

For maximization problems, the optimal objective function value to the LP relaxation provides what for the optimal objective function value of the ILP problem?

A) An upper bound.
B) A lower bound.
C) An alternative optimal solution.
D) An additional constraint for the ILP problem.

Question 17

An integrality condition indicates that some (or all) of the

A) RHS values for constraints must be integer
B) objective function coefficients must be integer
C) constraint coefficients must be integer
D) decision variables must be integer

Question 18

The LP relaxation of an ILP problem

A) always encompasses all the feasible integer solutions to the original ILP problem.
B) encompasses at least 90% of the feasible integer solutions to the original ILP problem.
C) encompasses different set of feasible integer solutions to the original ILP problem.
D) will not contain the feasible integer solutions to the original ILP problem.

Question 19

One approach to solving integer programming problems is to ignore the integrality conditions and solve the problem with continuous decision variables. This is referred to as

A) quickest solution method.
B) LP satisficing.
C) LP relaxation.
D) LP approximation.

Question 20

The B & B algorithm solves ILP problems

A) by solving for each variable separately.
B) by solving for the integer variables first.
C) by solving a series of LP problems.
D) by solving smaller ILP problems.

Question 21

A production company wants to ensure that if Product 1 is produced, production of Product 1 not exceed production of Product 2. Which of the following constraints enforce this condition?

A) X₁ $\ge$ M₂Y₂
B) X₁ $\le$ M₂X₂
C) X₁ $\le$ M₁Y₁, X₁ $\le$ Y₁X₂
D) X₁ $\le$ X₂

Question 22

Any integer variable in an ILP that assumes a fractional value in the optimal solution to the relaxed LP problem can be designated

A) a diverging variable.
B) a branching variable.
C) a bifurcating variable.
D) a splitting variable.

Question 23

A company is developing its weekly production plan. The company produces two products, A and B, which are processed in two departments. Setting up each batch of A requires $60 of labor while setting up a batch of B costs $80. Each unit of A generates a profit of $17 while a unit of B earns a profit of $21. The company can sell all the units it produces. The data for the problem are summarized below. $\quad$ $\quad$ $\quad$ $\quad$$\text { Hours required by }$
$\begin{array}{lccc}\text { Operation } & \text { A } & \text { B } & \text { Hours } \\\hline \text { Cutting } & 3 & 4 & 48 \\\text { Welding } & 2 & 1 & 36\end{array}$ The decision variables are defined as
X_i = the amount of product i produced
Y_i = 1 if X_i > 0 and 0 if X_i = 0
What is the appropriate value for M₁ in the linking constraint for product A?

A) 2
B) 3
C) 16
D) 12

Question 24

The branch-and-bound algorithm starts by

A) relaxing all the integrality conditions in an ILP and solving the resulting LP problem.
B) relaxing all the RHS values in an ILP and solving the resulting LP problem.
C) solving two LP problems in which X₁ is set at 0 and 1 respectively.
D) determining the most likely RHS values and solving for them.

Question 25

A company will be able to obtain a quantity discount on component parts for its three products, X₁, X₂ and X₃ if it produces beyond certain limits. To get the X₁ discount it must produce more than 50 X₁'s. It must produce more than 60 X₂'s for the X₂ discount and 70 X₃'s for the X₃ discount. Which of the following pair of constraints enforces the quantity discount relationship on X₃?

A) X₃₁ $\le$ M₃Y₃, X₃₂ $\ge$ 50Y₃
B) X₃₁ $\le$ M₃Y₃, X₃₁ $\ge$ 50
C) X₃₂ $\ge$ (1/50)X₃₁, X₃₁ $\le$ 50
D) X₃₂ $\le$ M₃Y₃, X₃₁ $\ge$ 50Y₃

Question 26

The setup cost incurred in preparing a machine to produce a batch of product is an example of a

A) fixed charge.
B) random charge.
C) sunk cost.
D) variable cost.

Question 27

A company is planning next month's production. It has to pay a setup cost to produce a batch of X₄'s so if it does produce a batch it wants to produce at least 100 units. Which of the following pairs of constraints show the relationship(s) between the setup variable Y₄ and the production quantity variable X₄?

A) X₄ $\le$ M₄Y₄, X₄ $\ge$ 100
B) X₄ $\le$ M₄Y₄, X₄ = 100 Y₄
C) X₄ $\le$ M₄Y₄, X₄ $\ge$ 100 Y₄
D) X₄ $\le$ M₄Y₄, X₄ $\le$ 100 Y₄

Question 28

If a company produces Product 1, then it must produce at least 150 units of Product 1. Which of the following constraints enforces this condition?

A) X₁ $\le$ 150Y₁
B) X₁ -150Y₁ $\ge$ 0
C) X₁Y₁ $\le$ 150
D) X₁ F $\ge$ 150 + Y₁

Question 29

The optimal relaxed solution for an ILP has X₁ = 3.6 and X₂ = 2.9. If we branch on X₁, what constraints must be added to the two resulting LP problems?

A) X₁ $\ge$ 3, X₁ $\ge$ 4
B) X₁ = 4
C) 3 $\le$ X₁, X₁ $\le$ 4
D) X₁ $\le$ 3, X₁ $\ge$ 4

Question 30

A company will be able to obtain a quantity discount on component parts for its three products, X₁, X₂ and X₃ if it produces beyond certain limits. To get the X₁ discount it must produce more than 50 X₁'s. It must produce more than 60 X₂'s for the X₂ discount and 70 X₃'s for the X₃ discount. How many binary variables are required in the formulation of this problem?

A) 3
B) 6
C) 9
D) 12

Question 31

A company is developing its weekly production plan. The company produces two products, A and B, which are processed in two departments. Setting up each batch of A requires $60 of labor while setting up a batch of B costs $80. Each unit of A generates a profit of $17 while a unit of B earns a profit of $21. The company can sell all the units it produces. The data for the problem are summarized below. $\quad$ $\quad$ $\quad$ $\quad$$\text { Hours required by }$
$\begin{array}{lccc}\text { Operation } & \text { A } & \text { B } & \text { Hours } \\\hline \text { Cutting } & 3 & 4 & 48 \\\text { Welding } & 2 & 1 & 36\end{array}$
The decision variables are defined as
X_i = the amount of product i produced
Y_i = 1 if X_i > 0 and 0 if X_i = 0
Which of the following constraints creates the link between setting up to produce A's and making some A's for this problem?

A) X₁ $\le$ 16Y₁
B) X₁ -Y₁ = 0
C) X₁- 18Y₁ > 0
D) = if(X₁ > 0, Y₁ = 1, Y₁ = 0)

Question 32

If a company selects either of Project 1 or Project 2 (or both), then either Project 3 or Project 4 (or both) must also be selected. Which of the following constraints enforce this condition?

A) X₁ + X₂ $\le$ 2(X₃ + X₄)
B) X₁ + X₂ $\le$ X₃ + X₄
C) X₁ -X₃ = X₂ - X₄
D) X₁ + X₂ + X₃ + X₄ $\le$ 2

Question 33

A wedding caterer has several wine shops from which it can order champagne. The caterer needs 100 bottles of champagne on a particular weekend for 2 weddings. The first supplier can supply either 40 bottles or 90 bottles. The relevant decision variable is defined as
X₁ = the number of bottles supplied by supplier 1
Which set of constraints reflects the fact that supplier 1 can supply only 40 or 90 bottles?

A) X₁ $\le$ 40 Y₁₁, X₁ $\le$ 90(1 - Y₁₁)
B) X₁ = 40Y₁₁ + 90Y₁₂, Y₁₁ + Y₁₂ $\le$ 1
C) X₁ = 40Y₁ + 90(1 - Y₁), Y₁ = 0 OR 1
D) X₁ = 40Y₁₁ + 90Y₁₂, Y₁₁ + Y₁₂ = 1

Question 34

A company is developing its weekly production plan. The company produces two products, A and B, which are processed in two departments. Setting up each batch of A requires $60 of labor while setting up a batch of B costs $80. Each unit of A generates a profit of $17 while a unit of B earns a profit of $21. The company can sell all the units it produces. The data for the problem are summarized below. $\quad$ $\quad$ $\quad$ $\quad$$\text { Hours required by }$
$\begin{array}{lccc}\text { Operation } & \text { A } & \text { B } & \text { Hours } \\\hline \text { Cutting } & 3 & 4 & 48 \\\text { Welding } & 2 & 1 & 36\end{array}$ What is the appropriate formula to use in cell E8 of the following Excel implementation of the ILP model for this problem?

A) =SUMPRODUCT(B5:C5,B7:C7) - SUMPRODUCT(B8:C8,B14:C14)
B) =SUMPRODUCT(B8:C8,B14:C14) - SUMPRODUCT(B5:C5,B7:C7)
C) =SUMPRODUCT(B5:C5,B7:C7) - B8:C8
D) =SUMPRODUCT(B5:C5,B7:C7) - SUMPRODUCT(B8:C8,B15:C15)

Question 35

A company is developing its weekly production plan. The company produces two products, A and B, which are processed in two departments. Setting up each batch of A requires $60 of labor while setting up a batch of B costs $80. Each unit of A generates a profit of $17 while a unit of B earns a profit of $21. The company can sell all the units it produces. The data for the problem are summarized below. $\quad$$\quad$$\quad$$\quad$$\text { Hours required by }$
$\begin{array}{lccc}\text { Operation } & \text { A } & \text { B } & \text { Hours } \\\hline \text { Cutting } & 3 & 4 & 48 \\\text { Welding } & 2 & 1 & 36\end{array}$
What is the appropriate formula to use in cell B15 of the following Excel implementation of the ILP model for this problem?

A) =B5- MIN($E$11/B11, $E$11/C11)*B14
B) =B5 -MIN($E$11/B11, $E$12/B12)
C) =B5- $E$12/B12*B14
D) =B5 - MIN($E$11/B11, $E$12/B12)*B14

Question 36

If a company selects Project 1 then it must also select either Project 2 or Project 3. Which of the following constraints enforces this condition?

A) X₁- X₂ - X₃ $\ge$ 0
B) X₁ + (X₂ - X₃) $\le$ 0
C) X₁ + X₂ + X₃ $\le$ 2
D) X₁ -X₂ -X₃ $\le$ 0

Question 37

A company must invest in project 1 in order to invest in project 2. Which of the following constraints ensures that project 1 will be chosen if project 2 is invested in?

A) X₁ + X₂ = 0
B) X₁ + X₂ = 1
C) X₁ -X₂ $\ge$ 0
D) X₁- X₂ $\le$ 0

Question 38

A manufacturing company has costs associated with production preparation and with per unit production. The per unit production costs are referred to as

A) decision variables.
B) production cost constraint coefficients.
C) variable costs.
D) marginal costs.

Question 39

A company is developing its weekly production plan. The company produces two products, A and B, which are processed in two departments. Setting up each batch of A requires $60 of labor while setting up a batch of B costs $80. Each unit of A generates a profit of $17 while a unit of B earns a profit of $21. The company can sell all the units it produces. The data for the problem are summarized below. $\quad$ $\quad$ $\quad$$\text { Hours required by }$
$\begin{array}{lccc}\text { Operation } & \text { A } & \text { B } & \text { Hours } \\\hline \text { Cutting } & 3 & 4 & 48 \\\text { Welding } & 2 & 1 & 36\end{array}$
The decision variables are defined as
X_i = the amount of product i produced
Y_i = 1 if X_i > 0 and 0 if X_i = 0
What is the objective function for this problem?

A) MAX: 17 X₁ + 21 X₂
B) MAX: 17 X₁ + 21 X₂ - 60 Y₁ - 80 Y₂
C) MIN: 17 X₁ + 21 X₂ -60 Y₁ - 80 Y₂
D) MIN: 60 Y₁ + 80 Y₂

Question 40

A company will be able to obtain a quantity discount on component parts for its three products, X₁, X₂ and X₃ if it produces beyond certain limits. To get the X₁ discount it must produce more than 50 X₁'s. It must produce more than 60 X₂'s for the X₂ discount and 70 X₃'s for the X₃ discount. How many decision variables are required in the formulation of this problem?

A) 3
B) 6
C) 9
D) 12

Question 41

A company wants to build a new factory in either Atlanta or Columbia. It is also considering building a warehouse in whichever city is selected for the new factory. The following table shows the net present value (NPV) and cost of each facility. The company wants to maximize the net present value of its facilities, but it only has $15 million to invest.
Formulate the ILP for this problem.

Question 42

A sub-problem in a B & B is solved and found infeasible. Should the B & B algorithm continue further analysis on this candidate problem?

A) Yes, a feasible solution may be found when additional constraints are added.
B) Yes, removing a constraint in further analysis may restore feasibility.
C) No, adding more constraints will not restore problem feasibility.
D) No, the result cannot occur so re-examine the formulation and start over.

Question 43

An investor has $500,000 to invest and wants to maximize the money they will receive at the end of one year. They can invest in condos, apartments and houses. The profit after one year, the cost and the number of units available are shown below.
Based on this ILP formulation of the problem and the indicated optimal integer solution values what values should go in cells B5:F12 of the following Excel spreadsheet?

Question 44

A small town wants to build some new recreational facilities. The proposed facilities include a swimming pool, recreation center, basketball court and baseball field. The town council wants to provide the facilities which will be used by the most people, but faces budget and land limitations. The town has $400,000 and 14 acres of land. The pool requires locker facilities which would be in the recreation center, so if the swimming pool is built the recreation center must also be built. Also the council has only enough flat land to build the basketball court or the baseball field. The daily usage and cost of the facilities (in $1,000) are shown below.
Based on this ILP formulation of the problem and the indicated optimal solution what values should go in cells B5:G12 of the following Excel spreadsheet?

Question 45

A company wants to build a new factory in either Atlanta or Columbia. It is also considering building a warehouse in whichever city is selected for the new factory. The following table shows the net present value (NPV) and cost of each facility. The company wants to maximize the net present value of its facilities, but it only has $15 million to invest.
Based on this ILP formulation of the problem and the indicated optimal solution what values should go in cells B6:G14 of the following Excel spreadsheet?

Question 46

Exhibit 6.1
The following questions pertain to the problem, formulation, and spreadsheet implementation below.
A research director must pick a subset of research projects to fund over the next five years. He has five candidate projects, not all of which cover the entire five-year period. Although the director has limited funds in each of the next five years, he can carry over unspent research funds into the next year. Additionally, up to $30K can be carried out of the five-year planning period. The following table summarizes the projects and budget available to the research director.
The following is the ILP formulation and a spreadsheet model for the problem.

Refer to Exhibit 6.1. What values would you enter in the Risk Solver Platform (RSP) task pane for the above Excel spreadsheet?
Objective Cell:
Variables Cells:
Constraints Cells:

Question 47

A city wants to locate 2 new fire fighting ladder trucks to maximize the number of tall buildings which they can cover within a 3 minute response time. The city is divided into 4 zones. The fire chief wants to locate no more than one of the trucks in either Zone 1 or Zone 2. The number of tall buildings in each zone and the travel time between zones is listed below.
Formulate the ILP for this problem.

Question 48

A company wants to build a new factory in either Atlanta or Columbia. It is also considering building a warehouse in whichever city is selected for the new factory. The following table shows the net present value (NPV) and cost of each facility. The company wants to maximize the net present value of its facilities, but it only has $16 million to invest.
Based on this ILP formulation of the problem what is the optimal solution to the problem?

Question 49

Exhibit 6.1
The following questions pertain to the problem, formulation, and spreadsheet implementation below.
A research director must pick a subset of research projects to fund over the next five years. He has five candidate projects, not all of which cover the entire five-year period. Although the director has limited funds in each of the next five years, he can carry over unspent research funds into the next year. Additionally, up to $30K can be carried out of the five-year planning period. The following table summarizes the projects and budget available to the research director.
The following is the ILP formulation and a spreadsheet model for the problem.

Refer to Exhibit 6.1. What formula should go in cell D15 of the above Excel spreadsheet?

Question 50

A city wants to locate 2 new fire fighting ladder trucks to maximize the number of tall buildings which they can cover within a 3 minute response time. The city is divided into 4 zones. The fire chief wants to locate no more than one of the trucks in either Zone 1 or Zone 2. The number of tall buildings in each zone and the travel time between zones is listed below.
Based on this ILP formulation of the problem what values should go in cells B5:G24 of the following Excel spreadsheet?
Let X_i = 1 if truck located in zone i, 0 otherwise

Question 51

An investor has $500,000 to invest and wants to maximize the money they will receive at the end of one year. They can invest in condos, apartments and houses. The profit after one year, the cost and the number of units available are shown below.
Formulate the ILP for this problem.

Question 52

A company has four projects, numbered 1 through 4. If any project is selected for implementation, each lower-numbered project must also be selected for implementation. Formulate the constraints to enforce these conditions.

Question 53

An investor has $500,000 to invest and wants to maximize the money they will receive at the end of one year. They can invest in condos, apartments and houses. The profit after one year, the cost and the number of units available are shown below.
Based on this ILP formulation of the problem what formulas should go in cells E5:E12 of the following Excel spreadsheet?

Question 54

Exhibit 6.1
The following questions pertain to the problem, formulation, and spreadsheet implementation below.
A research director must pick a subset of research projects to fund over the next five years. He has five candidate projects, not all of which cover the entire five-year period. Although the director has limited funds in each of the next five years, he can carry over unspent research funds into the next year. Additionally, up to $30K can be carried out of the five-year planning period. The following table summarizes the projects and budget available to the research director.
The following is the ILP formulation and a spreadsheet model for the problem.

Refer to Exhibit 6.1. What formulas should go in cells D8:H8 and D11:H11 of the above Excel spreadsheet?

Question 55

A company wants to build a new factory in either Atlanta or Columbia. It is also considering building a warehouse in whichever city is selected for the new factory. The following table shows the net present value (NPV) and cost of each facility. The company wants to maximize the net present value of its facilities, but it only has $16 million to invest.
Based on this ILP formulation of the problem and the indicated optimal solution what formulas should go in cells F6:F14 of the following Excel spreadsheet?

Question 56

A research director must pick a subset of research projects to fund over the next five years. He has five candidate projects, not all of which cover the entire five-year period. Although the director has limited funds in each of the next five years, he can carry over unspent research funds into the next year. Additionally, up to $30K can be carried out of the five-year planning period. The following table summarizes the projects and budget available to the research director.
Define the ILP formulation for this capital budgeting problem.

Question 57

A city wants to locate 2 new fire fighting ladder trucks to maximize the number of tall buildings which they can cover within a 3 minute response time. The city is divided into 4 zones. The fire chief wants to locate no more than one of the trucks in either Zone 1 or Zone 2. The number of tall buildings in each zone and the travel time between zones is listed below.
Based on this ILP formulation of the problem what formulas should go in cells B13:B16, B20:E20, F20, and F23:F24 of the following Excel spreadsheet?
Let X_i = 1 if truck located in zone i, 0 otherwise

Question 58

A small town wants to build some new recreational facilities. The proposed facilities include a swimming pool, recreation center, basketball court and baseball field. The town council wants to provide the facilities which will be used by the most people, but faces budget and land limitations. The town has $400,000 and 14 acres of land. The pool requires locker facilities which would be in the recreation center, so if the swimming pool is built the recreation center must also be built. Also the council has only enough flat land to build the basketball court or the baseball field. The daily usage and cost of the facilities (in $1,000) are shown below.
Formulate the ILP for this problem.

Question 59

A small town wants to build some new recreational facilities. The proposed facilities include a swimming pool, recreation center, basketball court and baseball field. The town council wants to provide the facilities which will be used by the most people, but faces budget and land limitations. The town has $400,000 and 14 acres of land. The pool requires locker facilities which would be in the recreation center, so if the swimming pool is built the recreation center must also be built. Also the council has only enough flat land to build the basketball court or the baseball field. The daily usage and cost of the facilities (in $1,000) are shown below.
Based on this ILP formulation of the problem what formulas should go in cells F5:F12 of the following Excel spreadsheet?

Question 60

A company needs to hire workers to cover a 7 day work week. Employees work 5 consecutive days with 2 days off. The demand for workers by day of the week and the wages per shift are:
Formulate the ILP for this problem.

Question 61

The following ILP is being solved by the branch and bound method. You have been given the initial relaxed IP solution. Complete the entries for the 3 nodes and label the arcs when you branch on X₁.
Initial solution
X₁ = 4.6X₂ = 1.6
Obj = 233.9

Question 62

A company produces three products which must be painted, assembled, and inspected. The machinery must be cleaned and adjusted before each batch is produced. They want to maximize their profits for the amount of operating time they have. The unit profit and setup cost per batch are:
The operation time per unit and total operating hours available are:
Formulate the ILP for this problem.

Question 63

A cellular phone company wants to locate two new communications towers to cover 4 regions. The company wants to minimize the cost of installing the two towers. The regions that can be covered by each tower site are indicated by a 1 in the following table:
Based on this ILP formulation of the problem and the solution (X₁, X₂, X₃, X₄) = (1, 1, 0, 0) what values should go in cells B6:G14 of the following Excel spreadsheet?

Question 64

The following ILP is being solved by the branch and bound method. You have been given the initial relaxed IP solution. Complete the entries for the 3 nodes and label the arcs when you branch on X2.
Initial solution
X₁ = 5.0
X₂ = 7.5
Obj = 550

Question 65

Exhibit 6.2
The following questions pertain to the problem, formulation, and spreadsheet implementation below.
A certain military deployment requires supplies delivered to four locations. These deliveries come from one of three ports. Logistics planners wish to deliver the supplies in an efficient manner, in this case by minimizing total ton-miles. The port-destination data, along with destination demand is provided in the following table.
The ports are supplied by one of two supply ships. These ships travel to a particular port where their supplies are off-loaded and shipped to the requesting destinations. Ship S1 carries 1200 tones of supplies while Ship S2 carries 1120 tons of supplies. These ships can only go to a single port and each port can only accommodate one ship. Assume the costs for a ship to travel to a port are not part of the objective function.
The following is the ILP formulation and a spreadsheet model for the problem.

Refer to Exhibit 6.2. What formula would go into cells B11:E11 and cells F8:F10?

Question 66

Exhibit 6.2
The following questions pertain to the problem, formulation, and spreadsheet implementation below.
A certain military deployment requires supplies delivered to four locations. These deliveries come from one of three ports. Logistics planners wish to deliver the supplies in an efficient manner, in this case by minimizing total ton-miles. The port-destination data, along with destination demand is provided in the following table.
The ports are supplied by one of two supply ships. These ships travel to a particular port where their supplies are off-loaded and shipped to the requesting destinations. Ship S1 carries 1200 tones of supplies while Ship S2 carries 1120 tons of supplies. These ships can only go to a single port and each port can only accommodate one ship. Assume the costs for a ship to travel to a port are not part of the objective function.
The following is the ILP formulation and a spreadsheet model for the problem.

Refer to Exhibit 6.2. What formula would go into cells G8:G10?

Question 67

A company produces three products which must be painted, assembled, and inspected. The machinery must be cleaned and adjusted before each batch is produced. They want to maximize their profits for the amount of operating time they have. The unit profit and setup cost per batch are:
The operation time per unit and total operating hours available are:
Based on this ILP formulation of the problem and the optimal solution (X₁, X₂, X₃) = (270, 0, 0), what values should appear in the shaded cells in the following Excel spreadsheet?
X_i = amount of product i produced
Y_i = 1 if product i produced, 0 otherwise

Question 68

A company needs to hire workers to cover a 7 day work week. Employees work 5 consecutive days with 2 days off. The demand for workers by day of the week and the wages per shift are:
Based on this ILP formulation of the problem and the optimal solution (X₁, X₂, X₃, X₄, X₅, X₆) = (2, 10, 16, 6, 14, 8, 6) what values should go in cells B5:J13 of the following Excel spreadsheet?

Question 69

A cellular phone company wants to locate two new communications towers to cover 4 regions. The company wants to minimize the cost of installing the two towers. The regions that can be covered by each tower site are indicated by a 1 in the following table:
Based on this ILP formulation of the problem what formulas should go in cells F6:F14 of the following Excel spreadsheet?

Question 70

Exhibit 6.2
The following questions pertain to the problem, formulation, and spreadsheet implementation below.
A certain military deployment requires supplies delivered to four locations. These deliveries come from one of three ports. Logistics planners wish to deliver the supplies in an efficient manner, in this case by minimizing total ton-miles. The port-destination data, along with destination demand is provided in the following table.
The ports are supplied by one of two supply ships. These ships travel to a particular port where their supplies are off-loaded and shipped to the requesting destinations. Ship S1 carries 1200 tones of supplies while Ship S2 carries 1120 tons of supplies. These ships can only go to a single port and each port can only accommodate one ship. Assume the costs for a ship to travel to a port are not part of the objective function.
The following is the ILP formulation and a spreadsheet model for the problem.

Refer to Exhibit 6.2. What formula would go into cell E14?

Question 71

A certain military deployment requires supplies delivered to four locations. These deliveries come from one of three ports. Logistics planners wish to deliver the supplies in an efficient manner, in this case by minimizing total ton-miles. The port-destination data, along with destination demand is provided in the following table.
The ports are supplied by one of two supply ships. These ships travel to a particular port where their supplies are off-loaded and shipped to the requesting destinations. Ship S1 carries 1200 tones of supplies while Ship S2 carries 1120 tons of supplies. These ships can only go to a single port and each port can only accommodate one ship. Assume the costs for a ship to travel to a port are not part of the objective function.
Formulate the ILP for this problem capturing the ship choice of ports and the supply-to-demand transportation from the ports to the destinations.

Question 72

A cellular phone company wants to locate two new communications towers to cover 4 regions. The company wants to minimize the cost of installing the two towers. The regions that can be covered by each tower site are indicated by a 1 in the following table:
Formulate the ILP for this problem.