Concave extensions for nonlinear 0-1 maximization problems

Crama, Yves

doi:10.1007/BF01582138

Request a copy

Article (Scientific journals)

Concave extensions for nonlinear 0-1 maximization problems

Crama, Yves

1993 • In Mathematical Programming, 61, p. 53-60

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/217335

DOI
10.1007/BF01582138

Files (2)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Concave extensions MathProg 1993.pdf

Publisher postprint (389.14 kB)

Request a copy

Full Text Parts

RRR 32-88, MAY 1988.pdf

Author preprint (1.03 MB)

Long unpublished version

Request a copy

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Nonlinear 0-1 optimization; concave extension; concave envelope; linearization; balanced matrices

Abstract :

[en] A well-known linearization technique for nonlinear 0-1 maximization problems can be viewed as extending any polynomial in 0-1 variables to a concave function defined on [0, 1]. Some properties of this "standard" concave extension are investigated. Polynomials for which the standard extension coincides with the concave envelope are characterized in terms of integrality of a certain polyhedron or balancedness of a certain matrix. The standard extension is proved to be identical to another type of concave extension, defined as the lower envelope of a class of affine functions majorizing the given polynomial.

Disciplines :

Mathematics
Quantitative methods in economics & management

Author, co-author :

Crama, Yves ; Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production

Language :

English

Title :

Concave extensions for nonlinear 0-1 maximization problems

Publication date :

1993

Journal title :

Mathematical Programming

ISSN :

0025-5610

eISSN :

1436-4646

Publisher :

Springer

Volume :

Pages :

53-60

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 21 December 2017

Statistics

Number of views

54 (2 by ULiège)

Number of downloads

0 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Ada W.P., Dearing P.M. “On the equivalence between roof duality and Lagrangian duality for unconstrained 0–1 quadratic programming problems,” Technical Report URI-061, Clemson University, Clemson, SC; 1988.
Balas E. Notes of the three lectures given at Cornell University in the distinguished lecturer series, GSIA, Carnegie Mellon University, Pittsburgh, PA; 1987.
Balas E., Mazzola J.B. (1984) Nonlinear 0–1 programming: I. Linearization techniques. Mathematical Programming 30:1-22.
.
Crama Y. “Linearization techniques and concave extensions in nonlinear 0–1 optimization,” RUTCOR Research Report 32-88, Rutgers University, New Brunswick, NJ; 1988.
Crama Y. (1989) Recognition problems for special classes of polynomials in 0–1 variables. Mathematical Programming 44:139-155.
Crama Y., Hansen P., Jaumard B. (1990) The basic algorithm for pseudo-Boolean programming revisited. Discrete Applied Mathematics 29:171-185.
Falk J.E., Hoffman K.R. (1976) A successive underestimation method for concave minimization problems. Mathematics of Operations Research 1:251-259.
Fortet R. (1960) Applications de l'algèbre de Boole en recherche opérationelle. Revue Française de Recherche Opérationelle 4:17-26.
Glover F., Woolsey E. (1974) Converting the 0–1 polynomial programming problem to a 0–1 linear program. Operations Research 22:180-182.
Granot D., Granot F. (1980) Generalized covering relaxation for 0–1 programs. Operations Research 28:1442-1449.
Granot F., Hammer P.L. (1974) On the role of generalized covering problems. Cahiers du Centre d'Etudes de Recherche Opérationnelle 16:277-289.
Hammer P.L., Hansen P., Simeone B. (1984) Roof duality, complementation and persistency in quadratic 0–1 optimization. Mathematical Programming 28:121-155.
Hammer P.L., Kalantari B. (1989) A bound on the roof duality gap. Combinatorial Optimization , B., Simeone, Lecture Notes in Mathematics, No. 1403, Springer, Berlin; 254-257.
Hammer P.L., Rosenberg I.G. (1974) Linear decomposition of a positive group-Boolean function. Numerische Methoden bei Optimierung, Vol. II , L., Collatz, W., Wetterling, Birkhauser, Basel; 51-62.
Hammer P.L., Rubin A.A. (1970) Some remarks on quadratic programming with 0–1 variables. Revue Française de Recherche Opérationelle et d'Informatique 4:67-79.
Hammer P.L., Rudeanu S. Boolean Methods in Operations Research and Related Areas, Springer, Berlin; 1968.
Hammer P.L., Simeone B. (1989) Quadratic functions of binary variables. Combinatorial Optimization , B., Simeone, Lecture Notes in Mathematics, No. 1403, Springer, Berlin; 1-56.
Hansen P. (1979) Methods of nonlinear 0–1 programming. Annals of Discrete Mathematics 5:53-70.
Hansen P., Lu S.H., Simeone B. (1990) On the equivalence of paved-duality and standard linearization in nonlinear 0–1 optimization. Discrete Applied Mathematics 29:187-193.
Hansen P., Simeone B. (1986) Unimodular functions. Discrete Applied Mathematics 14:269-281.
Karp R.M. (1972) Reducibility among combinatorial problems. Complexity of Computer Computations , R.E., Miller, J.W., Thatcher, Plenum Press, New York; 85-104.
Lovász L. An Algorithmic Theory of Numbers, Graphs and Convexity, Society for Industrial and Applied Mathematics, Philadelphia, PA; 1986.
Lu S.H., Willia A.C. (1987) Roof duality for polynomial 0–1 optimization. Mathematical Programming 37:357-360.
Lu S.H., Willia A.C. “Roof duality and linear relaxation for quadratic and polynomial 0–1 optimization,” RUTCOR Research Report 8-87, Rutgers University, New Brunswick, NJ; 1987.
Rockafellar R.T. Convex Analysis, Princeton University Press, Princeton, NJ; 1970.
Schrijver A. Theory of Linear and Integer Programming, Wiley, Chichester; 1986.
Singer I. (1984) Extensions of functions of 0–1 variables and applications to combinatorial optimization. Numerical Functional Analysis and Optimization 7:23-62.
Truemper K. (1982) Alpha-balanced graphs and matrices and GF(3)-representability of matroids. Journal of Combinatorial Theory Series B 32:112-139.