Skip to main content
SpringerLink
Log in

Several versions of the devour digest tidy-up heuristic for unconstrained binary quadratic problems

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

The unconstrained binary quadratic minimization problem is known to be NP-hard and due to its computational challenge and application capability, it becomes more and more considered and involved by the recent research studies, including both exact and heuristic solution approaches. Our work is in line with what was suggested by Glover et al. (in Eur. J. Oper. Res. 137, 272–287, 2002) who proposed one pass heuristics as alternatives to the well-known Devour Digest Tidy-up procedure (DDT) of Boros et al. (in RRR 39-89, 1989). The “devour” step sets a term of the current representation to 0 or 1, and the “tidy-up” step substitutes the logical consequences derived from the “digest” step into the current quadratic function. We propose several versions of the DDT constructive heuristic based on the alternative representation of the quadratic function. We also present an efficient implementation of local search using one-flip and two-flip moves that simultaneously change the values of one or two binary variables. Computational experiments performed on instances up to 7000 variables show the efficiency of our implementation in terms of quality improvement and CPU use enhancement.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Adams, W.P., Forrester, R.J., Glover, F.W.: Comparisons and enhancement strategies for linearizing mixed 0–1 quadratic programs. Discrete Optim. 1(2), 99–120 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  • Alidaee, B., Kochenberger, G., Ahmadian, A.: 0-1 quadratic programming approach for the optimal solution of two scheduling problems. Int. J. Syst. Sci. 25, 401–408 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  • Alidaee, B., Kochenberger, G., Wang, H.: Theorems supporting r-flip search for pseudo-boolean optimization. Int. J. Appl. Metaheuristic Comput. 1(1), 93–109 (2010)

    Article  MathSciNet  Google Scholar 

  • Alkhamis, T.M., Hasan, M., Ahmed, M.A.: Simulated annealing for the unconstrained binary quadratic pseudo-boolean function. Eur. J. Oper. Res. 108, 641–652 (1998)

    Article  MATH  Google Scholar 

  • Amini, M., Alidaee, B., Kochenberger, G.: A scatter search approach to unconstrained quadratic binary programs. In: Corne, Dorigo, Glover (eds.) New Methods in Optimization, pp. 317–330. McGraw-Hill, New York (1999)

    Google Scholar 

  • Badics, T.: Approximation of Some Nonlinear Binary Optimization Problems. PhD thesis, RUTCOR, Rutgers University (1996)

  • Balas, E.: Extension de l’algorithme additif à la programmation en nombres entiers et à la programmation non linéaire. C. R. Acad. Sci. Paris (1964)

  • Beasley, J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41, 1069–1072 (1990)

    Google Scholar 

  • Beasley, J.E.: Heuristic algorithms for the unconstrained binary quadratic programming problem. Working Paper, Imperial College (1998)

  • Borgulya, I.: An evolutionary algorithm for the binary quadratic problems. Adv. Soft Comput. 2, 3–16 (2005)

    Article  Google Scholar 

  • Boros, E., Hammer, P.L.: A max-flow approach to improved roof-duality in quadratic 0–1 minimization. Research Report 15, Rutgers Center for Operations Research, Rutgers University, New Brunswick, NJ (1989)

  • Boros, E., Hammer, P.L.: Pseudo-boolean optimization. Discrete Appl. Math. 123, 155–225 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • Boros, E., Hammer, P., Sun, X.: The DDT method for quadratic 0-1 minimization. RUTCOR Research Center, RRR 39-89 (1989)

  • Boros, E., Hammer, P.L., Tavares, G.: Local search heuristics for quadratic unconstrained binary optimization (QUBO). J. Heuristics 13, 99–132 (2007)

    Article  Google Scholar 

  • Boros, E., Hammer, P.L., Sun, R., Tavares, G.: A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO). Discrete Optim. 5, 501–529 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Chartaire, P., Sutter, A.: A decomposition method for quadratic zero-one programming. Manag. Sci. 41(4), 704–712 (1994)

    Article  Google Scholar 

  • Feo, T.A., Resende, M.G.C., Smith, S.H.: A greedy randomized adaptive search procedure for maximum independent set. Oper. Res. 42, 860–878 (1994)

    Article  MATH  Google Scholar 

  • Fortet, R.: L’algèbre de Boole et ses Applications en Recherche Operationnelle. Cah. Cent. Etudes Rech. Oper. 1(4), 5–36 (1959)

    MATH  Google Scholar 

  • Fortet, R.: Applications de l’algèbre de Boole en recherche opérationelle. Rev. Fr. Info. Rech. Opér. 4, 17–26 (1960)

    Google Scholar 

  • Gallo, G., Simeone, B.: On the supermodular knapsack problem. Math. Program. 45, 295–309 (1998)

    Article  MathSciNet  Google Scholar 

  • Glover, F.: Improved linear integer programming formulations of nonlinear integer problems. Manag. Sci. 22, 455–460 (1975)

    Article  MathSciNet  Google Scholar 

  • Glover, F.: An improved MIP formulation for products of discrete and continuous variables. J. Inf. Optim. Sci. 5(1), 469–471 (1984)

    Google Scholar 

  • Glover, F., Hanafi, S.: Tabu search and finite convergence. Discrete Appl. Math. 119, 3–36 (2002). Special Issue on “Foundations of Heuristics in Combinatorial Optimization”

    Article  MathSciNet  MATH  Google Scholar 

  • Glover, F., Hao, J.K.: Fast 2-fip move evaluations for binary unconstrained quadratic optimization problems. Working paper, LERIA, Université d’Angers (2009)

  • Glover, F., Hao, J.K.: Efficient evaluations for solving large 0-1 unconstrained quadratic optimization problems. Int. J. Metaheuristics 1(1), 3–10 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  • Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Dordrecht (1997)

    Book  MATH  Google Scholar 

  • Glover, F., Woolsey, E.: Converting the 0–1 polynomial programming problem to a 0–1 linear program. Oper. Res. 22, 180–182 (1974)

    Article  MATH  Google Scholar 

  • Glover, F., Kochenberger, G., Alidaee, B.: Adaptive memory tabu search for binary quadratic programs. Manag. Sci. 44(3), 336–345 (1998)

    Article  MATH  Google Scholar 

  • Glover, F., Kochenberger, G., Alidaee, B., Amini, M.: Unconstrained quadratic binary program approach to quadratic knapsack problems. Working paper, Hearin Center for Enterprise Science, University of Mississippi (1999a)

  • Glover, F., Kochenberger, G., Alidaee, B., Amini, M.: Tabu search with critical event memory: an enhanced application for binary quadratic programs. In: Voss, S.M.S., Osman, I., Roucairol, C. (eds.) Meta-Heuristics, Advances and Trends in Local Search Paradigms for Optimization, pp. 93–109. Kluwer, Dordrecht (1999b)

    Chapter  Google Scholar 

  • Glover, F., Amini, M., Kochenberger, G., Alidaee, B.: A new evolutionary metaheuristic for the unconstrained binary quadratic programming: a case study of the scatter search. School of Business, University of Colorado, Boulder (September 1999c)

  • Glover, F., Alidaee, B., Rego, C., Kochenberger, G.: One-pass heuristics for large-scale unconstrained binary quadratic problems. Eur. J. Oper. Res. 137, 272–287 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • Glover, F., Lü, Z., Hao, J.-K.: Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR (2010). doi:10.1007/s10288-009-0115-y

    Google Scholar 

  • Goldberg, D.E.: Genetic Algorithms in Search Optimization and Machine Learning. Addison Wesley, Reading (1989), p. 41

    MATH  Google Scholar 

  • Goldman, A.J.: Linearization in 0–1 variables: a clarification. Oper. Res. 31(5), 946–947 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  • Gueye, S., Michelon, P.: “Miniaturized” linearizations for quadratic 0–1 problems. Ann. Oper. Res. 140 (2005)

  • Hammer, P.L., Rudeanu, S.: Boolean Methods in Operations Research and Related Areas. Springer, Berlin (1968)

    Book  MATH  Google Scholar 

  • Hammer, P.L., Hansen, P., Simeone, B.: Roof duality, complementation and persistency in quadratic 0–1 optimization. Math. Program. 28, 121–155 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  • Hammer, P., Boros, E., Sun, X.: On quadratic unconstrained binary optimization. In: INFORMS National Meeting, Seattle, October (1998)

    Google Scholar 

  • Hansen, P., Meyer, C.: Improved compact linearizations for the unconstrained quadratic 0–1 minimization problem. Discrete Appl. Math. 157, 1267–1290 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  • Hansen, P., Jaumard, B., Mathon, V.: Constrained nonlinear 0-1 programming. INFORMS J. Comput. 5(2), 97–119 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  • Harary, F.: On the notion of balanced of a signed graph. Mich. Math. J. 2, 143–146 (1953/54)

    Article  Google Scholar 

  • Katayama, K., Narihisa, H.: Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem. Eur. J. Oper. Res. 134, 103–119 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  • Katayama, K., Tani, M., Narihisa, H.: Solving large binary quadratic programming problems by an effective genetic local search algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’00), pp. 643–650. Morgan Kaufmann, San Mateo (2000)

    Google Scholar 

  • Kirkpatrick, S., Gerlatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  • Kochenberger, G., Alidaee, B., Amini, M.: Applications of the unconstrained quadratic binary program. University of Colorado Working Paper (1998)

  • Krarup, J., Pruzan, A.: Computer aided layout design. Math. Program. Stud. 9, 75–94 (1978)

    Article  MathSciNet  Google Scholar 

  • Laughunn, D.J.: Quadratic binary programming. Oper. Res. 14, 454–461 (1970)

    Article  Google Scholar 

  • Lodi, A., Allemand, K., Liebling, T.M.: An evolutionary heuristic for quadratic 0-1 programming. Eur. J. Oper. Res. 119(3), 662–670 (1999)

    Article  MATH  Google Scholar 

  • Lourenço, H.R., Martin, O., Stützle, T.: Iterated Local Search. Handbook of Metaheuristics. Springer, Berlin (2003)

    Google Scholar 

  • Lü, Z., Glover, F., Hao, J.K.: Neighborhood combination for unconstrained binary quadratic programming. In: Proceedings of the 8th Metaheuristic International Conference (MIC 2009), Hamburg, Germany, 13–16 July (2009)

    Google Scholar 

  • Lü, Z., Glover, F., Hao, J.-K.: A hybrid metaheuristic approach to solving the UBQP problem. Eur. J. Oper. Res. (2010). doi:10.1016/j.ejor.2010.06.039

    Google Scholar 

  • McBride, R.D., Yormack, J.S.: An implicit enumeration algorithm for quadratic integer programming. Manag. Sci. 26, 282–296 (1980)

    Article  MATH  Google Scholar 

  • Merz, P., Freisleben, B.: Genetic algorithms for binary quadratic programming. In: Proceedings of the 1999 International Genetic and Evolutionary Computation Conference (GECCO’99), pp. 417–424. Morgan Kaufmann, San Mateo (1999)

    Google Scholar 

  • Merz, P., Freisleben, B.: Greedy and local search heuristics for unconstrained binary quadratic programming. J. Heuristics, 197–213 (2002)

  • Merz, P., Katayama, K.: Memetic algorithms for the unconstrained binary quadratic programming problem. Biosystems 78, 99–118 (2004)

    Article  Google Scholar 

  • Mladenovic, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24, 1097–1100 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  • Palubeckis, G.: Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann. Oper. Res. 131, 259–282 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  • Palubeckis, G.: Iterated tabu search for the unconstrained binary quadratic optimization problem. Informatica 17(2), 279–296 (2006)

    MathSciNet  MATH  Google Scholar 

  • Pardalos, P., Rodgers, G.P.: Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45, 131–144 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  • Pardalos, P., Rodgers, G.P.: A branch and bound algorithm for maximum clique problem. Comput. Oper. Res. 19, 363–375 (1992)

    Article  MATH  Google Scholar 

  • Pardalos, P., Xue, J.: The maximum clique problem. J. Glob. Optim. 4, 301–328 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  • Phillips, A.T., Rosen, J.B.: A quadratic assignment formulation of the molecular conformation problem. J. Glob. Optim. 4, 229–241 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  • Plateau, M.-C.: Reformulations quadratiques convexes pour la programmation quadratique en variables 0-1. Ph.D. Thesis, Conservatoire National des Arts et Métiers / CEDRIC (November 2006) (in French, available online at http://www.cedric.cnam.fr/PUBLIS/RC1115.pdf)

  • Watters, L.J.: Reduction of integer polynomial programming problems to zero-one linear programming problems. Oper. Res. 15, 1171–1174 (1967)

    Article  Google Scholar 

  • Williams, A.C.: Quadratic 0-1 programming using the roof duality with computational results. Rutcor Research Report 8-85, Rutgers University, New Brunswick, NJ (1985)

  • Witsgall, C.: Mathematical methods of site selection for electronic system (EMS). NBS Internal Report (1975)

  • Zangwill, W.I.: Media selection by decision programming. J. Advert. Res. 5(3), 30–36 (1965)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LAMIH, Université de Valenciennes, 59313, Valenciennes Cedex 9, France

    Saïd Hanafi

  2. Electrical & Computer Engineering Program, Texas A&M University at Qatar, PO Box 23874, Doha, Qatar

    Ahmed-Riadh Rebai

  3. LGI2P, Ecole des Mines d’Alès, Parc scientifique Georges Besse, 30035, Nímes, France

    Michel Vasquez

Authors
  1. Saïd Hanafi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ahmed-Riadh Rebai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michel Vasquez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Saïd Hanafi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hanafi, S., Rebai, AR. & Vasquez, M. Several versions of the devour digest tidy-up heuristic for unconstrained binary quadratic problems. J Heuristics 19, 645–677 (2013). https://doi.org/10.1007/s10732-011-9169-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-011-9169-z

Keywords

Search

Navigation