Two applications of combinatorial optimization

This thesis presents two applications of combinatorial optimization. The first part contains a detailed description of a conference scheduling problem. We model the problem as a symmetric clustering problem, or a variant of minimum k-partition we call capacitated k-partition. This problem is proved to be NP-hard to solve to optimality, and further, unless P = NP, no constant factor polynomial-time approximation algorithm exists. We also propose a branch-and-cut algorithm with semidefinite programming relaxations enhanced with polyhedral cuts found at each tree node. Many cutting planes are demonstrated to be satisfied, or provably close to being satisfied, by semidefinite matrices in the variable space [−1/(k − 1), 1], which is in contrast to basic linear programming relaxations. Our algorithm also relies on a novel heuristic strategy when attempting to generate feasible solutions at every tree node. We test an implementation of our algorithm on random k-partition instances as well as a particular conference data set which comes from the 13th Annual INFORMS Computing Society Conference and was solved to within 0.85% of optimum in under 4 hours. The results here are promising and provide a starting point for future projects. In the second part, we describe a project called the Boat Allocation Module, where a team comprised of United States Coast Guard (USCG) analysts, and Command, Control, and Interoperability Center for Advanced Data Analysis researchers worked together in building a decision support system for USCG analysts. The software was designed to solve the problem of allocating boats of the Coast Guard to the nation’s coastal stations, so as to meet station requirements, while adhering to particular budget and capability limitations. We model the problem as a resource allocation problem and prove that it is NP-hard to solve. We relax the problem slightly by allowing a single boat type to be shared, or assigned among disjoint subsets of stations rather than to individual stations, but show that implementing “seasonal” sharing is NP-hard. A mixed integer linear programming formulation is proposed, and an implementation within a decision support system for USCG analysts is tested as per USCG Verification and Validation standards. The software provides an intuitive interface and allows for a variety of scenarios. Tests have shown that our tool may save the Coast Guard millions of dollars a year.