Constructive Duality in Integer Programming

A new integer programming dual problem is constructed from a reformulation of the integer programming problem. Properties of this integer programming dual problem are developed and it is shown that strong integer programming cuts and surrogate constraints can be derived from optimal dual solutions....

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on applied mathematics 1974-07, Vol.27 (1), p.31-52
Main Authors: Fisher, Marshall L., Shapiro, Jeremy F.
Format: Article
Language:English
Subjects:
Algorithms
Integer programming
Integers
Lagrange multipliers
Lagrangian function
Mathematical duality
Mathematical functions
Mathematical programming
Nonlinear programming
Objective functions
Optimal solutions
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:A new integer programming dual problem is constructed from a reformulation of the integer programming problem. Properties of this integer programming dual problem are developed and it is shown that strong integer programming cuts and surrogate constraints can be derived from optimal dual solutions. A primal-dual ascent algorithm for solution of the integer programming dual problem is presented, and the use of this algorithm in branch-and-bound is explained.
ISSN:0036-1399
1095-712X
DOI:10.1137/0127003