Bahram Alidaee, Gary Kochenberger and Haibo Wang Journal of Heuristics Vol. 14, Issue 6, p. 571-585
In a recent paper Glover (J. Heuristics 9:175–227, 2003) discussed a variety of surrogate constraint-based heuristics for solving optimization problems in graphs. The key ideas put forth in the paper were illustrated by giving specializations designed for certain covering and coloring problems. In particular, a family of methods designed for the maximum cardinality independent set problem was presented. In this paper we report on the efficiency and effectiveness of these methods based on considerable computational testing carried out on test problems from the literature as well as some new test problems.
Alidaee, Bahram, Kochenberger, Gary, Lewis, Karen, Lewis, Mark, and Wang, Haibo European Journal of Operational Research Vol. 186, Issue 2, p. 504-512
In recent years the unconstrained quadratic binary program has emerged as a unified modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this unified approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing special purpose methods. In this paper we report on the application of this unified framework to set packing problems with a variety of coefficient distributions. Computational experience is reported illustrating the attractiveness of the approach. In particular, our results highlight both the effectiveness and robustness of our approach across a wide array of test problems.
Alidaee, B., Kochenberger, G., Lewis, K., Lewis, M. and Wang, H. European Journal of Operational Research Vol. 186, Issue 2, p. 504-512
In recent years the unconstrained quadratic binary program has emerged as a unified modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this unified approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing special purpose methods. In this paper we report on the application of this unified framework to set packing problems with a variety of coefficient distributions. Computational experience is reported illustrating the attractiveness of the approach. In particular, our results highlight both the effectiveness and robustness of our approach across a wide array of test problems.
Lewis, Mark, Kochenberger, Gary, and Alidaee, Bahram Computers & Operations Research Vol. 35, Issue 3, p. 807-813
The set-partitioning problem (SPP) is widely known for both its application potential and its computational challenge. This NP-hard problem is known to pose considerable difficulty for classical solution methods such as those based on LP technologies. In recent years, the unconstrained binary quadratic program has proven to perform well as a unified modeling and solution framework for a variety of IP problems. In this paper we illustrate how this unified framework can be applied to SPP. Computational experience is presented, illustrating the attractiveness of the approach.
Alidaee, Bahram, Glover, Fred, Kochenberger, Gary and Wang, Haibo European Journal of Operational Research Vol. 181, Issue 2, p. 592-597
The unconstrained quadratic binary program (UQP) is proving to be a successful modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing more traditional methods. In this paper we report on the application of UQP to the maximum edge-weighted clique problem. Computational experience is reported illustrating the attractiveness of the approach.
GLOVER, FRED W. and KOCHENBERGER, GARY International Journal of Information Technology & Decision Making Vol. 5 Issue 4, p. 605-609
In recent years modern methods of optimization have contributed greatly to the advances in data mining and related areas. These contributions continue today and promise to further advance the state of the art both in terms of modeling innovations and new solution methodologies. In this paper, we present a new modeling and solution methodology for unsupervised clustering. Preliminary computational experience is given to illustrate the approach. This methodology is part of our current research and offers considerable opportunity for additional investigation to be conducted by other researchers.
Kochenberger, Gary A., Glover, Fred, Alidaee, Bahram and Rego, Cesar Annals of Operations Research Vol. 139, Issue 1, pp. 229 – 241.
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.
Lewis, Mark, Alidaee, Bahram and Kochenberger, Gary Operations Research Letters Vol. 33, Issue 2, p. 176-182
This paper illustrates how large instances of the unconstrained task allocation problem can be effectively modeled and efficiently solved as unconstrained quadratic binary programs. Computational experience and a comparison to the state-of-the-art commercial code (CPLEX) illustrate the attractiveness of our approach.
Alidaee, Bahram, Glover, Fred, Kochenberger, Gary A. and Rego, Ceasar Journal Of Applied Mathematics And Decision Sciences Vol. 9, Issue 2, p. 135-145
The number partitioning problem has proven to be a challenging problem for both exact and heuristic solution methods. In this paper we present a new modeling and solution approach that consists of re-casting the problem as an unconstrained quadratic binary program that can be solved by effcient metaheuristic methods. Our approach readily accommodates both the common two-subset partition case as well as the more general case of multiple subsets. Preliminary computational experience is presented illustrating the attractiveness of the method.