Abstract
A nonlinear 0–1 program can be restated as a multilinear 0–1 program, which in turn is known to be equivalent to a linear 0–1 program with generalized covering (g.c.) inequalities. In a companion paper [6] we have defined a family of linear inequalities that contains more compact (smaller cardinality) linearizations of a multilinear 0–1 program than the one based on the g.c. inequalities. In this paper we analyze the dominance relations between inequalities of the above family. In particular, we give a criterion that can be checked in linear time, for deciding whether a g.c. inequality can be strengthened by extending the cover from which it was derived. We then describe a class of algorithms based on these results and discuss our computational experience. We conclude that the g.c. inequalities can be strengthened most of the time to an extent that increases with problem density. In particular, the algorithm using the strengthening procedure outperforms the one using only g.c. inequalities whenever the number of nonlinear terms per constraint exceeds about 12–15, and the difference in their performance grows with the number of such terms.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E. Balas, “Facets of the knapsack polytope”,Mathematical Programming 8 (1975) 146–164.
E. Balas and R. G. Jeroslow, “Canonical cuts on the unit hypercube”,SIAM Journal of Applied Mathematics 23 (1972) 61–69.
E. Balas and C. H. Martin, “Pivot and complement-A heuristic for 0–1 programming”,Management Science 26 (1980) 86–96.
E. Balas and J. B. Mazzola, “Linearizing nonlinear 0–1 programs: Some new techniques”. Paper presented at the ORSA/TIMS Meeting in Milwaukee, October 17–19, 1979.
E. Balas and J. B. Mazzola, “Linearizing nonlinear 0–1 programs”, MSRR No. 467, Carnegie-Mellon University, Pittsburgh, PA, October 1980.
E. Balas and J. B. Mazzola, “Nonlinear 0–1 programming: I. Linearization techniques”,Mathematical Programming 30 (1984) 1–21 (this issue).
D. H. Evans, “Modular design—a special case in nonlinear programming”,Operations Research 11 (1963) 637–647.
D. H. Evans, “A note on ‘Modular design—A special case in nonlinear programming”,Operations Research 18 (1970) 562–564.
D. Granot and F. Granot, “Generalized covering relaxation for 0–1 programs”,Operations Research 28 (1980) 1442–1449.
D. Granot, F. Granot and J. Kallberg, “Covering relaxation for positive 0–1 polynomial programs”,Management Science 25 (1979) 264–273.
D. Granot, F. Granot and W. Vaessen, “An accelerated covering relaxation algorithm for solving 0–1 positive polynomial programs”, Working Paper No. 718, University of British Columbia, 1980.
F. Granot and P. L. Hammer, “On the use of Boolean functions in 0–1 programming”,Methods for Operations Research 12 (1971) 154–184.
S.S. Hamlen, “A chance-constrained mixed integer programming model for internal control design”,The Accounting Review LV (1980) 578–593.
P. L. Hammer and S. Rudeanu,Boolean methods in operations research and related areas (Springer, Berlin, New York, 1968).
P. Kolesar. “Testing for vision loss in glaucoma suspects”,Management Science 26 (1980) 439–450.
D. E. Peterson and D. Laughhunn, “Capital expenditure programming and some alternative approaches to risk”,Management Science 17 (1971) 320–336.
A. Pritsker, L. J. Watters and F. Wolfe, “Multiproject scheduling with limited resources: A zero-one programming approach”,Management Science 16 (1969) 622–626.
M. R. Rao, “Cluster analysis and mathematical programming”.Journal of the American Statistical Association 66 (1971) 622–626.
K E. Stecke, “Nonlinear MIP formulations of production planning problems in flexible manufacturing systems“, Working Paper No. 293, GSBA, University of Michigan, March 1982.
K. E. Stecke and J.J. Solberg, “The optimality of unbalanced workloads and machine group sizess for flexible manufacturing systems”. Working Paper No. 290, GSBA, University of Michigan, January 1982.
H. A. Taha, “A Balasian-based algorithm for zero-one polynomial programming”,Management Science 18B (1972) 328–343.
W. Zangwill, “Media selection by decision programming”,Journal of Advertising Research 5 (1965) 30–36.
Author information
Authors and Affiliations
Additional information
Research supported by the National Science Foundation under grant ECS 7902506 and by the Office of Naval Research under contract N00014-75-C-0621 NR 047-048.
Rights and permissions
About this article
Cite this article
Balas, E., Mazzola, J.B. Nonlinear 0–1 programming: II. Dominance relations and algorithms. Mathematical Programming 30, 22–45 (1984). https://doi.org/10.1007/BF02591797
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591797