This grant provides funding for the investigation of theory and computational strategies for solving dense mixed integer programming (MIP) problems. Prior work has focused on sparse MIP problems, but in many applications of MIP technology, the MIP models are often dense. The research will investigate the facial structure of the independent set polytope via the construction of high-dimensional conflict hypergraphs. Specifically, various structures such as hyper-cliques, hyper-odd holes, hyper-odd antiholes, hyper-webs and hyper-antiwebs will be identified on the conflict hypergraph, and valid inequalities and facet-defining properties will be derived. To investigate the complexity, there will be an analysis on the ranks of the cutting planes associated with the hypergraphical structures. For computational strategies, the research will generalize a separation algorithm for identifying odd holes in hypergraphs, develop fast heuristics for generating the hyper-cliques, and implement the associated cutting planes within a parallel cutting plane and branch-and-cut environment to gauge their effectiveness and performance.
If successful, the results of the research will advance the frontiers of knowledge in integer programming in several areas. First, it will lead to fundamental theoretical advances. Second, from a computational standpoint, it will offer new directions of research related to separation strategies for hypergraphic structures. The research will also have an impact in several application areas. Dense MIP problems arise naturally in many medical applications, including constrained discriminant analysis for medical diagnosis; brachytherapy cancer treatment; and medical imaging. The ability to solve the associated MIP problem instances will help to advance the medical frontiers. The research will also lead to advances in finance and business, including market-share problems, and the wide range of applications that involve classification (constrained discrimination), such as credit lending prediction, market trends, and consumer preference prediction.
