Problem 1: (15 points) Evaluate AFIT SCP Solver -
1.a Consider SCP test suites: OR-Library, papers, …
Select at least three test problems - small, medium. large
dimension (show details) and generate and discuss results
1.b Generate an explicit graph search tree diagram for medium
SCP test example (limit search node presentation)
1.c Discuss Complexity of SCP PD and Christofides’ algorithm,
and complexity of AFIT SCP Solver implementation.
Problem 2: (10 points)
2.a Define a new SCP Heuristic (English and math/symbolic)
2.b Define a SCP approximation algorithm in Talbi’s form
Discuss approximation results with optimal results (theory?)
2.c If possible, compare results with two different SCP
algorithm implementations.
Problem 3: (5 points)
3.a Have “good" software engineering principles (design and
implementation) been employed in the AFIT SCP Solver?
Regarding the implementation, discuss:
• Ease of understanding of code (suggested modifications?)
• Ease of use of standard interface (modifications?)
Problem 4: (5 points)
4.a Define a real-world (not pedagogical) discrete combinatoric
optimization SCP NPC problem associated with an Air Force
application (Networks, UAVs, Robotics, Sensors, …)
Report: Evaluate using Barr and Talbi Section 1.7 suggestions with timing results and good references.
Extra credit: Implement in AFIT SCP code ability to generate search graph data.
