Deck 19: Integer Programming: the Branch and Bound Method

Question 1

The branch and bound method is a solution technique specifically limited to integer programming problems.

Answer 1

False

Question 2

In implicit enumeration the feasible integer solutions closest to the optimal non-integer solution are evaluated to see which is best.

Answer 2

False

Question 3

The number of nodes considered in a branch and bound tree for maximization integer programming problems is always minimized by going to the node with the largest upper bound.

Answer 3

True

Question 4

Rounding non-integer solution values up to the nearest integer value can result in an infeasible solution.

Question 5

In solving a maximization problem, the optimal profit associated with the relaxed solution (LP-relaxation) is always less than or equal to the value of the optimal profit associated with the integer solution.

Question 6

If an integer programming problem has no feasible solution, then its LP relaxation (relaxed solution) must also have no feasible solution.

Question 7

The branch and bound method of solving linear integer programming problems is an enumeration method.

Question 8

A linear programming model solution with no integer restrictions is called a relaxed solution.

Question 9

The branch and bound method is a solution approach that partitions the feasible solution space into smaller subsets of solutions.

Question 10

A linear programming model solution with integer restrictions is called a relaxed solution.

Question 11

The branch and bound method is a solution approach that partitions the infeasible solution space into smaller subsets of solutions.

Question 12

A feasible solution is ensured by rounding down non-integer solution values.

Question 13

A feasible solution is ensured by rounding down integer solution values.

Question 14

When the branch and bound approach is applied to an integer programming problem, it is used in conjunction with the normal non-integer solution approach.

Question 15

In using the branch and bound method, if a branch gives an infeasible solution to the associated linear programming problem, then the particular branch is fathomed and is not considered any further.

Question 16

When using branch and bound for a maximization integer programming problem, the lower bound at the initial node can always be determined by rounding down the LP relaxation solution values regardless of the types of constraints in the problem.

Question 17

The branch and bound solution method cannot be applied to 0-1 integer programming problems.

Question 18

If an integer linear programming problem has no feasible solution, then its relaxed solution (LP relaxation) must also have no feasible solution

Question 19

An infeasible solution is ensured by rounding down non-integer solution values.

Question 20

A rounded-down integer solution can result in a less than optimal solution.

Question 21

The branch and bound method can be used for ________ integer problems except only variables with integer restrictions are rounded down to achieve an initial lower bound and only integer variables are branched on.

Question 22

The ________ integer solution will always be between the upper bound of the relaxed solution and a lower bound of the rounded-down solution.

Question 23

An ________ solution is reached when a feasible integer solution is reached at a node that has an upper bound equal to lower bound.

Question 24

The branch and bound method can be used for 0-1 integer programming problems by adding a ________ 1 constraint for each 0-1 variable.

Question 25

Consider a capital budgeting example with five projects from which to select. Let xi = 1 if project a is selected, 0 if not, for i = 1, 2, 3, 4, 5. Write the appropriate constraint(s) for the following condition: If project 3 is chosen, project 4 must be chosen.

Question 26

The ________ method evaluates all feasible solutions to determine the optimal solution.

Question 27

The production manager for the Rusty soft drink company is considering the production of two kinds of soft drinks: regular and diet. Two of her resources are constraint production time (8 hours = 480 minutes per day) and syrup (1 of the ingredients), limited to 675 gallons per day. To produce a regular case requires 2 minutes and 5 gallons of syrup, while a diet case needs 4 minutes and 3 gallons of syrup. Profits for regular soft drink are $3 per case and profits for diet soft drink are $2 per case. What are optimal daily profits?

Question 28

The branch and bound method uses a tree diagram of ________ and ________ to organize the solution partitioning.

Question 29

Branch and bound cannot be used to solve mixed integer programs.

Question 30

We begin the branch and bound method by first solving the problem as a regular ________ model without integer restrictions.

Question 31

In implicit enumeration, all feasible solutions are evaluated to see which is best.

Question 32

A linear programming model solution with no integer restrictions is called a ________ solution.

Question 33

The production manager for Beer etc. produces two kinds of beer: light and dark. Two of his resources are constrained: malt, of which he can get at most 4800 oz per week; and wheat, of which he can get at most 3200 oz per week. Each bottle of light beer requires 12 oz of malt and 4 oz of wheat, while a bottle of dark beer uses 8 oz of malt and 8 oz of wheat. Profits for light beer are $2 per bottle, and profits for dark beer are $1 per bottle. What are the optimal weekly profits?

Question 34

A ________ solution is not guaranteed by rounding down non-integer solution values.

Question 35

The Wiethoff Company has a contract to produce 10,000 garden hoses for a customer. Wiethoff has four different machines that can produce this kind of hose. Because these machines are from different manufacturers and use differing technologies, their specifications are not the same and not all four machines have to be used to produce all of the garden hoses. $\begin{array}{cccc}&\text { Fixed Cost }\\&to~ Setup&Variable ~Cost\\\text { Machine } & \text { Production Run } & \text { per Hose } & \text { Capacity } \\\hline 1 & 750 & 1.25 & 6000 \\2 & 500 & 1.50 & 7500 \\3 & 1000 & 1.00 & 4000 \\4 & 300 & 2.00 & 5000\end{array}$
This problem requires two different kinds of decision variables. Clearly define each kind.

Question 36

Consider a capital budgeting example with five projects from which to select. Let xi = 1 if project a is selected, 0 if not, for i = 1, 2, 3, 4, 5. Write the appropriate constraint(s) for the following condition: If project 1 is chosen, project 5 must not be chosen.

Question 37

The ________ method evaluates all feasible and infeasible solutions to determine the optimal solution.

Question 38

The ________ method is a solution approach that partitions the feasible solution space into smaller subsets of solutions.

Question 39

The branch and bound method uses a tree diagram of nodes and branches to organize the solution partitioning.

Question 40

In using the branch and bound method, we always branch from the node with the ________ upper bound.

Question 41

Solve the following integer LP using branch and bound:

$\begin{array} { l l } \text { MAX } & Z = x _ { 1 } + 5 x _ { 2 } \\\text { subject to: } & x _ { 1 } + 10 x _ { 2 } \leq 20 \\& x _ { 1 } \leq 2 \\& x _ { 1 } , x _ { 2 } \geq 0 \text { and integer }\end{array}$

Question 42

Consider the following integer programming problem. Solve it using the branch and bound method. What are the optimal values of x1, x2, and Z?
Maximize \mathrm    { Z } = 2 x _ { 1 } + x _ { 2 }
Subject to: \quad    2 x _ { 1 } + 2 x _ { 2 } \leq 7
           $4 x _ { 1 } + x _ { 2 } \leq 11$
             $x _ { 1 }$ and $x _ { 2 } \geq 0$

A) x₁ = 1, x₂ = 2, Z = 4
B) x₁= 2, x₂ = 1, Z = 5
C) x₁ = 1, x₂ = 1, Z = 3
D) x₁ = 0, x₂= 3, Z = 3
E) x₁ = 2, x₂ = 2, Z = 6

Question 43

The branch and bound method is a solution approach that partitions the ________ solution space into smaller subsets of solutions.

A) infeasible
B) feasible
C) optimal
D) all of the above

Question 44

Consider the following integer programming problem. Solve it using the branch and bound method. What are the optimal values of x1, x2 and Z?
Maximize $\mathrm { Z } = 2 x _ { 1 } + x _ { 2 }$
Subject to: $\quad 2 x _ { 1 } + 2 x _ { 2 } \leq 7$
$~~~~~~~~~~~~~~~~~~~4 x _ { 1 } + x _ { 2 } \leq 11$
$~~~~~~~~~~~~~~~~~~~x _ { 1 }$ and $x _ { 2 } \geq 0$

Question 45

Solve the following integer linear program:

$\begin{array} { l l } \operatorname { MAX } & x _ { 1 } + x _ { 2 } \\\text { subject to: } & 4 x _ { 1 } + 6 x _ { 2 } \leq 22 \\& x _ { 1 } + 5 x _ { 2 } \leq 15 \\& 2 x _ { 1 } + x _ { 2 } \leq 9 \\& x _ { 1 } , x \geq 0 , \text { integer }\end{array}$

Question 46

Solve the following integer linear program:
$\begin{array} { l l } \operatorname { MAX } & x _ { 1 } + x _ { 2 } \\\text { subject to: } & 4 x _ { 1 } + 6 x _ { 2 } \leq 22 \\& x _ { 1 } + 5 x _ { 2 } \leq 15 \\& 2 x _ { 1 } + x _ { 2 } \leq 9 \\& x _ { 1 } , x \geq 0 , \text { integer }\end{array}$

Question 47

Rounding large values of decision variables to the nearest integer value causes ________ problems than rounding small values.

A) more
B) fewer
C) none of the above

Question 48

Solve the following integer linear program using implicit enumeration.
$\begin{array} { l l } \text { MAX } & Z = x _ { 2 } \\\text { subject to: } & - x _ { 1 } + x _ { 2 } \leq 0.5 \\& x _ { 1 } + x _ { 2 } \leq 3.5 \\& x _ { 2 } , x _ { 2 } \geq 0 \text { and integer }\end{array}$

Question 49

Which of the following can be used to solve integer programs with 2 variables?
I) Graphical techniques
II) Complete enumeration
III) Relaxed LP solutions
IV) Branch and bound

A) I, II, III, and IV
B) I and III
C) I, II, and IV
D) I and IV
E) I, II and III

Question 50

The branch and bound method of solving linear integer programming problems is

A) a nonlinear method.
B) a relaxation method.
C) a graphical solution.
D) an enumeration method.

Question 51

The branch and bound method uses a tree diagram of ________ to organize the solution partitioning.

A) branches
B) nodes
C) nodes and branches
D) none of the above

Question 52

The Wiethoff Company has a contract to produce 10,000 garden hoses for a customer. Wiethoff has four different machines that can produce this kind of hose. Because these machines are from different manufacturers and use differing technologies, their specifications are not the same and not all four machines have to be used to produce all of the garden hoses. $\begin{array}{cccc}&\text { Fixed Cost }\\&to~ Setup&Variable ~Cost\\\text { Machine } & \text { Production Run } & \text { per Hose } & \text { Capacity } \\\hline 1 & 750 & 1.25 & 6000 \\2 & 500 & 1.50 & 7500 \\3 & 1000 & 1.00 & 4000 \\4 & 300 & 2.00 & 5000\end{array}$ Write a constraint to ensure that if machine 4 is used, machine 1 will not be used.

A) y1 + y4 ? 0
B) y1 + y4 ? 1
C) y1 + y4 ? 1
D) y1 - y4 ? 1
E) y1 - y4 ? 0

Question 53

The optimal integer solution will always be between the upper bound of the ________ solution and a lower bound of the rounded-down ________ solution.

A) relaxed, non-integer
B) integer, relaxed
C) relaxed, integer
D) none of the above

Question 54

When using branch and bound to solve an integer programming problem, if the value of X₁ = 2.5 at a given node, then one of the descendant branches would have which one of the additional constraints?

A) X₁ ? 2
B) X₁ ? 3
C) X₁ = 3
D) X₁ ? 2
E) X₁ = 2

Question 55

A linear programming model solution with no integer restrictions is called a(n) ________ solution.

A) optimal
B) feasible
C) relaxed
D) all of the above

Question 56

The optimal integer solution will always be between the ________ bound of the relaxed solution and a lower bound of the rounded-down integer solution.

A) lower
B) optimal
C) upper
D) all of the above

Question 57

The upper bound at the initial node of a branch and bound tree is given by

A) the value of the objective function of the LP relaxation .
B) the value of the objective function after the LP relaxation solution is rounded down to an integer solution.
C) the value of the objective function corresponding to an integer feasible solution determined on the basis of trial and error.
D) cannot be determined

Question 58

The Wiethoff Company has a contract to produce 10,000 garden hoses for a customer. Wiethoff has four different machines that can produce this kind of hose. Because these machines are from different manufacturers and use differing technologies, their specifications are not the same and not all four machines have to be used to produce all of the garden hoses. $\begin{array}{cccc}&\text { Fixed Cost }\\&to~ Setup&Variable ~Cost\\\text { Machine } & \text { Production Run } & \text { per Hose } & \text { Capacity } \\\hline 1 & 750 & 1.25 & 6000 \\2 & 500 & 1.50 & 7500 \\3 & 1000 & 1.00 & 4000 \\4 & 300 & 2.00 & 5000\end{array}$
Give the constraints for the problem.

Question 59

The Wiethoff Company has a contract to produce 10,000 garden hoses for a customer. Wiethoff has four different machines that can produce this kind of hose. Because these machines are from different manufacturers and use differing technologies, their specifications are not the same and not all four machines have to be used to produce all of the garden hoses. $\begin{array}{cccc}&\text { Fixed Cost }\\&to~ Setup&Variable ~Cost\\\text { Machine } & \text { Production Run } & \text { per Hose } & \text { Capacity } \\\hline 1 & 750 & 1.25 & 6000 \\2 & 500 & 1.50 & 7500 \\3 & 1000 & 1.00 & 4000 \\4 & 300 & 2.00 & 5000\end{array}$
Write a constraint to ensure that if machine 4 is used, machine 1 will not be used.

Question 60

In using rounding of a linear programming model to obtain an integer solution, the solution is

A) always optimal and feasible.
B) sometimes optimal and feasible.
C) always optimal.
D) always feasible.

Question 61

Solve the following integer LP using branch and bound:
$\begin{array} { l l } \text { MAX } & x _ { 1 } + 5 x _ { 2 } \\\text { subject to: } & x _ { 1 } + 10 x _ { 2 } \leq 20 \\& x _ { 1 } \leq 2 \\& x _ { 1 } , x _ { 2 } \geq 0 \text { and integer }\end{array}$
The optimal value of Z is:

A) 7
B) 6
C) 10
D) 11
E) 12

Question 62

Consider the following integer LP.
$\begin{array} { l l } \text { MAX } & x _ { 1 } + 5 x _ { 2 } \\\text { subject to: } & x _ { 1 } + 10 x _ { 2 } \leq 20 \\& x _ { 1 } \leq 2 \\& x _ { 1 } , x _ { 2 } \geq 0 \text { and integer }\end{array}$
Solve for the value of x₂ at the first node and identify the constraint below that correctly represents one of the descendant branches.

A) x₂ ? 1
B) x₂ ? 1
C) x₂ ? 2
D) x₂ ? 0

Question 63

Solve the following integer linear program:
MAX    $\quad Z = 2 x _ { 1 } + x _ { 2 }$
subject to:     $2 x _ { 1 } + 2 x _ { 2 } \leq 7$
          $4 x _ { 1 } + x _ { 2 } \leq 11$
          $x _ { 1 }$ and $x _ { 2 } \geq 0$
What are the optimal values of x1 and x2?

A) x₁ = 1, x₂ = 3
B) x₁ = 4, x₂ = 1
C) x₁ = 0, x₂ = 3
D) x₁ = 3, x₂ = 2
E) x₁ = 2, x₂= 2