×

Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs. (English) Zbl 1091.90040

Summary: We present a linearization strategy for mixed 0-1 quadratic programs that produces small formulations with tight relaxations. It combines constructs from a classical method of Glover and a more recent reformulation-linearization technique (RLT). By using binary identities to rewrite the objective, a variant of the first method results in a concise formulation with the level-1 RLT strength. This variant is achieved as a modified surrogate dual of a Lagrangian subproblem to the RLT. Special structures can be exploited to obtain reductions in problem size, without forfeiting strength. Preliminary computational experience demonstrates the potential of the new representations.

MSC:

90C09 Boolean programming
90C20 Quadratic programming

Software:

Knapsack
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] W. Adams, R. Forrester, A simple recipe for mixed 0-1 linearizations, Operations Research Letters, to appear.; W. Adams, R. Forrester, A simple recipe for mixed 0-1 linearizations, Operations Research Letters, to appear. · Zbl 1076.90030
[2] Adams, W.; Johnson, T., Improved linear programming-based lower bounds for the quadratic assignment problem, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 16, 43-76 (1994) · Zbl 0819.90049
[3] Adams, W.; Sherali, H., A tight linearization and an algorithm for zero-one quadratic programming problems, Management Sci., 32, 1274-1290 (1986) · Zbl 0623.90054
[4] Adams, W.; Sherali, H., Linearization strategies for a class of zero-one mixed integer programming problems, Oper. Res., 38, 217-226 (1990) · Zbl 0724.90046
[5] Adams, W.; Sherali, H., Mixed-integer bilinear programming problems, Math. Programming, 59, 279-305 (1993) · Zbl 0801.90085
[6] Benders, J., Partitioning procedures for solving mixed-variables programming problems, Numer. Math., 4, 238-252 (1962) · Zbl 0109.38302
[7] Billionnet, A.; Calmels, F., Linear programming for the 0-1 quadratic knapsack problem, European J. Oper. Res., 92, 310-325 (1996) · Zbl 0912.90221
[8] Burkard, R.; Bönniger, T., A heuristic for quadratic Boolean programs with applications to quadratic assignment problems, European J. Oper. Res., 13, 374-386 (1983) · Zbl 0509.90058
[9] Burkard, R.; Derigs, U., Assignment and matching problemssolution methods with FORTRAN-programs, (Lecture Notes in Economics and Mathematical Systems, Vol. 184 (1980), Springer: Springer Berlin), 99-148
[10] Caprara, A.; Pisinger, D.; Toth, P., Exact solution of the quadratic knapsack problem, INFORMS J. Comput., 11, 125-137 (1999) · Zbl 1034.90521
[11] Glover, F., Improved linear integer programming formulations of nonlinear integer programs, Management Sci., 22, 455-460 (1975) · Zbl 0318.90044
[12] Glover, F., An improved MIP formulation for products of discrete and continuous variables, J. Inform. Optim. Sci., 5, 469-471 (1984)
[13] Hahn, P.; Grant, T., Lower bounds for the quadratic assignment problem based upon a dual formulation, Oper. Res., 46, 912-922 (1998) · Zbl 0979.90100
[14] Hahn, P.; Hightower, W.; Johnson, T.; Guignard-Spielberg, M., Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem, Yugoslav J. Oper. Res., 11, 41-60 (2001)
[15] T. Johnson, New linear programming-based solution procedures for the quadratic assignment problem, Ph.D. Dissertation, Department of Mathematical Sciences, Clemson University, 1992.; T. Johnson, New linear programming-based solution procedures for the quadratic assignment problem, Ph.D. Dissertation, Department of Mathematical Sciences, Clemson University, 1992.
[16] Kaufman, L.; Broeckx, F., An algorithm for the quadratic assignment problem using Benders’ decomposition, European J. Oper. Res., 2, 207-211 (1978) · Zbl 0378.90065
[17] Krarup, J.; Pruzan, P., Computer aided-layout design, (Mathematical Programming Study, Vol. 9 (1978), North-Holland Publishing Company: North-Holland Publishing Company Amsterdam), 75-94 · Zbl 0413.90058
[18] R. Lougee-Heimer, W. Adams, A conditional logic approach for strengthening mixed 0-1 linear programs, Ann. Oper. Res., to appear.; R. Lougee-Heimer, W. Adams, A conditional logic approach for strengthening mixed 0-1 linear programs, Ann. Oper. Res., to appear. · Zbl 1091.90057
[19] Lovász, L.; Schrijver, S., Cones of matrices and set-functions and 0-1 optimization, SIAM J. Optim., 1, 166-190 (1991) · Zbl 0754.90039
[20] Michelon, P.; Veilleux, L., Lagrangean methods for the 0-1 quadratic knapsack problem, European J. Oper. Res., 92, 326-341 (1996) · Zbl 0912.90222
[21] Nugent, C.; Vollmann, T.; Ruml, J., An experimental comparison of techniques for the assignment of facilities to locations, Oper. Res., 16, 150-173 (1968)
[22] Sherali, H.; Adams, W., 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
[23] Sherali, H.; Adams, W., A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems, Discrete Appl. Math., 52, 83-106 (1994) · Zbl 0819.90064
[24] Sherali, H.; Adams, W., A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA · Zbl 0926.90078
[25] Sherali, H.; Adams, W.; Driscoll, P., Exploiting special structures in constructing a hierarchy of relaxations for 0-1 mixed integer problems, Oper. Res., 46, 396-405 (1998) · Zbl 0979.90090
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.