The theory of simultaneous lifting: constellations in conflict hypergraphs

Abstract

Integer programming (IP) is a powerful technique used by many companies and organizations to determine optimal strategies for making decisions and managing resources to achieve their goals. One class of IP problems is the multiple knapsack (MK) problem. However, MK and other IP problems, are extremely complicated since they are ${\cal NP}$-hard problems. Furthermore, there exist numerous instances that can not be solved.

One technique commonly used to reduce the solution time for IP problems is lifting. This method, introduced by Gomory, takes an existing valid inequality and strengthens it. Lifting has the potential to form facet defining inequalities, which are the strongest inequalities to solve an IP problem. As a result, lifting is frequently used in integer programming applications.

This research takes a broad approach to simultaneous lifting and provides its theoretical background for. The underlying hypergraphic structure for simultaneous lifting in an MK problem is identified and called a constellation. A constellation contains two hypercliques and multiple hyperstars from various conflict hypergraphs. Theoretical results demonstrate that a constellation induces valid inequalities that could be obtained by simultaneous lifting. Moreover, these constellation inequalities can be facet defining.

The primary advancements, constellations and the associated valid inequalities, of this thesis are theoretical in nature. By providing the theory behind simultaneous lifting, researchers should be able to apply this knowledge to develop new algorithms that enable simultaneous lifting to be performed faster and over more complex integer programs.