Cutting plane based methods for integer programs

Abstract

A wide variety of integer programs belong to the class of hard combinational optimization problems, and there is no known algorithm to date to solve them in polynomial time. Examples are the multi item lot sizing problems, with or without start-up costs and backlogging, plant location problems and the fixed charge network design problem. These problems are standard in the operations research/management science literature not only because of their close similarity to real life problems. The running times of exact combinatorial algorithms varies exponentially with the size of input data, and hence they are not useful for problems of large size. We study only the uncapacitated versions of the problem. The capacited version needs to be studied seperately, and is outside the scope of this paper.