Deck 6: Integer Linear Programming

Question 1

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

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

Answer 1

D

Question 2

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.

Answer 2

A

Question 3

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.

Answer 3

C

Question 4

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 5

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 6

What does the Analytic Solver Platform 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.

Question 7

Which of the following are potential pitfalls of using a non-zero integer tolerance factor in the Analytic Solver Platform?

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 8

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 9

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 10

How are general integrality requirements indicated in the Analytic Solver Platform?

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 11

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 12

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 13

How is the integer tolerance factor set in the Analytic Solver Platform ASP)?

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 ASP Options dialog box.
C)By choosing the 100% Precision field in the ASP Options dialog box.
D)By entering the desired tolerance factor value in the Integer Tolerance field of ASP.

Question 14

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₄ ≤ 2
C)X₁ + X₂ + X₃ + X₄ ≥ 2
D)X₁ + X₂ + X₃ + X₄ ≥ 0

Question 15

What are binary integer variables?

A)Variables with any two values,a and b.
B)Variables with values 0 and 1.
C)Variables whose sum of digits is 2.
D)Variables with values between 0 and 1.

Question 16

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

How are binary variables specified in the Analytic Solver Platform ASP)?

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 ASP.
D)By selecting Assume Binary Model in the ASP Options dialog box.

Question 19

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

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

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 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.
Hours required by
$$\begin{array} { r c c c } \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₁ ? 16Y₁ b.X₁ ? Y₁ = 0
B)X₁ ? 18Y₁ > 0
C)= ifX₁ > 0,Y₁ = 1,Y₁ = 0)

Question 22

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 23

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₃₁ ≤ M₃Y₃,X₃₂ ≥ 50Y₃ b.X₃₁ ≤ M₃Y₃,X₃₁ ≥ 50
C)X₃₂ ≥ 1/50)X₃₁,X₃₁ ≤ 50
D)X₃₂ ≤ M₃Y₃,X₃₁ ≥ 50Y₃

Question 24

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 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.How many binary variables are required in the formulation of this problem?

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

Question 26

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₁ ≤ 150Y₁
B)X₁ − 150Y₁ ≥ 0
C)X₁Y₁ ≤ 150
D)X₁ ≥ 150 + Y₁

Question 27

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₄ ≤ 1
C)X₁ + X₂ + X₃ + X₄ ≥ 1
D)X₁ + X₂ + X₃ + X₄ ≥ 0

Question 28

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₂ ≤ 2X₃ + X₄)
B)X₁ + X₂ ≤ X₃ + X₄
C)X₁ − X₃ = X₂ − X₄
D)X₁ + X₂ + X₃ + X₄ ≤ 2

Question 29

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.
Hours required by
$$\begin{array} { r c c c } \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 30

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 31

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 32

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.
Hours required by
$$\begin{array} { r c c c } \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 33

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.
Hours required by
$$\begin{array} { r c c c } \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
Using the approach discussed in the text,what is the appropriate value for M₁ in the linking constraint for product A?

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

Question 34

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 relationships)between the setup variable Y₄ and the production quantity variable X₄?

A)X₄ ≤ M₄Y₄,X₄ ≥ 100
B)X₄ ≤ M₄Y₄,X₄ = 100 Y₄ c.X₄ ≤ M₄Y₄,X₄ ≥ 100 Y₄ d.X₄ ≤ M₄Y₄,X₄ ≤ 100 Y₄

Question 35

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₃ ≥ 0
B)X₁ + X₂ − X₃)≤ 0
C)X₁ + X₂ + X₃ ≤ 2
D)X₁ − X₂ − X₃ ≤ 0

Question 36

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 37

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₁ ≥ M₂Y₂
B)X₁ ≤ M₂X₂
C)X₁ ≤ M₁Y₁,X₁ ≤ Y₁X₂
D)X₁ ≤ X₂

Question 38

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₁ ≤ 40 Y₁₁,X₁ ≤ 901 − Y₁₁)
B)X₁ = 40Y₁₁ + 90Y₁₂,Y₁₁ + Y₁₂ ≤ 1
C)X₁ = 40Y₁ + 901 − Y₁),Y₁ = 0 OR 1
D)X₁ = 40Y₁₁ + 90Y₁₂,Y₁₁ + Y₁₂ = 1

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.
Hours required by
$$\begin{array} { r c c c } \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)=SUMPRODUCTB5:C5,B7:C7)? SUMPRODUCTB8:C8,B14:C14)
B)=SUMPRODUCTB8:C8,B14:C14)? SUMPRODUCTB5:C5,B7:C7)
C)=SUMPRODUCTB5:C5,B7:C7)? B8:C8
D)=SUMPRODUCTB5:C5,B7:C7)? SUMPRODUCTB8:C8,B15:C15)

Question 40

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₂ ≥ 0
D)X₁ − X₂ ≤ 0

Question 41

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.
$$\begin{array}{c}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text { To zone }\\\begin{array} { c c c c c c } \text { No. tall buildings } & \text { Fram zone } & 1 & 2 & 3 & 4 \\\hline 50 & 1 & 0 & 2 & 1 & 6 \\90 & 2 & 2 & 0 & 4 & 5 \\60 & 3 & 1 & 4 & 0 & 1 \\70 & 4 & 6 & 5 & 1 & 0\end{array}\end{array}$$
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
$$\begin{array} { c c c } \text { Zone } & \text { Covers these zones } & \text { With the many building } \\\hline 1 & 1,2,3 & 200 \\2 & 1,2 & 140 \\3 & 1,3,4 & 180 \\4 & 3,4 & 130\end{array}$$
MAX: ^{200 X}₁ ^{+ 140 X}₂ ^{+ 180 X}₃ ^{+ 130 X}₄
Subject to: ^X₁ ^{+ X}₂ ^{+ X}₃ ^{+ X}₄ ^{= 2}
X₁ + X₂ ? 1
X_i = 0,1

Question 42

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.
Project Funds Required in $000s)Benefit
$\begin{array}{ccccccc}\text { Project } & 1 & 2 & 3 & 4 & 5 & \text { in } \$ 000 s) \\\hline 1 & \$ 70 & \$ 40 & \$ 30 & \$ 15 & \$ 15 & \$ 160 \\2 & \$ 82 & \$ 35 & \$ 20 & \$ 20 & \$ 10 & \$ 190 \\3 & \$ 55 & \$ 10 & \$ 10 & \$ 5 & & \$ 125 \\4 & \$ 69 & \$ 17 & \$ 15 & \$ 12 & \$ 8 & \$ 139 \\5 & \$ 75 & \$ 20 & \$ 25 & \$ 30 & \$ 45 & \$ 174 \\\hline\end{array}$
Budget $225K $60K $60K $50K $50K The following is the ILP formulation and a spreadsheet model for the problem.
Let ^X_i ^{= 0 if project i not selected,1 if project i selected for i = 1,2,3,4,5}
C_j = amount carried out of year j,j = 1,2,3,4,5
MAX ^160X₁ ^{+ 190X}₂ ^{+ 125X}₃ ^+139X₄ ^{+ 174X}₅ Subject to: ^70X₁ ^{+ 82X}₂ ^{+ 55X}₃ ^{+ 69X}₄ ^{+ 75X}₅ ^{+ C}₁ ^{= 225}
40X₁ + 35X₂ + 10X₃ + 17X₄ + 20X₅ + C₂ = 60 + C₁
30X₁ + 20X₂ + 10X₃ + 15X₄ + 25X₅ + C₃ = 60 + C₂
15X₁ + 20X₂ + 5X₃ + 12X₄ + 30X₅ + C₄ = 50 + C₃
15X₁ + 10X₂ + 8X₄ + 45X₅ + C₅ = 50 + C₄ C₅ ? 30
X_i binary,C₁,C₂,C₃,C₄,C₅ ? 0


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

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.
$\begin{array}{rrrrr}&&\text { Profit}&\text { Cost }&\text { Number }\\\text { Variable } & \text { Investment } & \$ 1,000) & \$ 1,000) & \text { Available } \\\hline \mathrm{X}_{1} & \text { Condos } & 6 & 50 & 10 \\\mathrm{X}_{2} & \text { Apartments } & 12 & 90 & 5 \\\mathrm{X}_{3} & \text { Houses } & 9 & 100 & 7\end{array}$
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?
MAX: ^{6 X}₁ ^{+ 12 X}₂ ^{+ 9 X}₃
Subject to: ^{50 X}₁ ^{+ 90 X}₂ ^{+ 100 X}₃ ^{? 500}
X₁ ? 10
X₂ ? 5
X₃ ? 7
X_i ? 0 and integer

Question 44

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.
$$\begin{array}{c}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \text { To zone }\\\begin{array} { c c c c c c } \text { No. tall buildings } & \text { Fram zone } & 1 & 2 & 3 & 4 \\\hline 50 & 1 & 0 & 2 & 1 & 6 \\90 & 2 & 2 & 0 & 4 & 5 \\60 & 3 & 1 & 4 & 0 & 1 \\70 & 4 & 6 & 5 & 1 & 0\end{array}\end{array}$$

Question 45

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.
Project Funds Required in $000s)Benefit
$\begin{array}{ccccccc}\text { Project } & 1 & 2 & 3 & 4 & 5 & \text { in } \$ 000 s) \\\hline 1 & \$ 70 & \$ 40 & \$ 30 & \$ 15 & \$ 15 & \$ 160 \\2 & \$ 82 & \$ 35 & \$ 20 & \$ 20 & \$ 10 & \$ 190 \\3 & \$ 55 & \$ 10 & \$ 10 & \$ 5 & & \$ 125 \\4 & \$ 69 & \$ 17 & \$ 15 & \$ 12 & \$ 8 & \$ 139 \\5 & \$ 75 & \$ 20 & \$ 25 & \$ 30 & \$ 45 & \$ 174 \\\hline\end{array}$
Budget $225K $60K $60K $50K $50K 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 Analytic Solver Platform task pane for the above Excel spreadsheet?
Objective Cell: Variables Cells: Constraints Cells:

Question 46

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.
$$\begin{array} { r r r r r } \text { Variable } & \text { Facilty } & \text { Usage } & \text { Cost \$1,000) } & \text { Land } \\\hline \mathbf { x } _ { 1 } & \text { Swimruine pool } & 400 & 100 & 2 \\\mathbf { x } _ { 2 } & \text { Recreation center } & 500 & 200 & 3 \\\mathbf { x } _ { 3 } & \text { Basketball court } & 300 & 150 & 4 \\\mathbf { x } _ { 4 } & \text { Baseball field } & 200 & 100 & 5\end{array}$$

Question 47

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.
Variable Decision
NPV
$million)
Cost $million)
^X₁ Factory in Columbia 3 10
^X₂ Factory in Atlanta 4 8
^X₃ Warehouse in Columbia 2 6
^X₄ Warehouse in Atlanta 1 5
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?
MAX: ^{3 X}₁ ^{+ 4 X}₂ ^{+ 2 X}₃ ^{+ X}₄
Subject to: ^{10 X}₁ ^{+ 8 X}₂ ^{+ 6 X}₃ ^{+ 5 X}₄ ^{≤ 15}
X₁ + X₂ = 1 X₃ + X₄ ≤ 1 X₃ − X₁ ≤ 0 X₄ − X₂ ≤ 0 X_i = 0,1

Question 48

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₁ ≥ 3,X₁ ≥ 4
B)X₁ = 4
C)3 ≤ X₁,X₁ ≤ 4
D)X₁ ≤ 3,X₁ ≥ 4

Question 49

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.
Variable Decision
NPV
$million)
Cost $million)
^X₁ Factory in Columbia 3 10
^X₂ Factory in Atlanta 4 8
^X₃ Warehouse in Columbia 2 6
^X₄ Warehouse in Atlanta 1 5

Question 50

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 51

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 52

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.
Variable Decision
NPV
$million)
Cost $million)
^X₁ Factory in Columbia 3 10
^X₂ Factory in Atlanta 4 8
^X₃ Warehouse in Columbia 2 6
^X₄ Warehouse in Atlanta 1 5
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?
MAX: ^{3 X}₁ ^{+ 4 X}₂ ^{+ 2 X}₃ ^{+ X}₄
Subject to: ^{10 X}₁ ^{+ 8 X}₂ ^{+ 6 X}₃ ^{+ 5 X}₄ ^{≤ 15}
X₁ + X₂ = 1 X₃ + X₄ ≤ 1 X₃ − X₁ ≤ 0 X₄ − X₂ ≤ 0
X_i = 0,1

Question 53

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.
Variable Decision
NPV
$million)
Cost $million)
^X₁ Factory in Columbia 3 10
^X₂ Factory in Atlanta 4 8
^X₃ Warehouse in Columbia 2 6
^X₄ Warehouse in Atlanta 1 5
Based on this ILP formulation of the problem what is the optimal solution to the problem?
MAX: ^{3 X}₁ ^{+ 4 X}₂ ^{+ 2 X}₃ ^{+ X}₄
Subject to: ^{10 X}₁ ^{+ 8 X}₂ ^{+ 6 X}₃ ^{+ 5 X}₄ ^{≤ 15}
X₁ + X₂ = 1 X₃ + X₄ ≤ 1 X₃ − X₁ ≤ 0 X₄ − X₂ ≤ 0 X_i = 0,1

Question 54

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.
$\begin{array}{rrrrr}&&\text { Profit } & \text { Cost } & \text { Number } \\\text { Variable } & \text { Investment } &\$ 1,000)&\$ 1,000) & \text { Available }\\\hline \mathrm{X} 1 & \text { Condos } & 6 & 50 & 10 \\\mathrm{X} 2 & \text { Apartments } & 12 & 90 & 5 \\\mathrm{X} 3 & \text { Houses } & 9 & 1 \mathrm{nn} & 7\end{array}$
Based on this ILP formulation of the problem what formulas should go in cells E5:E12 of the following Excel spreadsheet?
MAX: ^{6 X}₁ ^{+ 12 X}₂ ^{+ 9 X}₃
Subject to: ^{50 X}₁ ^{+ 90 X}₂ ^{+ 100 X}₃ ^{? 500}
X₁ ? 10
X₂ ? 5
X₃ ? 7
Xi ? 0 and integer

Question 55

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:
$$\begin{array} { l c r r r } \text { Days af Week } & \text { Workers Required } & \text { Shift } & \text { Days off } & \text { Wage } \\\hline \text { Sunday } & 54 & 1 & \text { Sun a Man } & 900 \\\text { Munday } & 50 & 2 & \text { Man a Tue } & 1000 \\\text { Tuesday } & 36 & 3 & \text { Tue d Wed } & 1000 \\\text { Wednestay } & 38 & 4 & \text { Wed a Thur } & 1000 \\\text { Thursday } & 42 & 5 & \text { Thur a Fri } & 1000 \\\text { Friday } & 40 & 6 & \text { Fri a Sat } & 900 \\\text { Saturday } & 48 & 7 & \text { Sat a Sun } & 850\end{array}$$
Formulate the ILP for this problem.

Question 56

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.
$$\begin{array} { r r r r r } \text { Variable } & \text { Facilty } & \text { Usage } & \text { Cost \$1,000) } & \text { Land } \\\hline \mathbf { x } _ { 1 } & \text { Swimming pool } & 400 & 100 & 2 \\\mathbf { x } _ { 2 } & \text { Recreation center } & 500 & 200 & 3 \\\mathbf { x } _ { 3 } & \text { Basketball court } & 300 & 150 & 4 \\\mathbf { x } _ { 4 } & \text { Baseball field } & 200 & 100 & 5\end{array}$$
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?
$$\begin{array} { l l l } \text { MAX: } & 400 \mathbf { x } _ { 1 } + 500 \mathbf { x } _ { 2 } + 300 \mathbf { x } _ { 3 } + 200 \mathbf { x } _ { 4 } & \\\text { Subject ta: } & 100 \mathbf { x } _ { 1 } + 200 \mathbf { x } _ { 2 } + 150 \mathbf { x } _ { 3 } + 100 \mathbf { x } _ { 4 } \leq 400 & \text { budget } \\& 2 \mathbf { x } _ { 1 } + 3 \mathbf { x } _ { 2 } + 4 \mathbf { x } _ { 3 } + 5 \mathbf { x } _ { 4 } \leq 14 & \text { land } \\& \mathbf { x } _ { 1 } - \mathbf { x } _ { 2 } \leq 0 & \text { pool and recreation center } \\& \mathbf { x } _ { 3 } + \mathbf { x } _ { 4 } \leq 1 & \text { basketball and baseball } \\& \mathbf { x } _ { 1 } = 0.1 &\end{array}$$
Solution: $\left. \mathbf { x } _ { 1 } , \mathbf { x } _ { 2 } , \mathbf { x } _ { 3 } , \mathbf { X } _ { 4 } \right) = 1,1,0,1$ )

Question 57

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:
Tower Sites
$\begin{array}{rrrrr}\text { Region } & 1 & 2 & 3 & 4 \\\hline \text { A } & & 1 & & 1 \\\text { B } & 1 & & 1 & 1 \\\text { C } & 1 & 1 & 1 & \\\text { D } & 1 & & &1 \\\hline \text { COST } \$ 000 \text { s) } & 200 & 150 & 190 & 250\end{array}$

Formulate the ILP for this problem.

Question 58

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.
$\begin{array}{rrrrr}&&\text { Profit}&\text { Cost }&\text { Number }\\\text { Variable } & \text { Investment } & \$ 1,000) & \$ 1,000) & \text { Available } \\\hline \mathrm{X}_{1} & \text { Condos } & 6 & 50 & 10 \\\mathrm{X}_{2} & \text { Apartments } & 12 & 90 & 5 \\\mathrm{X}_{3} & \text { Houses } & 9 & 100 & 7\end{array}$

Question 59

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:
Tower Sites
$\begin{array}{rrrrr}\text { Region } & 1 & 2 & 3 & 4 \\\hline \text { A } & & 1 & & 1 \\\text { B } & 1 & & 1 & 1 \\\text { C } & 1 & 1 & 1 & \\\text { D } & 1 & & & 1\\\hline \text { COST } \$ 000 \text { s) } & 200 & 150 & 190 & 250\end{array}$
MIN: ^{200 X}₁ ^{+ 150 X}₂ ^{+ 190 X}₃ ^{+ 250 X}₄
Subject to: ^X₂ ^{+ X}₄ ^{? 1}
X₁ + X₃ + X₄ ? 1 X₁ + X₂ + X₃ ? 1 X₁ + X₄ ? 1
X₁ + X₂ + X₃ + X₄ = 2 X_i = 0,1
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 60

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:
Tower Sites
$\begin{array}{rrrrr}\text { Region } & 1 & 2 & 3 & 4 \\\hline \text { A } & & 1 & & 1 \\\text { B } & 1 & & 1 & 1 \\\text { C } & 1 & 1 & 1 &\\\text { D } & 1 & & & 1 \\\hline \text { COST } \$ 000 \text { s) } & 200 & 150 & 190 & 250\end{array}$
MIN: ^{200 X}₁ ^{+ 150 X}₂ ^{+ 190 X}₃ ^{+ 250 X}₄
Subject to: ^X₂ ^{+ X}₄ ^{? 1}
X₁ + X₃ + X₄ ? 1 X₁ + X₂ + X₃ ? 1 X₁ + X₄ ? 1
X₁ + X₂ + X₃ + X₄ = 2 X_i = 0,1
Based on this ILP formulation of the problem what formulas should go in cells F6:F14 of the following Excel spreadsheet?

Question 61

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.
$$\begin{array}{c}\text { Destination }\\\begin{array} { c r r r r } \text { Port } & \text { D1 } & \text { D2 } & \text { D3 } & \text { D4 } \\\hline \text {A}& 75 & 88 & 103 & 56 \\\text { B } & 105 & 76 & 101 & 85 \\\mathrm { C } & 43 & 80 & 95 & 62 \\\hline \text { Demand } & 500 & 600 & 450 & 700\end{array}\end{array}$$
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 62

Binary decision variables:

A)are either 0 or 1
B)must be integers
C)may be continuous
D)may be negative

Question 63

Suppose you want to minimize an objective function z=2x₁+3x₂.Both decision variables must be integer.The optimal solution to the LP relaxation will:

A)be smaller than the optimal IP solution
B)be larger than the optimal IP solution
C)can be either smaller or larger than the optimal IP solution
D)will be within 5% of the optimal IP solution value

Question 64

Suppose you want to maximize an objective function z=2x₁+3x₂.Both decision variables must be integer.The optimal solution to the LP relaxation will:

A)be smaller than the optimal IP solution
B)be larger than the optimal IP solution
C)can be either smaller or larger than the optimal IP solution
D)will be within 5% of the optimal IP solution value

Question 65

The concept of a lower bound in IP is associated with:

A)LP relaxation of a minimization problem
B)LP relaxation of a maximization problem
C)a cutting plane technique
D)explicit enumeration of corner point solutions

Question 66

Project 6.2 ? Dayton Electronics Manufacturing Inc.DEMI)
The Dayton Electronic Manufacturing,Inc DEMI)company manufactures two styles of remote keyless entry systems the X30 and the X40)that various auto dealers supply to customers when a new or used)automobile is purchased.DEMI currently operates four production facilities located in Springfield OH,Hartford,New Orleans,and Orlando.The manufactured items are shipped from the plants to regional distribution centers located in Trenton,Chicago and Seattle.It is from these regional locations that the product is distributed nationwide.
As more automobile manufactures include keyless entry as a standard option,and DEMI finds itself locked out of the manufacturer market,demand for DEMI's products have decreased.As a result,management is contemplating closing one or more of its production facilities.Distribution facilities are not currently being considered for closing.
Each production facility carries a fixed operating cost and a variable cost associated with building each of the products.Data has been compiled on production costs,resource availability,and resource usage at each of the production plants.That information is summarized in the table below.
$\begin{array}{ccccc}\text { Plant } & \begin{array}{l}\text { Fixed Cost Per } \\\text { Month } \$ 1000 \text { ) }\end{array} & \begin{array}{c}\text { Production } \\\text { Cost per } 100 \text { ) } \\\text { X } 30-\mathrm{X} 40\end{array} & \begin{array}{c}\text { Production } \\\text { Time } \mathrm{hr} / 100 \text { ) } \\\mathrm{X} 30-\mathrm{X} 40\end{array} & \begin{array}{c}\text { Available } \\\text { Hours } \\\text { per Month }\end{array} \\\hline \text { Springfield } & 53 & 1100 \quad 1300 & 6\quad6 & 720 \\ \text { Hartford } & 38 & 1100 \quad 1250 & 7\quad8 & 780 \\\text { New Orleans } & 25 & 10001000 & 5\quad5 & 530 \\ \text { Orlando } & 28 & 1200 \quad 1500 & 5\quad9 & 680 \\\end{array}$
The entry systems are sold nationwide at the same prices: $24 for the X30 and $30 for the X40.
Current monthly demand projections at each distribution center for both products are given in the following table.
$$\begin{array}{c}\text { Demand }\\\begin{array} { c c c c } & \text { Trenton } & \text { Chicago } & \text { Seattle } \\\hline X 30 & 2200 & 3100 & 4000 \\X 40 & 4500 & 5800 & 6000\end{array}\end{array}$$
The transportation costs between each plant and each distribution center,which are the same for either product,are shown in the following table:
$\text {Cost per 100}$ $\quad$$\quad$$\text {To}$

$\begin{array}{lccc}\text { From } & \text { Trenton } & \text { Chicago } & \text { Seattle } \\\hline \text { Springfield } & \$ 200 & \$ 270 & \$ 450 \\\text { Hartford } & \$ 100 & \$ 200 & \$ 700 \\\text { New Orleans } & \$ 250 & \$ 240 & \$ 300 \\\text { Orlando } & \$ 180 & \$ 220 & \$ 350\end{array}$
• Determine which of the plants to close and which to keep open.
• Determine the number of X30 and X40 to be produced at each plant.
• Determine a shipping pattern from the plants to the distribution centers.
• Maximize the net total monthly profit.If any plants were closed,what was the impact of the closing on profits?
• Do not exceed the production capacities at any plant.
Formulate DEMI's problem as a fixed charge,integer program.Implement your model in Excel and solve the model to answer DEMI's questions.

Question 67

A practical way of dealing with the complexity of IP problems is to:

A)stop searching for a better solution when the current best solution is within specified suboptimality tolerances
B)continue searching for the optimal solution until no further objective function improvement can be achieved
C)use a B&B technique
D)use LP relaxation and round the values of the decision variables to the nearest integers

Question 68

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:
$$\begin{array} { r r r } \text { Product } & \text { Profit per unit } & \text { Setup cost per batch } \\\hline 1 & 9 & 500 \\2 & 10 & 600 \\3 & 12 & 650\end{array}$$
The operation time per unit and total operating hours available are:
$$\begin{array}{c}\text { Operating Time per Unit }\\\begin{array} { l c c c c } \text { Operation } & \text { Product 1 } & \text { Product 2 } & \text { Product 3 } & \text { Operating Hours Available } \\\hline \text { Paint } & 1 & 2 & 2 & 400 \\\text { Assemble } & 2 & 3 & 2 & 600 \\\text { Inspection } & 2 & 4 & 3 & 540\end{array}\end{array}$$
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
MAX: ^{9 X}₁ ^{+ 10 X}₂ ^{+ 12 X}₃ ^{? 500 Y}₁ ^{? 600 Y}₂ ^{? 650 Y}₃
Subject to: ^{1 X}₁ ^{+ 2 X}₂ ^{+ 2 X}₃ ^{? 400}
2 X₁ + 3 X₂ + 2 X₃ ? 600
2 X₁ + 4 X₂ + 3 X₃ ? 540 X₁ ? M₁ Y₁ OR 270 Y₁ X₂ ? M₂ Y₂ OR 135 Y₂ X₃ ? M₃ Y₃ OR 180 Y₃ Y_i = 0,1
X_i ? 0 and integer

Question 69

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.
Destination
$$\begin{array} { r r r r r } \text { Port } & \text { D1 } & \text { D2 } & \text { D3 } & \text { D4 } \\\hline \text { A } & 75 & 88 & 103 & 56 \\\mathrm {~B} & 105 & 76 & 101 & 85 \\\mathrm { C } & 43 & 80 & 95 & 82 \\\hline \text { Demand } & 500 & 600 & 450 & 700\end{array}$$ 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.
Let ^Y_ij ^{be 1 if ship i travels to port j,for i = S1,S2 and j = A,B,C}
X_jk be the tons shipped from port j = A,B,C to Destination k = D1,D2,D3,D4
Minimize ^75X₁₁ ^{+ 88X}₁₂ ^{+ 103X}₁₃ ^{+ 56X}₁₄ ^{+ 105X}₂₁ ^{+ 76X}₂₂ ^{+ 101X}₂₃ ^{+ 85X}₂₄
+ 43X₃₁ + 80X₃₂ + 95X₃₃ + 62X₃₄
Subject to: ^Y₁₁ ^{+ Y}₂₁ ^{? 1}
Y₁₂ + Y₂₂ ? 1 Y₁₃ + Y₂₃ ? 1
Y₁₁ + Y₁₂ + Y₁₃ = 1 Y₂₁ + Y₂₂ + Y₂₃ = 1
X₁₄ + X₁₅ + X₁₆ + X₁₇ ? 1200Y₁₁ + 1120Y₂₁ X₂₄ + X₂₅ + X₂₆ + X₂₇ ? 1200Y₁₂ + 1120Y₂₂ X₃₄ + X₃₅ + X₃₆ + X₃₇ ? 1200Y₁₃ + 1120Y₂₃ X₁₄ + X₂₄ + X₃₄ ? 500
X₁₅ + X₂₅ + X₃₅ ? 600 X₁₆ + X₂₆ + X₃₆ ? 450 X₁₇ + X₂₇ + X₃₇ ? 700
Y_ij.X_jk ? 0


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

Question 70

The concept of an upper bound in IP is associated with:

A)LP relaxation of a minimization problem
B)LP relaxation of a maximization problem
C)a cutting plane technique
D)explicit enumeration of corner point solutions

Question 71

Pure IP formulation requires that:

A)all decision variables must be integer
B)the optimal objective function value must be integer
C)some decision variables must be integer
D)some decision variables and the optimal value of the objective function must be integer

Question 72

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.
Destination
$$\begin{array} { r r r r r } \text { Port } & \text { D1 } & \text { D2 } & \text { D3 } & \text { D4 } \\\hline \text { A } & 75 & 88 & 103 & 56 \\\mathrm {~B} & 105 & 76 & 101 & 85 \\\mathrm { C } & 43 & 80 & 95 & 82 \\\hline \text { Demand } & 500 & 600 & 450 & 700\end{array}$$ 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.
Let ^Y_ij ^{be 1 if ship i travels to port j,for i = S1,S2 and j = A,B,C}
X_jk be the tons shipped from port j = A,B,C to Destination k = D1,D2,D3,D4
Minimize ^75X₁₁ ^{+ 88X}₁₂ ^{+ 103X}₁₃ ^{+ 56X}₁₄ ^{+ 105X}₂₁ ^{+ 76X}₂₂ ^{+ 101X}₂₃ ^{+ 85X}₂₄
+ 43X₃₁ + 80X₃₂ + 95X₃₃ + 62X₃₄
Subject to: ^Y₁₁ ^{+ Y}₂₁ ^{? 1}
Y₁₂ + Y₂₂ ? 1 Y₁₃ + Y₂₃ ? 1
Y₁₁ + Y₁₂ + Y₁₃ = 1 Y₂₁ + Y₂₂ + Y₂₃ = 1
X₁₄ + X₁₅ + X₁₆ + X₁₇ ? 1200Y₁₁ + 1120Y₂₁ X₂₄ + X₂₅ + X₂₆ + X₂₇ ? 1200Y₁₂ + 1120Y₂₂ X₃₄ + X₃₅ + X₃₆ + X₃₇ ? 1200Y₁₃ + 1120Y₂₃ X₁₄ + X₂₄ + X₃₄ ? 500
X₁₅ + X₂₅ + X₃₅ ? 600 X₁₆ + X₂₆ + X₃₆ ? 450 X₁₇ + X₂₇ + X₃₇ ? 700
Y_ij.X_jk ? 0


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

Question 73

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:
$$\begin{array} { r r r } \text { Product } & \text { Profit per unit } & \text { Setup cost per batch } \\\hline 1 & 9 & 500 \\2 & 10 & 600 \\3 & 12 & 650\end{array}$$
The operation time per unit and total operating hours available are:
$$\begin{array}{c}\text { Operating Time per Unit }\\\begin{array} { l c c c c } \text { Operation } & \text { Product 1 } & \text { Product 2 } & \text { Product 3 } & \text { Operating Hours Available } \\\hline \text { Paint } & 1 & 2 & 2 & 400 \\\text { Assemble } & 2 & 3 & 2 & 600 \\\text { Inspection } & 2 & 4 & 3 & 540\end{array}\end{array}$$
Formulate the ILP for this problem.

Question 74

Binary variables are useful for modeling

A)the fixed-charge problem
B)the assignment problem
C)the transportation problem
D)the shortest route problem

Question 75

ILP formulations can be used to model:

A)production problems
B)personnel scheduling problems
C)investment allocation problems
D)all of the above

Question 76

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.
MAX: ^{50 X}₁ ^{+ 40 X}₂
Subject to: ^{2 X}₁ ^{+ 4 X}₂ ^{≤ 40}
3 X₁ + 2 X₂ ≤ 30
X₁,X₂ ≥ 0 and integer
Initial solution X₁ = 5.0
X₂ = 7.5
Obj = 550

Question 77

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₁.
MAX: ^{35 X}₁ ^{+ 45 X}₂
Subject to: ^{35 X}₁ ^{+ 55 X}₂ ^{≤ 250}
65 X₁ + 25 X₂ ≤ 340
X₁,X₂ ≥ 0 and integer
Initial solution
X₁ = 4.6X₂ = 1.6 Obj = 233.9

Question 78

One way to find an optimal solution to the IP problem is to:

A)use a B&B technique
B)use LP relaxation and round the values of the decision variables up to the nearest integer value
C)use LP relaxation and round the values of the decision variables down to the nearest integer value
D)use LP relaxation and round 50 percent of the decision variable values down to the nearest integer value and the remaining 50 percent up to the nearest integer value

Question 79

A popular solution technique to IP problems is called:

A)a branch-and-bound algorithm
B)branching
C)bounding
D)LP relaxation

Question 80

A vendor offers 5 different prices per unit depending on the quantity purchased.How many binary variables are needed to model this discounting scheme?

A)4
B)2
C)3
D)5