Computational techniques for difficult integer programs

In this thesis we develop problem-specific computational techniques for solving difficult integer programs. We describe three integer programs typically regarded as difficult : the Set Partitioning Problem, a Cardinality constrained Least Squares Problem, and the Set Covering Problem consisting of triples. We present in each chapter techniques for solving each problem type. The techniques we introduce include a novel branching strategy in the Branch and Bound algorithm, variable(column) aggregation approach for constructing relaxations, and lifting to find facet-defining inequalities. The main topic in each chapter touches on a different area but the thesis demonstrates the wide variety of techniques that may make appreciable difference in our ability to effectively solve difficult integer programs. Computational experiments are performed to demonstrate that our techniques are useful for solving difficult integer programs.