Abstract
We present a new linearized model for the zero-one quadratic programming problem, whose size is linear in terms of the number of variables in the original nonlinear problem. Our derivation yields three alternative reformulations, each varying in model size and tightness. We show that our models are at least as tight as the one recently proposed in [7], and examine the theoretical relationship of our models to a standard linearization of the zero-one quadratic programming problem. Finally, we demonstrate the efficacy of solving each of these models on a set of randomly generated test instances.
Similar content being viewed by others
References
Adams W.P., Sherali H.D. (1986). A tight linearization and an algorithm for zero-one quadraic programming problems. Manage. Sci. 32(10):1274–1290
Alidaee B., Kochenberger G., Ahmadian A. (1994). 0-1 quadratic programming approach for the optimal solution of two scheduling problems. Int. J. Syst. Sci. 25(2):1–408
Aykin T. (1990). On a quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res. 46:409–411
Burer S., Monteiro R.D.C., Zhang Y. (2001). Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs. SIAM J. Optim. 12:503–521
Caprara A., Pisinger D., Toth P. (1999). Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 11(2):125–137
Chaovalitwongse W., Pardalos P.M., Iasemidis L.D., Shiau D.S., Sackellares J.C. (2005). Dynamical approaches and multi-quadratic integer programming for seizure prediction. Optim. Methods Softw. 20(2–3):389–400
Chaovalitwongse W., Pardalos P.M., Prokopyev O.A. (2004). A new linearization technique for multi-quadratic 0-1 programming problems. Oper. Res. Lett. 32:517–522
Chardaire P., Sutter A. (1995). A decomposition method for quadratic zero-one programming. Manage. Sci. 41(4):704–712
Fortet R. (1959). L’algebre de boole et ses applications en recherche operationnelle. Cahiers du Centre d’Etudes de Recheche Operationnelle 1:5–36
Glover F. (1975). Improved linear integer programming formulations of nonlinear integer problems. Manage. Sci. 22(4):455–460
Glover F., Woolsey E. (1973). Further reduction of zero-one polynomial programming problems to zero-one linear programming problems. Oper. Res. 21(1):156–161
Glover F., Woolsey E. (1974). Converting the 0-1 polynomial programming problem to a 0-1 linear program. Oper. Res. 22(1):180–182
Helme M.P., Magnanti T.L. (1989). Designing satellite communication networks by zero-one quadratic programming. Networks 19:427–450
Iasemidis L.D., Pardalos P.M., Sackellares J.C., Shiau D.-S. (2001). Quadratic binary programming and dynamical system approach to the predictability of epileptic seizures. J. Comb. Optim. 5(1):9–26
Kochenberger G.A., Glover F., Alidaee B., Rego C. (2005). An unconstrained quadratic binary programming approach to the vertex coloring problem. Ann. Oper. Res. 139(1):229–241
Lodi A., Allemand K., Liebling T.M. (1999). An evolutionary heuristic for quadratic 0-1 programming. Eur. J. Oper. Res., 119(3):662–670
Loiola, E.M., de Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P., Querido, T.: A survey for the quadratic assignment problem. Eur. J. Oper. Res. (2006) (to appear)
O’Kelly M.E. (1987). A quadratic integer program for the location of interacting hub facilities. Eur. J. Oper. Res. 32(3):393–404
Palubeckis G. (2004). Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann. Oper. Res. 131:259–282
Pardalos P.M., Chaovalitwongse W., Iasemidis L.D., Sackellares J.C., Shiau D.-S., Carney P.R., Prokopyev O.A., Yatsenko V.A. (2004). Seizure warning algorithm based on optimization and nonlinear dynamics. Math. Program. 101(2):365–385
Pardalos P.M., Rodgers G.P. (1990). Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45:131–144
Sherali H.D., Adams W.P. (1990). A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3(3):411–430
Thoa N.V. (1998). Global optimization techniques for solving the general quadratic integer programming problem. Comput. Optim. Appl. 10(2):149–163
Viswanathan S. (1995). Configuring cellular manufacturing systems: A quadratic integer programming formulation and a simple interchange heuristic. Int. J. Prod. Res. 33(2):361–376
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sherali, H.D., Smith, J.C. An improved linearization strategy for zero-one quadratic programming problems. Optimization Letters 1, 33–47 (2007). https://doi.org/10.1007/s11590-006-0019-0
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-006-0019-0