Skip to main content
SpringerLink
Log in

An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The vertex coloring problem has been the subject of extensive research for many years. Driven by application potential as well as computational challenge, a variety of methods have been proposed for this difficult class of problems. Recent successes in the use of the unconstrained quadratic programming (UQP) model as a unified framework for modeling and solving combinatorial optimization problems have motivated a new approach to the vertex coloring problem. In this paper we present a UQP approach to this problem and illustrate its attractiveness with preliminary computational experience.

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

  • Alidaee, B., G. Kochenberger, and A. Ahmadian. (1994). “0-1 Quadratic Programming Approach for the Optimal Solution of Two Scheduling Problems.” International Journal of Systems Science 25, 401–408.

    Google Scholar 

  • Alkhamis, T.M., M. Hasan, and M.A. Ahmed. (1998). “Simulated Annealing for the Unconstrained Binary Quadratic Pseudo-Boolean Function.” European Journal of Operational Research 108, 641–652.

    Article  Google Scholar 

  • Amini, M., B. Alidaee, and G. Kochenberger. (1999).“A Scatter Search Approach to Unconstrained Quadratic Binary Programs.” In Corne, Dorigo and Glover (eds.), New Methods in Optimization, McGraw-Hill, pp. 317–330.

  • Beasley, J.E. (1999). “Heuristic Algorithms for the Unconstrained Binary Quadratic Programming Problem.” Working Paper, Imperial College.

  • Billionet, A. and A. Sutter. (1994). “Minimization of a Quadratic Pseudo-Boolean Function.” European Journal of OR 78, 106–115.

    Article  Google Scholar 

  • Boros, E. and P. Hammer. (2002). “Pseudo-Boolean Optimization.” Discrete Applied Mathematics 123(1–3), 155–225.

    Google Scholar 

  • Boros, E., P. Hammer, and X. Sun. (1989). “The DDT Method for Quadratic 0-1 Minimization.” RUTCOR Research Center, RRR 39–89.

  • Boros, E. and A. Prekopa. (1989). “Probabilistic Bounds and Algorithms for the Maximum Satisfiability Problem.” Annals of OR 21, 109–126.

    Article  Google Scholar 

  • Bourjolly, J.M., P. Gill, G. Laporte and H. Mercure. (1994). “A Quadratic 0/1 Optimization Algorithm for the Maximum Clique and Stable Set Problems.” Working paper, University of Montreal.

  • Campos, V., R. Marti, and M. Laguna. (2000). “Intensification and Diversification with Elite Tabu Search Solutions for the Linear Ordering Problem.” Working Paper, University of Colorado at Boulder.

  • Chardaire, P. and A. Sutter. (1994). “A Decomposition Method for Quadratic Zero-One Programming.”Management Science 41:4, 704–712.

    Google Scholar 

  • Chiarandini, M. and T. Stutzle. (2002). “An Application of Iterated Local Search to Graph Coloring.” In D.S. Johnson, A. Mehrotra, and M. Trick (eds.), Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, pp. 112–125.

  • Coudert, O. (1997). “Exact coloring of Real Life Graphs is Easy.” In Proceedings of the 34th Design Automata Conference NY, pp. 121–126.

  • Di Blas, A. Jagota and R. Hughey. (2002). “Energy Function-Based Approaches to Graph Coloring.” IEEE Transactions on Neural Networks 13, 81–91.

    Article  Google Scholar 

  • Dorne, R. and J. Hao. (1999). “Tabu Search for Graph Coloring, t-Coloring and set t-Coloring.” In S. Voss, S. Martello, I. Osman, and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Boston: Kluwer Academic Publisher.

    Google Scholar 

  • Galinier, P. and J. Hao. (1999). “Hybrid Evolutionary Algorithms for Graph Coloring.” Journal of Combinatorial Optimization 3(4), 379–397.

    Article  Google Scholar 

  • Gallo, G., P. Hammer, and B. Simeone. (1980). “Quadratic Knapsack Problems.” Mathematical Programming 12, 132–149.

    Google Scholar 

  • Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer Academic Publishers.

  • Glover, F. (1998). “A Template for Scatter Search and Path Relinking.” School of Business, University of Colorado, Technical Report.

  • Glover, F., G. Kochenberger, B. Alidaee and M.M. Amini. (1999). “Tabu with Search Critical Event Memory: An Enhanced Application for Binary Quadratic Programs.” In S. Voss, S. Martello, I. Osman, and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Boston: Kluwer Academic Publisher.

    Google Scholar 

  • Glover, F., B. Alidaee, C. Rego, and G. Kochenberger. (2002). “One-Pass Heuristics for Large-Scale Unconstrained Binary Quadratic Programs.” EJOR 137, 272–287.

    Article  Google Scholar 

  • Glover, F., G. Kochenberger, and B. Alidaee. (1998). “Adaptive Memory Tabu Search for Binary Quadratic Programs.” Management Science 44(3), 336–345.

    Google Scholar 

  • Grotschel, M., M. Junger, and G. Reinelt. (1988). “An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design.” Operations Research 36(3), 493–513.

    Google Scholar 

  • Hammer, P., E. Boros, and X. Sun. (1998). “On Quadratic Unconstrained Binary Optimization.” INFORMS National Meeting, Seattle, October.

  • Hammer, P., P. Hansen, and B. Simone. (1981). “Upper Planes of Quadratic 0/1 Functions and Stability in Graphs.” In O. Mangasarian, R. Meyer, and S. Robinson (eds.), Nonlinear Programming 4, New York: Academic Press, pp. 395-414.

    Google Scholar 

  • Hammer, P. and S. Rudeanu. (1968). Boolean Methods in Operations Research. New York: Springer-Verlag.

    Google Scholar 

  • Hansen, P.B. (1979). “Methods of Nonlinear 0–1 Programming.” Annals Discrete Math 5, 53–70.

    Article  Google Scholar 

  • Hansen, P., B. Jaumard, and V. Mathon. (1993). “Constrained Nonlinear 0–1 Programming.” INFORMS Journal on Computing 5(2), 97–119.

    Google Scholar 

  • Helmberg, C. and F. Rendl. (1998). “Solving Quadratic (0,1)-Problems by Semidefinite Programs and Cutting Planes.” Mathematical Programming 82, 291–315.

    Google Scholar 

  • Harary, F. (1953/54). “On the Notion of Balanced of a Signed Graph.” Michigan Mathematical Journal 2, 143–146.

    Article  Google Scholar 

  • Iasemidis, L.D., D.S. Shiau, J.C. Sackellares, and P. Pardalos. (2000). “Transition to Epileptic Seizures: Optimization.” DIMACS Series in Discrete Math and Theoretical Computer Science 55, 55–73.

    Google Scholar 

  • Katayama, K., M. Tani, and H. Narihisa. (2000). “Solving Large Binary Quadratic Programming Problems by an Effective Genetic Local Search Algorithm.” In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'00).Morgan Kaufmann, pp. 643–650.

  • Kochenberger, G., F. Glover, B. Alidaee, and C. Rego. (2002). “Applications of the Unconstrained Quadratic Binary Program.” University of Colorado Working Paper.

  • Krarup, J. and A. Pruzan. (1978). “Computer Aided Layout Design.” Mathematical Programming Study 9, 75–94.

    Google Scholar 

  • Laughunn, D.J. (1970). “Quadratic Binary Programming.” Operations Research 14, 454–461.

    Article  Google Scholar 

  • Lewandowski, G. and A. Condon. (1996). “Experiments with Parallel Graph Coloring Heuristic and Applications of Graph Coloring.” DIMACS Series in Discrete Mathematics and Theoretical Computer Science Providence, RI, American Mathematical Society, Vol. 26, pp. 335–358.

  • Lodi, A., K. Allemand, and T. M. Liebling. (1997). “An Evolutionary Heuristic for Quadratic 0–1 Programming.” Technical Report OR-97-12, D.E.I.S., University of Bologna.

  • Mehrotra, A. and M. Trick. (1995). “A Column Generation Approach for Graph Coloring.” Working Paper, Carnegie Mellon University.

  • McBride, R.D. and J.S. Yormack. (1980). “An Implicit Enumeration Algorithm for Quadratic Integer Programming.” Management Science 26, 282–296.

    Google Scholar 

  • Merz, P. and B. Freisleben. (1999). “Genetic Algorithms for Binary Quadratic Programming.” In Proceedings of the 1999 International Genetic and Evolutionary Computation Conference (GECCO'99), Morgan Kaufmann, pp. 417–424.

  • Merz, P. and B. Freisleben. (2002). “Greedy and Local Search Heuristics for the Unconstrained Binary Quadratic Programming Problem.” Journal of Heuristics 8(2), 197–213.

    Article  Google Scholar 

  • Merz, P. and K. Katayama. (2004). “Memetic Algorithms for the Unconstrained Binary Quadratic Program.” Bio Systems 78(1–3), 99–118.

    Google Scholar 

  • Palubeckis, G. (1995). “A Heuristic-Branch and Bound Algorithm for the Unconstrained Quadratic Zero-One Programming Problem.” Computing 284–301.

  • Pardalos, P. and G.P. Rodgers. (1990). “Computational Aspects of a Branch and Bound Algorithm for Quadratic Zero-one Programming.” Computing 45, 131–144.

    Article  Google Scholar 

  • Pardalos, P. and G.P. Rodgers. (1992). “A Branch and Bound Algorithm for Maximum Clique problem.” Computers & OR 19, 363–375.

    Article  Google Scholar 

  • Pardalos, P. and J. Xue. (1994). “The Maximum Clique Problem.” The Journal of Global Optimization 4, 301–328.

    Article  Google Scholar 

  • Phillips, A.T. and J.B. Rosen. (1994). “A Quadratic Assignment Formulation of the Molecular Conformation Problem.” The Journal of Global Optimization 4, 229–241.

    Article  Google Scholar 

  • Rosenberg, I. (1972). “0/1 Optimization and Non-Linear Programming.” Revue Francaise d'Automatique, d'Informatique et de Recherche Operationnelle (S∖'erie Bleue) 2, 95–97.

  • Williams, A.C. (1985). “Quadratic 0-1 Programming Using the Roof Duality with Computational Results.” Rutcor Research Report 8-85, Rutgers University, New Brunswick, NJ.

  • Witsgall, C. (1975). “Mathematical Methods of site Selection for Electronic System (EMS).” NBS Internal Report.

Download references

Author information

Authors and Affiliations

  1. School of Business, University of Colorado at Denver, Campus Box 165, P.O. Box 173364, Denver, Colorado, 80217-3364

    Gary A. Kochenberger

  2. Leeds School of Business, University of Colorado at Boulder, Campus box 419, Boulder, Colorado, 80309

    Fred Glover

  3. Hearin Center for Enterprise Science, University of Mississippi, University, Mississippi, 38677

    Bahram Alidaee & Cesar Rego

Authors
  1. Gary A. Kochenberger
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fred Glover
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bahram Alidaee
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Cesar Rego
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kochenberger, G.A., Glover, F., Alidaee, B. et al. An Unconstrained Quadratic Binary Programming Approach to the Vertex Coloring Problem. Ann Oper Res 139, 229–241 (2005). https://doi.org/10.1007/s10479-005-3449-7

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-005-3449-7

Keywords

Search

Navigation