FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 19: Integer Programming: the Branch and Bound Method

Show Answer

Share

---

All types

Filters

Study FlashcardsPractice ExamLearn

Question 21

Short Answer

Review LaterAdd Note

Review Later

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$

Correct Answer

verified

x1

View Answer

Show Answer

Question 22

Multiple Choice

Review LaterAdd Note

Review Later

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

Correct Answer

verified

Show Answer

Question 23

Short Answer

Review LaterAdd Note

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

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

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

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.

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

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

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

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

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.

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

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

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$

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 linear programming model solution with no integer restrictions is called a relaxed solution.

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.

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

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

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.