Question 1

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

Accepted Answer

A) True 
 B)False

Question 2

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.

Accepted Answer

A) True 
 B)False

Question 3

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

Accepted Answer

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

Question 4

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.

Accepted Answer

The answer of The Wiethoff Company has a contract to...

Question 5

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

Accepted Answer

A) True 
 B)False

Question 6

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?

Accepted Answer

The answer of The production manager for the Rusty soft...

Question 7

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

Accepted Answer

The answer of Solve the following integer LP using branch...

Question 8

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:

Accepted Answer

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

Question 9

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

Accepted Answer

A)  x1 = 1, x2 = 3 
B)  x1 = 4, x2 = 1 
C)  x1 = 0, x2 = 3 
D)  x1 = 3, x2 = 2 
E)  x1 = 2, x2= 2

Question 10

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

Accepted Answer

The answer of Solve the following integer linear program:
\(\begin{array} {...

Question 11

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

Accepted Answer

The answer of We begin the branch and bound method...

Question 12

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

Accepted Answer

A) True 
 B)False

Question 13

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?

Accepted Answer

The answer of The production manager for Beer etc. produces...

Question 14

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

Accepted Answer

A) True 
 B)False

Question 15

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

Accepted Answer

A) True 
 B)False

Question 16

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

Accepted Answer

A) True 
 B)False

Question 17

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

Accepted Answer

A) True 
 B)False

Question 18

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

Accepted Answer

The answer of The ________ method evaluates all feasible solutions...

Question 19

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

Accepted Answer

The answer of Solve the following integer linear program using...

Question 20

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

Accepted Answer

The answer of The branch and bound method can be...

Exam 19: Integer Programming: the Branch and Bound Method

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

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.

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

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

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

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:

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?

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

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

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

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

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

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

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

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

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

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