A finiteness proof for modified dantzig cuts in integer programming

V. J. Bowman and G. L. Nemhauser

Naval Research Logistics Quarterly, 1970, vol. 17, issue 3, 309-313

Abstract: Let \documentclass{article}\pagestyle{empty}\begin{document}$$ x_i = y_{i0} - \sum\limits_{j \in R} {y_{ij} x_j, i = 0},...,m $$\end{document} be a basic solution to the linear programming problem \documentclass{article}\pagestyle{empty}\begin{document}$$ \max \,x_0 = \sum {{}_jc_j x_j } $$\end{document} subject to: \documentclass{article}\pagestyle{empty}\begin{document}$$ \sum {{}_ja_{ij} x_j } = b_i, i=1,...,m, $$\end{document} where R is the index set associated with the nonbasic variables. If all of the variables are constrained to be nonnegative integers and xu is not an integer in the basic solution, the linear constraint \documentclass{article}\pagestyle{empty}\begin{document}$$\sum\limits_{j \in R_u^* } {x_j \ge 1,} \,R_u^* = \{ j|j \in R\,{\rm\, and}\,\,y_{uj} \ne {\rm integer}\}$$\end{document} is implied. We prove that including these “cuts” in a specified way yields a finite dual simplex algorithm for the pure integer programming problem. The relation of these modified Dantzig cuts to Gomory cuts is discussed.

Date: 1970
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1002/nav.3800170307

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:17:y:1970:i:3:p:309-313

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().