zbMATH — the first resource for mathematics

A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems. (English) Zbl 0819.90064
Summary: This paper is concerned with the generation of tight equivalent representations for mixed-integer zero-one programming problems. For the linear case, we propose a technique which first converts the problem into a nonlinear, polynomial mixed-integer zero-one problem by multiplying the constraints with some suitable \(d\)-degree polynomial factors involving the \(n\) binary variables, for any given \(d\in \{0,\dots, n\}\), and subsequently linearizes the resulting problem through appropriate variable transformations. As \(d\) varies from zero to \(n\), we obtain a hierarchy of relaxations spanning from the ordinary linear programming relaxation to the convex hull of feasible solutions. The facets of the convex hull of feasible solutions in terms of the original problem variables are available through a standard projection operation. We also suggest an alternate scheme for applying this technique which gives a similar hierarchy of relaxations, but involving fewer “complicating” constraints. Techniques for tightening intermediate level relaxations, and insights and interpretations within a disjunctive programming framework are also presented. The methodology readily extends to multilinear mixed-integer zero-one polynomial programming problems in which the continuous variables appear linearly in the problem.

90C11 Mixed integer programming
90C09 Boolean programming
Full Text: DOI
[1] Adams, W.P.; Sherali, H.D., Linearization strategies for a class of zero—one mixed integer programming problems, Oper. res., 38, 2, 217-226, (1990) · Zbl 0724.90046
[2] Adams, W.P.; Sherali, H.D., Mixed-integer bilinear programming problems, Math. programming, 59, 279-305, (1993) · Zbl 0801.90085
[3] Balas, E., Disjunctive programming and a hierarchy of relaxations for discrete optimization problems, SIAM J. algebraic discrete methods, 6, 466-486, (1985) · Zbl 0592.90070
[4] Balas, E.; Ceria, S.; Cornuejols, G., A lift-and-project cutting plane algorithm for mixed 0-1 programs, Math. programming, 58, 295-324, (1993) · Zbl 0796.90041
[5] Boros, E.; Crama, Y.; Hammer, P.L., Upper bounds for quadratic 0-1 maximization problems, () · Zbl 0699.90073
[6] Lovász, L.; Schrijver, A., Cones of matrices and setfunctions, and 0-1 optimization, (), Department of Operations Research, Statistics, and System Theory · Zbl 0754.90039
[7] Sherali, H.D.; Adams, W.P., A hierarchy of relaxations between the continuous and convex hull representations for zero—one programming problems, SIAM J. discrete math., 3, 411-430, (1990) · Zbl 0712.90050
[8] Sherali, H.D.; Allameddine, A., A new reformulation-linearization technique for bilinear programming problems, J. global optim., 2, 379-410, (1992) · Zbl 0791.90056
[9] Sherali, H.D.; Tuncbilek, C.H., A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, J. global optim., 2, 101-112, (1992) · Zbl 0787.90088
[10] Sherali, H.D.; Tuncbilek, C.H., A squared-Euclidean distance location—allocation problem, Naval res. logist. quarterly, 39, 447-469, (1992) · Zbl 0763.90061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.