Generating an original Cutting-plane Algorithm in Three Sets

Abstract

Integer programs (IP) are a commonly researched class of problems used by governments and businesses to improve decision making through optimal resource allocation and scheduling. However, integer programs require an exponential amount of effort to solve and in some instances a feasible solution is unknown even with the most powerful computers.

There are several methods commonly used to reduce the solution time for IPs. One such approach is to generate new valid inequalities through lifting. Lifting strengthens a valid inequality by changing the coefficients of the variables in the inequality. Lifting can result in facet defining inequalities, which are the theoretically strongest inequalities.

This thesis introduces the Cutting-plane Algorithm in Three Sets (CATS) that can help reduce the solution time of integer programs. CATS uses synchronized simultaneous lifting to generate a new class of previously undiscovered valid inequalities. These inequalities are based upon three sets of indices from a binary knapsack integer program, which is a commonly studied integer program. CATS requires quartic effort times the number of inequalities generated. Some theoretical results describe easily verifiable conditions under which CATS inequalities are facet defining.

A small computational study shows CATS obtains about an 8.9% percent runtime improvement over a commercial IP software. CATS preprocessing time is fast and requires an average time of approximately .032 seconds to perform. With the exciting new class of inequalities produced relatively quickly compared to the solution time, CATS is advantageous and should be implemented to reduce solution time of many integer programs.