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

Answer 1

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

Question 2

The feasible region for the pure ILP problem

A) is a subset of the feasible region for the LP problem
B) is a collection of extreme rays
C) is a k-dimensional hyperspace
D) is impossible to determine

Answer 2

is a subset of the feasible region for the LP problem

Question 3

​One way of solving an ILP problem is to solve its LP relaxation and round the solution up or down to the nearest integer.

Answer 3

False

Question 4

The objective function value for the optimal solution to the ILP problem may be better than the objective function value for the optimal solution to its LP relaxation. ​

Question 5

​A problem in which some decision variables are restricted to assuming only integer values is called a 0-1 programming problem.

Question 6

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 7

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 8

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 9

​A problem in which all decision variables are restricted to assuming only integer values is called a pure IP programming problem.

Question 10

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

Binary variables are useful in modeling logical conditions in ILP problems. ​

Question 12

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

Question 13

Specifying suboptimality tolerances can be useful if a decision maker wants to find a good but nor optimal solution to a complex ILP problem.

Question 14

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 15

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 16

The default value of suboptimality tolerance in Solver is ​1%

Question 17

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

Question 18

Values of the binary integer variable are ​restricted to -1 or 1.

Question 19

​One useful feature of Analytic Solver Platform (ASP) is its ability to generate graphs of the optimization results.

Question 20

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 21

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 22

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 23

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 24

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 25

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 26

The branch & bound algorithm stops when:

A) the current best solution cannot be improved
B) the set of candidate problems to evaluate is not empty
C) the LP relaxation produced an integer solution
D) the LP relaxation produced a continuous solution

Question 27

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 28

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 29

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 30

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 31

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

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

Question 32

ILP formulations can be used to model:

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

Question 33

Binary decision variables:

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

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

A popular solution technique to IP problems is called:

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

Question 36

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 37

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 38

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 39

Rounding the LP relaxation solution up or down to the nearest integer may:

A) produce an infeasible solution
B) simplify the IP solution procedure
C) eliminate the need for B&B
D) reduce the risk of infeasibility

Question 40

The ILP problems are computationally

A) more demanding than their LP relaxations
B) less demanding than their LP relaxations
C) equally demanding compared to their LP relaxations
D) less complex than the corresponding LP problems

Question 41

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 42

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 43

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 44

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. 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
C) X₁ − 18Y₁ > 0
D) = if(X₁ > 0, Y₁ = 1, Y₁ = 0)

Question 45

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 46

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 47

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 48

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 49

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

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

Question 51

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 52

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 53

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 54

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 55

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 56

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

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 58

Binary variables are:

A) a subset of integer variables
B) continuous on an interval (0,1)
C) continuous on an interval (0,+∞)
D) negative

Question 59

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 60

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 61

The feasible region for the pure ILP problem

A) is a subset of the feasible region for the LP problem
B) is a superset of the feasible region for the LP problem
C) is a solid area
D) is a continuous area

Question 62

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 63

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 64

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 65

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 66

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 67

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 68

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 69

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

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 71

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 72

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

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 74

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 75

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₄ ≤ 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 76

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 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₁. Initial solution
X₁ = 4.6X₂ = 1.6
Obj = 233.9

Question 78

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 79

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 80

The feasible region for the pure ILP problem

A) is equivalent to the feasible region for the LP relaxation problem
B) is a lattice consisting of points corresponding only to integer values of the decision variables
C) is a k-dimensional hyperspace
D) is impossible to determine