Section A: Introduction to the Traveling Salesman Problem

1. What is the main objective of the Traveling Salesman Problem?
   a) Find the shortest tour that visits every city once and returns to the starting city
   b) Assign workers to jobs
   c) Determine inventory order quantities
   d) Minimize customer waiting time
   Answer: a) Find the shortest tour that visits every city once and returns to the starting city
2. The Traveling Salesman Problem is commonly abbreviated as:
   a) TSM
   b) TSP
   c) TPS
   d) STP
   Answer: b) TSP
3. In the TSP, each city must normally be visited:
   a) At least twice
   b) Any number of times
   c) Exactly once
   d) Only if its travel cost is low
   Answer: c) Exactly once
4. After visiting all cities, the salesperson must:
   a) Stop at the last city
   b) Visit the nearest warehouse
   c) Choose another starting city
   d) Return to the starting city
   Answer: d) Return to the starting city
5. A complete feasible TSP route is also called a:
   a) Tour
   b) Queue
   c) Transportation allocation
   d) Basic feasible solution
   Answer: a) Tour
6. The TSP is most closely related to which area of operations research?
   a) Inventory control
   b) Network optimization
   c) Queuing theory
   d) Replacement theory
   Answer: b) Network optimization
7. In graph-theory terms, cities in a TSP are represented by:
   a) Costs
   b) Routes
   c) Nodes or vertices
   d) Constraints only
   Answer: c) Nodes or vertices
8. Roads or travel connections between cities are represented by:
   a) Demand values
   b) Supply values
   c) Decision criteria
   d) Edges or arcs
   Answer: d) Edges or arcs
9. The value associated with an edge in a TSP commonly represents:
   a) Distance, time or cost
   b) Number of cities
   c) Customer demand only
   d) Number of vehicles
   Answer: a) Distance, time or cost
10. Which is a practical application of the TSP?
    a) Determining economic order quantity
    b) Planning a delivery route
    c) Calculating employee salaries
    d) Measuring queue length
    Answer: b) Planning a delivery route
11. Which situation best represents a TSP?
    a) Assigning four employees to four jobs
    b) Shipping goods from factories to warehouses
    c) Visiting several customer locations using the shortest closed route
    d) Scheduling activities in a project
    Answer: c) Visiting several customer locations using the shortest closed route
12. The TSP is called a combinatorial optimization problem because:
    a) It contains no constraints
    b) It can be solved only graphically
    c) It always has two variables
    d) It requires selecting the best route from many possible combinations
    Answer: d) It requires selecting the best route from many possible combinations
13. The TSP is generally classified as:
    a) An NP-hard problem
    b) A simple arithmetic problem
    c) A queuing problem
    d) A continuous forecasting problem
    Answer: a) An NP-hard problem
14. As the number of cities increases, the number of possible tours:
    a) Remains constant
    b) Increases very rapidly
    c) Decreases
    d) Becomes equal to the number of cities
    Answer: b) Increases very rapidly
15. For a symmetric TSP with (n) cities, the number of distinct tours is generally:
    a) (n)
    b) (n^2)
    c) ((n-1)!/2)
    d) (2n)
    Answer: c) ((n-1)!/2)
16. Why is the number of symmetric TSP tours divided by two?
    a) Two cities are removed
    b) Half the distances are zero
    c) Only half the cities are visited
    d) A tour and its reverse are considered equivalent
    Answer: d) A tour and its reverse are considered equivalent
17. In a symmetric TSP:
    a) Travel cost from city (i) to city (j) equals the cost from (j) to (i)
    b) Every route has the same cost
    c) All cities have identical locations
    d) Only clockwise tours are allowed
    Answer: a) Travel cost from city (i) to city (j) equals the cost from (j) to (i)
18. In an asymmetric TSP:
    a) Every city must be visited twice
    b) Travel cost from (i) to (j) may differ from the cost from (j) to (i)
    c) The route does not return to the start
    d) No cost matrix is used
    Answer: b) Travel cost from (i) to (j) may differ from the cost from (j) to (i)
19. Which may cause an asymmetric TSP?
    a) Equal road distances in both directions
    b) Identical traffic conditions
    c) One-way streets or direction-dependent travel times
    d) A fully symmetric distance matrix
    Answer: c) One-way streets or direction-dependent travel times
20. A symmetric TSP cost matrix is normally:
    a) Rectangular
    b) Diagonal only
    c) Filled with zeros
    d) Symmetric about the main diagonal
    Answer: d) Symmetric about the main diagonal
21. The diagonal entries of a TSP cost matrix are often assigned:
    a) Zero or a very large value to prevent self-travel
    b) The smallest travel cost
    c) The average route cost
    d) The number of cities
    Answer: a) Zero or a very large value to prevent self-travel
22. A Hamiltonian cycle is a cycle that:
    a) Uses every edge exactly once
    b) Visits every vertex exactly once and returns to the start
    c) Visits only the nearest cities
    d) Has zero total cost
    Answer: b) Visits every vertex exactly once and returns to the start
23. The TSP seeks the minimum-cost:
    a) Spanning tree
    b) Shortest path between two cities
    c) Hamiltonian cycle
    d) Transportation allocation
    Answer: c) Hamiltonian cycle
24. Which statement distinguishes TSP from the shortest-path problem?
    a) TSP has no objective
    b) Shortest path must visit all cities
    c) TSP does not use networks
    d) TSP requires visiting every city, while shortest path connects selected endpoints
    Answer: d) TSP requires visiting every city, while shortest path connects selected endpoints
25. Which statement distinguishes TSP from a minimum spanning tree problem?
    a) TSP requires a closed tour, whereas a spanning tree contains no cycle
    b) Both always produce identical solutions
    c) A spanning tree visits each node twice
    d) TSP does not involve edge costs
    Answer: a) TSP requires a closed tour, whereas a spanning tree contains no cycle

Section B: TSP Formulation and Characteristics

26. In a common TSP formulation, (x_{ij}=1) means:
    a) City (i) is not connected to city (j)
    b) The tour travels directly from city (i) to city (j)
    c) The cost from (i) to (j) is one
    d) City (i) is the starting city
    Answer: b) The tour travels directly from city (i) to city (j)
27. The TSP decision variable (x_{ij}) is normally:
    a) Continuous and unrestricted
    b) Negative
    c) Binary
    d) Greater than one
    Answer: c) Binary
28. Which is the standard binary restriction?
    a) (x_{ij}\geq1)
    b) (x_{ij}\leq0)
    c) (x_{ij}) unrestricted
    d) (x_{ij}\in{0,1})
    Answer: d) (x_{ij}\in{0,1})
29. A common TSP objective function is:
    a) Minimize (\sum_i\sum_j c_{ij}x_{ij})
    b) Maximize the number of cities
    c) Minimize the number of constraints
    d) Maximize (\sum_i x_{ii})
    Answer: a) Minimize (\sum_i\sum_j c_{ij}x_{ij})
30. In the TSP objective function, (c_{ij}) represents:
    a) The number of cities visited
    b) The travel cost from city (i) to city (j)
    c) The binary decision value
    d) The number of tours
    Answer: b) The travel cost from city (i) to city (j)
31. The constraint (\sum_j x_{ij}=1) generally means:
    a) Every city is entered once
    b) The total cost equals one
    c) Exactly one route leaves city (i)
    d) All cities connect to city (i)
    Answer: c) Exactly one route leaves city (i)
32. The constraint (\sum_i x_{ij}=1) generally means:
    a) Exactly one route leaves city (j)
    b) City (j) is the starting city
    c) Every route enters city (j)
    d) Exactly one route enters city (j)
    Answer: d) Exactly one route enters city (j)
33. Degree constraints alone may produce:
    a) Several disconnected subtours
    b) A guaranteed complete TSP tour
    c) No selected edges
    d) A minimum spanning tree
    Answer: a) Several disconnected subtours
34. Subtour-elimination constraints are added to:
    a) Reduce every edge cost
    b) Prevent disconnected cycles
    c) Create additional cities
    d) Make the matrix symmetric
    Answer: b) Prevent disconnected cycles
35. A subtour is:
    a) A route visiting every city
    b) A path with no repeated nodes
    c) A smaller closed cycle containing only some cities
    d) A route with maximum cost
    Answer: c) A smaller closed cycle containing only some cities
36. A valid TSP solution must contain:
    a) Several independent cycles
    b) At least two subtours
    c) An open path
    d) One complete cycle containing all cities
    Answer: d) One complete cycle containing all cities
37. Which constraints ensure one departure and one arrival at each city?
    a) Degree constraints
    b) Inventory constraints
    c) Balance-sheet constraints
    d) Precedence constraints only
    Answer: a) Degree constraints
38. The Miller-Tucker-Zemlin formulation is commonly used for:
    a) Finding row minima
    b) Eliminating subtours
    c) Calculating queue length
    d) Balancing transportation models
    Answer: b) Eliminating subtours
39. In a complete graph with (n) cities, each city is directly connected to:
    a) One other city
    b) Two cities only
    c) Every other city
    d) No other city
    Answer: c) Every other city
40. A Euclidean TSP uses costs based mainly on:
    a) Inventory levels
    b) Waiting times
    c) Assignment penalties
    d) Geometric distances between locations
    Answer: d) Geometric distances between locations
41. The triangle inequality states that:
    a) Direct travel between two cities is no longer than traveling through an intermediate city
    b) Every triangle has equal sides
    c) All route costs must be integers
    d) Every city has three connections
    Answer: a) Direct travel between two cities is no longer than traveling through an intermediate city
42. A TSP satisfying the triangle inequality is often called:
    a) An unbalanced TSP
    b) A metric TSP
    c) A dynamic TSP
    d) A dummy TSP
    Answer: b) A metric TSP
43. Which version of TSP permits different travel costs in opposite directions?
    a) Symmetric TSP
    b) Euclidean TSP only
    c) Asymmetric TSP
    d) Metric TSP only
    Answer: c) Asymmetric TSP
44. A TSP with customer service deadlines is known as:
    a) A transportation problem
    b) A minimum spanning tree
    c) A pure assignment problem
    d) TSP with time windows
    Answer: d) TSP with time windows
45. In the TSP with time windows, each city must be visited:
    a) Within a specified time interval
    b) At exactly the same time
    c) More than once
    d) Without considering travel time
    Answer: a) Within a specified time interval
46. Which TSP variation includes more than one salesperson or vehicle?
    a) Symmetric TSP
    b) Multiple Traveling Salesman Problem
    c) Euclidean TSP
    d) Sequential TSP
    Answer: b) Multiple Traveling Salesman Problem
47. The vehicle-routing problem extends the TSP by including factors such as:
    a) Only city coordinates
    b) Only symmetric costs
    c) Vehicle capacities and customer demands
    d) No route constraints
    Answer: c) Vehicle capacities and customer demands
48. Which statement best describes a feasible TSP solution?
    a) It contains the cheapest edge only
    b) It visits some cities more than once
    c) It contains several disconnected cycles
    d) It visits each city once and returns to the start
    Answer: d) It visits each city once and returns to the start
49. Changing the chosen starting city in the same cyclic tour generally:
    a) Does not change the total tour cost
    b) Doubles the cost
    c) Makes the tour infeasible
    d) Creates a new set of edges
    Answer: a) Does not change the total tour cost
50. In a symmetric TSP, reversing a tour generally:
    a) Produces a higher cost
    b) Produces the same total cost
    c) Makes the route infeasible
    d) Removes one city
    Answer: b) Produces the same total cost

Section C: Exact Methods for Solving TSP

51. Which method evaluates every possible tour?
    a) Nearest-neighbor method
    b) Genetic algorithm
    c) Brute-force enumeration
    d) Simulated annealing
    Answer: c) Brute-force enumeration
52. The main disadvantage of brute-force enumeration is:
    a) It never finds an optimal solution
    b) It requires no data
    c) It applies only to asymmetric cases
    d) Computation grows factorially with the number of cities
    Answer: d) Computation grows factorially with the number of cities
53. Brute-force enumeration is practical mainly for:
    a) Small TSP instances
    b) Very large global routing problems
    c) Problems with thousands of cities
    d) Dynamic vehicle-routing systems only
    Answer: a) Small TSP instances
54. Which exact method systematically divides the problem into smaller subproblems?
    a) Nearest neighbor
    b) Branch and bound
    c) 2-opt
    d) Savings heuristic
    Answer: b) Branch and bound
55. In branch and bound, a branch represents:
    a) A completed optimal solution only
    b) A random route
    c) A decision that divides the solution space
    d) A dummy city
    Answer: c) A decision that divides the solution space
56. A lower bound in branch and bound is used to:
    a) Increase route cost
    b) Determine the number of cities
    c) Add subtours
    d) Estimate the best possible value within a branch
    Answer: d) Estimate the best possible value within a branch
57. A branch can be pruned when its lower bound is:
    a) No better than the best known feasible solution
    b) Equal to zero
    c) Lower than every edge cost
    d) Based on a symmetric matrix
    Answer: a) No better than the best known feasible solution
58. The best known feasible solution in branch and bound provides:
    a) A lower bound for minimization
    b) An upper bound for minimization
    c) The number of branches
    d) A subtour-elimination constraint
    Answer: b) An upper bound for minimization
59. Which technique can supply a lower bound for symmetric TSP?
    a) A random complete tour
    b) Row reduction only
    c) A minimum spanning tree-based relaxation
    d) A dummy assignment
    Answer: c) A minimum spanning tree-based relaxation
60. Branch and bound guarantees the optimal solution when:
    a) Only the first branch is examined
    b) A heuristic route is accepted immediately
    c) No bounds are calculated
    d) The search is completed correctly without premature termination
    Answer: d) The search is completed correctly without premature termination
61. Dynamic programming solves TSP by:
    a) Combining optimal solutions of smaller subsets of cities
    b) Selecting only nearest cities
    c) Randomly changing routes
    d) Ignoring previously solved subproblems
    Answer: a) Combining optimal solutions of smaller subsets of cities
62. The Held-Karp algorithm is an example of:
    a) Greedy search
    b) Dynamic programming
    c) Simulated annealing
    d) Ant-colony optimization
    Answer: b) Dynamic programming
63. Held-Karp dynamic programming stores information about:
    a) Only the starting city
    b) Complete tours only
    c) Subsets of visited cities and ending cities
    d) Transportation supplies
    Answer: c) Subsets of visited cities and ending cities
64. Compared with brute force, Held-Karp dynamic programming:
    a) Has constant complexity
    b) Is always polynomial
    c) Cannot find an optimum
    d) Improves computation but remains exponential
    Answer: d) Improves computation but remains exponential
65. Which exact approach formulates TSP using binary decision variables?
    a) Integer linear programming
    b) Queuing analysis
    c) Replacement analysis
    d) Forecasting
    Answer: a) Integer linear programming
66. In an integer-programming TSP model, subtour constraints are needed because:
    a) The objective is nonlinear
    b) Degree constraints alone can create disconnected cycles
    c) Travel costs may be negative
    d) Every city must be visited twice
    Answer: b) Degree constraints alone can create disconnected cycles
67. A cutting-plane method solves TSP by:
    a) Removing cities from the model
    b) Adding dummy routes
    c) Adding violated constraints as they are identified
    d) Replacing costs with profits
    Answer: c) Adding violated constraints as they are identified
68. In a branch-and-cut method, branch and bound is combined with:
    a) Simulation
    b) Nearest-neighbor search
    c) Inventory control
    d) Cutting planes
    Answer: d) Cutting planes
69. Which method is widely used by modern exact TSP solvers?
    a) Branch and cut
    b) Northwest Corner Method
    c) Hungarian row reduction only
    d) Exponential smoothing
    Answer: a) Branch and cut
70. An LP relaxation of a TSP model is obtained by:
    a) Removing the objective function
    b) Allowing binary variables to take fractional values
    c) Making all costs equal
    d) Adding more cities
    Answer: b) Allowing binary variables to take fractional values
71. The LP-relaxation value in a minimization TSP gives:
    a) An upper bound only
    b) An exact tour automatically
    c) A lower bound on the integer optimum
    d) No useful information
    Answer: c) A lower bound on the integer optimum
72. Exact methods are most appropriate when:
    a) A quick approximate answer is always sufficient
    b) The problem contains no objective
    c) No computational resources are available
    d) Proving optimality is important
    Answer: d) Proving optimality is important
73. Which exact method is usually easiest to understand for very small TSPs?
    a) Complete enumeration
    b) Ant-colony optimization
    c) Tabu search
    d) Genetic algorithms
    Answer: a) Complete enumeration
74. The main advantage of branch and bound over complete enumeration is that it:
    a) Never uses bounds
    b) Avoids exploring branches that cannot improve the best solution
    c) Examines every tour twice
    d) Produces only approximate answers
    Answer: b) Avoids exploring branches that cannot improve the best solution
75. Which statement about exact TSP algorithms is correct?
    a) They always run quickly
    b) They require symmetric costs
    c) They can certify that a solution is optimal
    d) They never use heuristics
    Answer: c) They can certify that a solution is optimal

Section D: Heuristic and Metaheuristic Methods

76. A heuristic method is designed mainly to:
    a) Guarantee the optimal solution in all cases
    b) Enumerate every possible tour
    c) Eliminate the objective function
    d) Find a good solution relatively quickly
    Answer: d) Find a good solution relatively quickly
77. The nearest-neighbor heuristic begins by:
    a) Selecting a starting city
    b) Calculating a minimum spanning tree only
    c) Adding subtour constraints
    d) Solving an integer program
    Answer: a) Selecting a starting city
78. At each step, the nearest-neighbor method selects:
    a) The farthest unvisited city
    b) The nearest unvisited city
    c) A random visited city
    d) The city with the highest demand
    Answer: b) The nearest unvisited city
79. After all cities are visited, nearest neighbor:
    a) Stops at the last city
    b) Deletes the first city
    c) Returns to the starting city
    d) Repeats the entire route
    Answer: c) Returns to the starting city
80. A disadvantage of nearest neighbor is that:
    a) It cannot create a feasible tour
    b) It requires factorial computation
    c) It always gives the worst route
    d) It can make poor early choices that lead to a costly tour
    Answer: d) It can make poor early choices that lead to a costly tour
81. One way to improve nearest-neighbor results is to:
    a) Run it from several different starting cities
    b) Use only the first city
    c) Ignore return-to-start cost
    d) Remove expensive cities
    Answer: a) Run it from several different starting cities
82. The cheapest-link algorithm repeatedly chooses:
    a) The longest available edge
    b) The cheapest available edge that does not violate tour conditions
    c) Only edges from the starting city
    d) Random edges
    Answer: b) The cheapest available edge that does not violate tour conditions
83. In the cheapest-link method, an edge should not be selected if it:
    a) Has a positive cost
    b) Connects two unvisited cities
    c) Gives a city degree greater than two or creates a premature subtour
    d) Is shorter than the average edge
    Answer: c) Gives a city degree greater than two or creates a premature subtour
84. The 2-opt method improves a tour by:
    a) Adding two new cities
    b) Deleting the objective function
    c) Replacing all edges
    d) Removing two edges and reconnecting the tour differently
    Answer: d) Removing two edges and reconnecting the tour differently
85. A 2-opt move is accepted when it:
    a) Reduces the total tour length
    b) Increases the number of cities
    c) Creates a subtour
    d) Duplicates a city
    Answer: a) Reduces the total tour length
86. The 3-opt method differs from 2-opt because it:
    a) Uses only three cities
    b) Removes three edges before reconnecting the tour
    c) Guarantees global optimality
    d) Applies only to asymmetric TSP
    Answer: b) Removes three edges before reconnecting the tour
87. Local-search methods such as 2-opt may stop at:
    a) An infeasible route
    b) A guaranteed global optimum
    c) A local optimum
    d) A transportation solution
    Answer: c) A local optimum
88. A local optimum is a solution that:
    a) Is optimal among all possible tours
    b) Has zero cost
    c) Contains no cities
    d) Cannot be improved by the chosen local moves
    Answer: d) Cannot be improved by the chosen local moves
89. Simulated annealing may accept a worse solution in order to:
    a) Escape a local optimum
    b) Guarantee a lower bound
    c) Create a dummy city
    d) Reduce the number of variables
    Answer: a) Escape a local optimum
90. In simulated annealing, the probability of accepting worse moves generally:
    a) Increases as the algorithm progresses
    b) Decreases as temperature falls
    c) Is always zero
    d) Is unrelated to temperature
    Answer: b) Decreases as temperature falls
91. Tabu search uses a tabu list to:
    a) Store all city coordinates
    b) Calculate exact lower bounds
    c) Prevent recently visited moves or solutions from being repeated immediately
    d) Remove the starting city
    Answer: c) Prevent recently visited moves or solutions from being repeated immediately
92. The main purpose of tabu search is to:
    a) Enumerate all tours
    b) Solve only symmetric problems
    c) Keep every solution feasible automatically
    d) Guide local search beyond local optima
    Answer: d) Guide local search beyond local optima
93. A genetic algorithm represents possible TSP tours as:
    a) Chromosomes or individuals
    b) Queue lengths
    c) Transportation supplies
    d) Shadow prices
    Answer: a) Chromosomes or individuals
94. In genetic algorithms, crossover is used to:
    a) Eliminate all cities
    b) Combine information from parent solutions
    c) Guarantee optimality
    d) Calculate exact bounds
    Answer: b) Combine information from parent solutions
95. Mutation in a genetic algorithm helps:
    a) Keep every route unchanged
    b) Remove the objective
    c) Maintain diversity in the population
    d) Convert the model into a linear program
    Answer: c) Maintain diversity in the population
96. Ant-colony optimization is inspired by:
    a) Human accounting systems
    b) Transportation balancing
    c) Project scheduling
    d) The pheromone-based behavior of ants
    Answer: d) The pheromone-based behavior of ants
97. In ant-colony optimization, stronger pheromone trails generally:
    a) Increase the probability that an edge will be selected
    b) Prohibit an edge
    c) Make every route equal
    d) Remove the need for distance information
    Answer: a) Increase the probability that an edge will be selected
98. Christofides’ algorithm is designed for:
    a) Any asymmetric TSP without restrictions
    b) Metric symmetric TSP
    c) Queuing problems
    d) Assignment problems only
    Answer: b) Metric symmetric TSP
99. For metric symmetric TSP, Christofides’ algorithm guarantees a tour no more than:
    a) Twice the optimum in every case
    b) Three times the optimum
    c) 1.5 times the optimal tour length
    d) Exactly equal to the optimum
    Answer: c) 1.5 times the optimal tour length
100. Which statement best summarizes TSP solution methods?
     a) Heuristics always prove optimality
     b) Exact methods are always faster than heuristics
     c) One method is best for every instance
     d) Exact methods seek certified optima, while heuristics trade guaranteed optimality for speed
     Answer: d) Exact methods seek certified optima, while heuristics trade guaranteed optimality for speed