Generating cutting planes through inequality merging on multiple variables in knapsack problems

Abstract

Integer programming is a field of mathematical optimization that has applications across a wide variety of industries and fields including business, government, health care and military. A commonly studied integer program is the knapsack problem, which has applications including project and portfolio selection, production planning, inventory problems, profit maximization applications and machine scheduling. Integer programs are computationally difficult and currently require exponential effort to solve.

Adding cutting planes is a way of reducing the solving time of integer programs. These cutting planes eliminate linear relaxation space. The theoretically strongest cutting planes are facet defining inequalities.

This thesis introduces a new class of cutting planes called multiple variable merging cover inequalities (MVMCI). The thesis presents the multiple variable merging cover algorithm (MVMCA), which runs in linear time and produces a valid MVMCI. Under certain conditions, an MVMCI can be shown to be a facet defining inequality. An example demonstrates these advancements and is used to prove that MVMCIs could not be identified by any existing techniques.

A small computational study compares the computational impact of including MVMCIs. The study shows that finding an MVMCI is extremely fast, less than .01 seconds. Furthermore, including an MVMCI improved the solution time required by CPLEX, a commercial integer programming solver, by 6.3% on average.