Back to Subject

Unit 7: Branch and Bound - Practice Quiz

ECAP538 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is the main purpose of the branch and bound technique?

General method Easy
A. To solve optimization problems systematically
B. To sort elements in ascending order
C. To encrypt data using private keys
D. To compile programs into machine code

2 What does branching do in the branch and bound method?

General method Easy
A. Combines all solutions into one problem
B. Removes every node from the search tree
C. Divides a problem into smaller subproblems
D. Converts an optimization problem into sorting

3 What is a bound in branch and bound?

General method Easy
A. An estimate of the best possible solution in a subproblem
B. The exact number of nodes in the complete search tree
C. A list containing every feasible solution to the problem
D. The maximum depth permitted for any search tree

4 What is pruning in branch and bound?

General method Easy
A. Selecting every child node without checking its bound
B. Sorting all input values before constructing the search tree
C. Adding duplicate subproblems to expand the search space
D. Discarding subproblems that cannot improve the current solution

5 In branch and bound, what does a node in the state-space tree usually represent?

General method Easy
A. A completed sorting operation
B. A randomly generated input value
C. A partial or complete candidate solution
D. A programming language instruction

6 What is the incumbent solution in branch and bound?

General method Easy
A. The first infeasible solution that is generated
B. The bound assigned to the root node
C. The final node removed during pruning
D. The best feasible solution found so far

7 Which structure is commonly used to represent choices in branch and bound?

General method Easy
A. A hash function
B. A syntax table
C. A state-space tree
D. A linked cycle

8 In the 0/1 knapsack problem, how many times may an item be selected?

0/1 knapsack problem Easy
A. Only a fractional number of times
B. Exactly two times
C. Either zero times or one time
D. Any nonnegative number of times

9 What is the objective of the 0/1 knapsack problem?

0/1 knapsack problem Easy
A. Minimize total profit beyond the capacity
B. Maximize total profit within the capacity
C. Maximize total weight without using items
D. Minimize the number of available items

10 What constraint must a feasible 0/1 knapsack solution satisfy?

0/1 knapsack problem Easy
A. Total weight must not exceed capacity
B. Every available item must be selected
C. Each item must be divided into fractions
D. Total profit must equal total weight

11 What does a branch commonly represent for an item in the 0/1 knapsack problem?

0/1 knapsack problem Easy
A. Sort the item or delete its profit
B. Increase the item weight or reduce it
C. Divide the item or duplicate the item
D. Include the item or exclude the item

12 If the knapsack capacity is and selected items weigh , the selection is:

0/1 knapsack problem Easy
A. Fractional
B. Infeasible
C. Optimal
D. Empty

13 Which relaxation is commonly used to calculate an upper bound for a 0/1 knapsack node?

0/1 knapsack problem Easy
A. Matrix multiplication relaxation
B. Binary search relaxation
C. Topological sorting relaxation
D. Fractional knapsack relaxation

14 An item has profit and weight . What is its profit-to-weight ratio?

0/1 knapsack problem Easy
A.
B.
C.
D.

15 What is the main objective of the travelling salesperson problem?

Travelling salesperson Easy
A. Connect all cities without completing a tour
B. Find the longest path between two selected cities
C. Find the minimum-cost tour visiting every city
D. Visit one city repeatedly at minimum cost

16 In a valid travelling salesperson tour, how often is each city visited?

Travelling salesperson Easy
A. At least twice before ending anywhere
B. Only when its travel cost is zero
C. Any number of times without restriction
D. Exactly once before returning to the start

17 What does an edge weight usually represent in the travelling salesperson problem?

Travelling salesperson Easy
A. Number of tours already completed
B. Number of salespeople in each city
C. Population of the destination city
D. Travel cost or distance between cities

18 A complete travelling salesperson solution must end at:

Travelling salesperson Easy
A. The nearest unvisited city
B. Any city outside the tour
C. The city with the lowest edge
D. The starting city

19 In branch and bound for the travelling salesperson problem, what can a tree node represent?

Travelling salesperson Easy
A. A sorted list of all edge weights
B. A table containing only final tours
C. A city removed permanently from the graph
D. A partial tour through some cities

20 When can a travelling salesperson branch be pruned in a minimization search?

Travelling salesperson Easy
A. Its path contains at least one edge
B. Its partial tour contains the starting city
C. Its next city has not yet been visited
D. Its lower bound is no better than the current best cost

21 In a least-cost branch-and-bound algorithm for a minimization problem, four live nodes have lower bounds , , , and . Which node is selected for expansion next?

General method Medium
A. The node with bound
B. The node with bound
C. The node with bound
D. The node with bound

22 For a maximization problem, live nodes , , and have upper bounds , , and , respectively. Which node should a best-bound strategy expand first?

General method Medium
A. Node with bound
B. Node with bound
C. Node with bound
D. Any node with bound above

23 A minimization algorithm currently has a feasible solution of cost . A live node has a valid lower bound of . What should the algorithm do with this node?

General method Medium
A. Prune it without further expansion
B. Recompute it as an upper bound
C. Replace the incumbent cost by
D. Expand it before all other nodes

24 Which combination correctly describes FIFO branch and bound and LIFO branch and bound?

General method Medium
A. FIFO uses a heap; LIFO uses a queue
B. FIFO uses a queue; LIFO uses a stack
C. FIFO uses a stack; LIFO uses a heap
D. FIFO uses a stack; LIFO uses a queue

25 For a maximization problem, which property must a valid upper-bound function satisfy at a node?

General method Medium
A. It equals every feasible completion value
B. It never exceeds the current incumbent
C. It is at least the best completion value
D. It is below every feasible completion value

26 A node in a minimization state-space tree has lower bound , while the current incumbent costs . Which conclusion is valid?

General method Medium
A. The node must contain a solution of cost
B. The node can be pruned because
C. The node may still improve the current solution
D. The incumbent must immediately change to

27 A knapsack has capacity . At a node, selected items have total weight and profit . The remaining ratio-ordered items are and . What fractional-knapsack upper bound applies?

0/1 knapsack problem Medium
A.
B.
C.
D.

28 At a knapsack node, the current weight is and the capacity is . The next item has weight and profit . How should branching handle the include child?

0/1 knapsack problem Medium
A. Keep it after reducing its profit proportionally
B. Prune it only if its bound is negative
C. Keep it because its profit is positive
D. Prune it because its weight becomes

29 Items , , , and have values , , , and . In what order should they be considered when computing the standard fractional upper bound?

0/1 knapsack problem Medium
A.
B.
C.
D.

30 For capacity , three items have values , , and . What is the optimal 0/1 knapsack profit?

0/1 knapsack problem Medium
A.
B.
C.
D.

31 The incumbent profit is , and a live knapsack node has an upper bound of . If only one optimal solution is required, what action is appropriate?

0/1 knapsack problem Medium
A. Expand the node to seek profit
B. Replace the incumbent with the node bound
C. Prune the node because it cannot improve
D. Lower the incumbent before branching further

32 A knapsack has capacity , and ratio-ordered items have values , , and . What is the fractional upper bound at the root?

0/1 knapsack problem Medium
A.
B.
C.
D.

33 In the binary state-space tree for a 0/1 knapsack problem, a node at level records decisions for the first items. What do its two children normally represent?

0/1 knapsack problem Medium
A. Including or excluding item
B. Increasing or decreasing item
C. Splitting item into fractions
D. Reordering or removing all remaining items

34 For the TSP cost matrix what lower bound results from row reduction followed by column reduction?

Travelling salesperson Medium
A.
B.
C.
D.

35 In Little's branch-and-bound method for TSP, several zero entries exist in the reduced cost matrix. Which zero is commonly selected for branching?

Travelling salesperson Medium
A. The zero with the largest exclusion penalty
B. The zero with the smallest original cost
C. The zero with the smallest row index
D. The zero generated by the last reduction

36 For a symmetric TSP with cities, how many distinct tours exist when rotations and reverse traversals are considered equivalent?

Travelling salesperson Medium
A.
B.
C.
D.

37 A partial TSP path is , while cities and remain unvisited. Why is adding normally forbidden at this stage?

Travelling salesperson Medium
A. It makes the cost matrix asymmetric
B. It forces every remaining edge to cost zero
C. It changes the problem into a shortest path problem
D. It creates a subtour before visiting every city

38 A symmetric four-city TSP has edge costs , , , , , and . Using half the sum of the two cheapest incident edges at each city, what lower bound is obtained?

Travelling salesperson Medium
A.
B.
C.
D.

39 A complete TSP tour of cost is the current incumbent. A live node has a valid lower bound of . What should branch and bound do?

Travelling salesperson Medium
A. Set the incumbent tour cost to
B. Convert the lower bound into an upper bound
C. Expand the node because is larger
D. Prune the node because it cannot improve

40 A symmetric TSP has costs , , , , , and . What is the minimum tour cost?

Travelling salesperson Medium
A.
B.
C.
D.

41 In a maximization branch-and-bound algorithm, is a valid upper bound on every solution below node , and the incumbent has value . If only one optimal solution is required, which pruning rule is valid?

General method Hard
A. Prune whenever
B. Prune whenever
C. Prune whenever
D. Prune whenever

42 A best-bound branch-and-bound algorithm minimizes an objective. Its incumbent value is , and the lower bounds of all live nodes are , and . What conclusion is justified?

General method Hard
A. The incumbent is suboptimal because one bound equals
B. Only nodes bounded strictly above may be pruned
C. The node bounded by must still be expanded
D. The incumbent is optimal, so the search may terminate

43 For a minimization problem, a child node has a valid raw lower bound of , while its parent has a valid lower bound of . Which bound can safely be assigned to the child to enforce monotonicity?

General method Hard
A. , obtained as the sum of the two bounds
B. , because parent bounds cannot constrain children
C. , obtained as the maximum of the two bounds
D. , obtained as the average of the two bounds

44 Suppose the branches generated from a node overlap, but their union still contains every feasible completion represented by the parent. What is the principal consequence?

General method Hard
A. Correctness can remain intact, but duplicate exploration may occur
B. Optimality is lost because branches must always be disjoint
C. Bounds become inadmissible whenever two branches share solutions
D. Termination becomes impossible even for a finite search space

45 Which comparison between depth-first and best-bound node selection is generally correct for branch-and-bound?

General method Hard
A. Best-bound uses linear memory because it stores only one active path
B. Depth-first always expands fewer nodes because it reaches leaves first
C. Depth-first uses less frontier memory but may delay a strong incumbent
D. Best-bound always finds a feasible incumbent before depth-first search

46 In a minimization problem, a node bound is computed by solving a relaxation. Which property is essential for this value to support safe pruning?

General method Hard
A. It must not exceed the best feasible value below the node
B. It must equal the best feasible value below the node
C. It must be obtained using the same variables as the original model
D. It must exceed the current incumbent whenever the node is feasible

47 A knapsack has capacity . Items ordered by profit-to-weight ratio are , , , and , where each pair is . At a node, item 1 is included and item 2 is excluded. What fractional-knapsack upper bound applies?

0/1 knapsack problem Hard
A.
B.
C.
D.

48 For capacity , the items are , , , and . What are the root fractional bound and the optimal 0/1 value, respectively?

0/1 knapsack problem Hard
A. and
B. and
C. and
D. and

49 All knapsack profits are integers. A node's fractional upper bound is , and the incumbent value is . If only a strictly better solution matters, what is the strongest valid conclusion?

0/1 knapsack problem Hard
A. The node may be pruned after replacing the bound by
B. The node must be expanded because exceeds the incumbent
C. The incumbent must be raised to before pruning the node
D. The node may be pruned only if its fractional bound is below

50 Item has weight and profit , while item has weight and profit . Why is deleting solely because has no greater weight and no smaller profit unsafe in a 0/1 instance?

0/1 knapsack problem Hard
A. Equal profits make the relaxation's bound inadmissible
B. The lighter item must always be selected fractionally
C. An optimal solution may contain both and
D. Dominance applies only when both weights are identical

51 At a 0/1 knapsack node, the LP relaxation has exactly one fractional variable . What is guaranteed when branching into and ?

0/1 knapsack problem Hard
A. The two children necessarily have equal fractional bounds
B. Both child bounds are strictly below the parent bound
C. At least one child immediately yields an integral optimum
D. The current fractional LP solution is excluded from both children

52 A branch-and-bound node fixes some knapsack decisions, and an exact dynamic program solves the residual instance. How should the resulting value be used?

0/1 knapsack problem Hard
A. Discard it unless the residual solution fills the capacity exactly
B. Use it only as an upper bound, then branch on every residual item
C. Use it as the exact node optimum, update the incumbent, and fathom the node
D. Use it as a lower bound, but retain the node until all siblings finish

53 A 0/1 knapsack instance contains positive-profit items of weight zero. Which preprocessing is correct before constructing a profit-to-weight fractional bound?

0/1 knapsack problem Hard
A. Assign every such item ratio zero and process it last
B. Include every such item and add its profit to all relevant bounds
C. Exclude every such item because its ratio is undefined
D. Branch on every such item before accepting any incumbent

54 For the directed cost matrix below, diagonal entries are forbidden. Using row reduction followed by column reduction, what root lower bound is obtained?

Travelling salesperson Hard
A.
B.
C.
D.

55 The assignment relaxation of an asymmetric travelling salesperson instance returns a minimum-cost cycle cover containing three disjoint cycles. Which statement is correct?

Travelling salesperson Hard
A. The relaxation is infeasible unless the cover contains one cycle
B. Its cost is a lower bound, but the cover is not necessarily a tour
C. The cover is a valid tour after independently rotating its cycles
D. Its cost is an upper bound because every city has degree two

56 For a symmetric TSP and a chosen root vertex , which construction gives the standard minimum 1-tree lower bound?

Travelling salesperson Hard
A. Two disjoint MSTs on joined through the root
B. An MST on plus the cheapest edge not contained in that tree
C. An MST on plus the two cheapest edges incident to
D. A shortest-path tree rooted at plus its most expensive missing edge

57 In a complete symmetric graph, the two smallest incident edge costs at vertices sum respectively to . What degree-based lower bound follows for any Hamiltonian tour?

Travelling salesperson Hard
A.
B.
C.
D.

58 For a symmetric TSP with distinct city labels, the starting city is fixed to remove rotational duplicates. Which additional restriction removes reversal duplicates without eliminating any distinct tour cost?

Travelling salesperson Hard
A. Require all visited city labels to occur in increasing order
B. Require the last city to be the largest-labelled remaining city
C. Require the second city's label to be smaller than the last city's label
D. Require the cheapest edge to leave the fixed starting city first

59 In Little's branch-and-bound algorithm, a reduced cost matrix contains a zero at entry . Excluding column , the smallest finite entry in row is ; excluding row , the smallest finite entry in column is . What is the exclusion penalty for this zero?

Travelling salesperson Hard
A.
B.
C.
D.

60 Two partial directed TSP paths start at the same fixed city, visit exactly the same subset , and end at the same city . Their costs are and . Edge costs depend only on endpoints. Which dominance decision is valid?

Travelling salesperson Hard
A. Discard the path costing because it may have used cheaper edges too early
B. Retain both paths because their internal visit orders are necessarily relevant
C. Merge their costs by averaging them before computing a completion bound
D. Discard the path costing because both paths have identical completion choices
Previous MCQ
Unit 6
Next MCQ
Unit 8