Valid Linear Programming Bounds for Exact Mixed-Integer Programming

Fast computation of valid linear programming (LP) bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for this application. The algorithm corrects approximate LP dual solutions to be exactly...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2013-03, Vol.25 (2), p.271-284
Main Authors: Steffy, Daniel E, Wolter, Kati
Format: Article
Language:English
Subjects:
Algorithms
Branch and bound algorithms
Design
exact computation
Integer programming
Linear programming
Methods
mixed-integer programming
Problem solving
Software
Studies
Traveling salesman problem
Variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Fast computation of valid linear programming (LP) bounds serves as an important subroutine for solving mixed-integer programming problems exactly. We introduce a new method for computing valid LP bounds designed for this application. The algorithm corrects approximate LP dual solutions to be exactly feasible, giving a valid bound. Solutions are repaired by performing a projection and a shift to ensure all constraints are satisfied; bound computations are accelerated by reusing structural information through the branch-and-bound tree. We demonstrate this method to be widely applicable and faster than solving a sequence of exact LPs. Several variations of the algorithm are described and computationally evaluated in an exact branch-and-bound algorithm within the mixed-integer programming framework SCIP (Solving Constraint Integer Programming).
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.1120.0501