Pivot,Cut, and Dive: a heuristic for 0-1 mixed integer programming |
| |
| Authors: | Jonathan Eckstein Mikhail Nediak |
| |
| Institution: | (1) Business School and RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854, USA;(2) Queen’s School of Business, Queen’s University, Goodes Hall, 143 Main St., Kingston, K7L 3N6, Ontario, Canada |
| |
| 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. |
| |
| Keywords: | Integer programming Simplex pivot Convexity cut |
| 本文献已被 SpringerLink 等数据库收录！ |
|
