Abstract
A type of program is considered in which, apart from the usual linear constraints, it is required that at least one variable from each of several sets be equal to zero. Applications include complementary pivot theory and concave minimization problems. Cutting planes are generated for the solution of such programs. A geometrical description of the cutting planes explains their meaning.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Lemke, C. E.,On Complementary Pivot Theory, Mathematics of the Decision Sciences, Part 1, Edited by G. B. Dantzig and A. F. Veinott, American Mathematical Society, Providence, Rhode Island, 1968.
Glover, F.,Convexity Cuts, University of Texas, School of Business, Working Paper, 1969.
Balas, E.,Intersection Cuts—A New Type of Cutting Planes for Integer Programming, Operations Research, Vol. 19, No. 1, 1971.
Young, R. D.,New Cuts for a Special Class of 0–1 Integer Programs, Rice University, Research Report, 1968.
Young, R. D.,Hypercylindrically Deduced Cuts in Zero—One Integer Programs, Operations Research, Vol. 19, No. 6, 1971.
Glover, F., andKlingman, D.,The Generalized Lattice Point Problem, University of Colorado, Management Science Report Series, 71-3, 1971.
Additional Bibliography
Gomory, R. E.,An Algorithm for the Mixed Integer Program, RAND Corporation, Report No. P-1885, 1960.
Gomory, R. E.,An Algorithm for Integer Solutions to Linear Programs, Recent Advances in Mathematical Programming, Edited by R. L. Graves and P. A. Wolfe, McGraw-Hill Book Company, New York, 1963.
Tui, H.,Concave Programming Under Linear Constraints, Soviet Mathematics, Vol. 5, No. 6, 1964.
Author information
Authors and Affiliations
Additional information
Communicated by M. Avriel
This research was supported by the Army Research Office, Durham, North Carolina.
Rights and permissions
About this article
Cite this article
Owen, G. Cutting planes for programs with disjunctive constraints. J Optim Theory Appl 11, 49–55 (1973). https://doi.org/10.1007/BF00934290
Issue Date:
DOI: https://doi.org/10.1007/BF00934290