Pivot, Cut, and Dive: a heuristic for 0–1 mixed integer programming

Pivot, Cut, and Dive: a heuristic for 0–1 mixed integer programming

0.00 Avg rating0 Votes
Article ID: iaor20083411
Country: Netherlands
Volume: 13
Issue: 5
Start Page Number: 471
End Page Number: 503
Publication Date: Oct 2007
Journal: Journal of Heuristics
Authors: ,
Keywords: heuristics
Abstract:

This paper describes a heuristic for 0–1 mixed-integer linear programming problems, focusing on ‘stand-alone’ implementation. Our approach is built around concave ‘merit functions’ measuring solution integrality, and consists of four layers: gradient-based pivoting, probing pivoting, convexity/intersection cutting, and diving on blocks of variables. The concavity of the merit function plays an important role in the first and third layers, as well as in connecting the four layers. We present both the mathematical and software details of a test implementation, along with computational results for several variants.

Reviews

Required fields are marked *. Your email address will not be published.