A Modified Benders' Partitioning Algorithm for Mixed Integer Programming

Abstract

As applied to mixed-integer programming, Benders' original work made two primary contributions: (1) development of a “pure integer” problem (Problem P ) that is equivalent to the original mixed-integer problem, and (2) a relaxation algorithm for solving Problem P that works iteratively on an LP problem and a “pure integer” problem. In this paper a modified algorithm for solving Problem P is proposed, in which the solution of a sequence of integer programs is replaced by the solution of a sequence of linear programs plus some (hopefully few) integer programs. The modified algorithm will still allow for taking advantage of any special structures (e.g., an LP subproblem that is a “network problem”) just as in Benders' original algorithm. The modified Benders' algorithm is explained and limited computational results are given.