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 encrypt data using private keys
B. To sort elements in ascending order
C. To compile programs into machine code
D. To solve optimization problems systematically

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

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

3 What is a bound in branch and bound?

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

4 What is pruning in branch and bound?

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

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 programming language instruction
C. A randomly generated input value
D. A partial or complete candidate solution

6 What is the incumbent solution in branch and bound?

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

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. Any nonnegative number of times
B. Only a fractional number of times
C. Either zero times or one time
D. Exactly two times

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

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

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. Total profit must equal total weight
D. Each item must be divided into fractions

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

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

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

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

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

0/1 knapsack problem Easy
A. Binary search relaxation
B. Topological sorting relaxation
C. Matrix multiplication 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. Visit one city repeatedly at minimum cost
B. Find the longest path between two selected cities
C. Find the minimum-cost tour visiting every city
D. Connect all cities without completing a tour

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

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

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

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

18 A complete travelling salesperson solution must end at:

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

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 city removed permanently from the graph
C. A partial tour through some cities
D. A table containing only final tours

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

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

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. Any node with bound above
B. Node with bound
C. Node with bound
D. Node with bound

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. Replace the incumbent cost by
B. Expand it before all other nodes
C. Prune it without further expansion
D. Recompute it as an upper bound

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

General method Medium
A. FIFO uses a queue; LIFO uses a stack
B. FIFO uses a stack; LIFO uses a queue
C. FIFO uses a stack; LIFO uses a heap
D. FIFO uses a heap; 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 is below every feasible completion value
B. It equals every feasible completion value
C. It never exceeds the current incumbent
D. It is at least the best 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 may still improve the current solution
B. The node must contain a solution of cost
C. The incumbent must immediately change to
D. The node can be pruned because

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. Prune it because its weight becomes
B. Prune it only if its bound is negative
C. Keep it after reducing its profit proportionally
D. Keep it because its profit is positive

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. Prune the node because it cannot improve
B. Lower the incumbent before branching further
C. Expand the node to seek profit
D. Replace the incumbent with the node bound

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. Increasing or decreasing item
B. Reordering or removing all remaining items
C. Splitting item into fractions
D. Including or excluding item

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 generated by the last reduction
B. The zero with the largest exclusion penalty
C. The zero with the smallest original cost
D. The zero with the smallest row index

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 changes the problem into a shortest path problem
B. It makes the cost matrix asymmetric
C. It forces every remaining edge to cost zero
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. Expand the node because is larger
B. Convert the lower bound into an upper bound
C. Prune the node because it cannot improve
D. Set the incumbent tour cost to

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 optimal, so the search may terminate
B. Only nodes bounded strictly above may be pruned
C. The incumbent is suboptimal because one bound equals
D. The node bounded by must still be expanded

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 average of the two bounds
B. , obtained as the maximum of the two bounds
C. , obtained as the sum of the two bounds
D. , because parent bounds cannot constrain children

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. Bounds become inadmissible whenever two branches share solutions
B. Optimality is lost because branches must always be disjoint
C. Termination becomes impossible even for a finite search space
D. Correctness can remain intact, but duplicate exploration may occur

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

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

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 be obtained using the same variables as the original model
B. It must not exceed the best feasible value below the node
C. It must exceed the current incumbent whenever the node is feasible
D. It must equal the best feasible value below the node

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 only if its fractional bound is below
B. The node may be pruned after replacing the bound by
C. The node must be expanded because exceeds the incumbent
D. The incumbent must be raised to before pruning the node

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. Dominance applies only when both weights are identical
B. An optimal solution may contain both and
C. The lighter item must always be selected fractionally
D. Equal profits make the relaxation's bound inadmissible

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. Both child bounds are strictly below the parent bound
B. The current fractional LP solution is excluded from both children
C. The two children necessarily have equal fractional bounds
D. At least one child immediately yields an integral optimum

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 as a lower bound, but retain the node until all siblings finish
C. Use it only as an upper bound, then branch on every residual item
D. Use it as the exact node optimum, update the incumbent, and fathom the node

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. Branch on every such item before accepting any incumbent
C. Exclude every such item because its ratio is undefined
D. Include every such item and add its profit to all relevant bounds

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. Its cost is an upper bound because every city has degree two
B. The cover is a valid tour after independently rotating its cycles
C. Its cost is a lower bound, but the cover is not necessarily a tour
D. The relaxation is infeasible unless the cover contains one cycle

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

Travelling salesperson Hard
A. An MST on plus the two cheapest edges incident to
B. An MST on plus the cheapest edge not contained in that tree
C. Two disjoint MSTs on joined through the root
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 cheapest edge to leave the fixed starting city first
D. Require the second city's label to be smaller than the last city's label

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. Merge their costs by averaging them before computing a completion bound
B. Discard the path costing because both paths have identical completion choices
C. Discard the path costing because it may have used cheaper edges too early
D. Retain both paths because their internal visit orders are necessarily relevant
Previous MCQ
Unit 6
Next MCQ
Unit 8