Abstract
This paper analyses a necessary and sufficient optimality condition for quadratic pseudo-Boolean unconstrained problems. It is proved that in general testing any necessary and sufficient optimality condition is a difficult task for anyNP-hard problem. Anɛ-optimality condition is derived together with an approximation scheme to test it.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-completeness. San Francisco, Freeman
Hammer PL (1979) Boolean elements in combinatorial optimization. Annals of Discrete Mathematics 4:51–71
Hammer PL, Rudeanu S (1968) Boolean methods in operations research and related areas. New York Springer Berlin
Hansen P (1979) Methods of nonlinear 0–1 programming. Annals of Discrete Mathematics 5:53–69
Hirriart-Urruty JB (1989) From convex optimization to nonconvex optimization. Part I: Necessary and sufficient conditions for global optimality. Nonsmooth Optimization and Related Topics. Clarke FH, Demyanov V., Giannessi F. (eds.) Plenum Press 219–239
Hirriart-Urruty JB, Lemarechal C (1990) Testing necessary and sufficient conditions for global optimality in the problem of maximizing a convex quadratic function over a convex polyhedron. University Paul Sabatier Toulouse
Long J, Williams AC (1993) On the number of local maxima in quadratic 0–1 programs. Operations Research Letters 13:75–78
Pardalos PM, Rosen JB (1987) Constrained global optimization. Berlin Springer-Verlag
Pardalos PM, Jha S (1992) Complexity of uniqueness and local search in quadratic 0–1 programming. Operations Research Letters 11:119–123
Pardalos PM, Rodgers GP (1990) Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45:131–144
Rockafellar RT (1970) Convex analysis. Princeton University Press
Rosenberg IG (1975) Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d'Etudes de Recherche Opérationelle 17:71–79
Author information
Authors and Affiliations
Additional information
This work has been supported by the “Progetto Finalizzato Trasporti 2”, 93.01799.PF74.
Professor Paolo Carraresi died unexpectedly on March 5, 1994. At the time of his death this paper had been completed. While undertaking the final revision, the other two authors were reminded just how much they were indebted to Professor Carraresi after many years of common work together.
Rights and permissions
About this article
Cite this article
Carraresi, P., Malucelli, F. & Pappalardo, M. Testing optimality for quadratic 0–1 unconstrained problems. ZOR - Methods and Models of Operations Research 42, 295–311 (1995). https://doi.org/10.1007/BF01432506
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01432506