Pivot and Shift – a mixed integer programming heuristic

Pivot and Shift is an extension to general mixed integer programming of Pivot and Complement, the well-known 1980s heuristic for pure 0–1 programs. It is essentially a sophisticated rounding procedure, amended with two variants of a neighborhood search. The rounding takes the form of several pivot types meant to eliminate from the basis all integer-constrained variables while keeping the objective function value close to the LP optimum, followed by up and down shifts in the value of the nonbasic integer variables. The neighborhood search is akin to the local branching procedure proposed by Fischetti and Lodi. When Pivot and Shift is joined to an efficient MIP solver, the combined procedure finds better solutions faster than the MIP solver alone. The procedure has been tested on a multitude of test problems available from the literature or the web.