Fred Glover, Gary Kochenberger, Weihong Xie, Jianbin Luo
Journal of Heuristics,Vol. 25, Issue 4-5, Pages: 643-671.
We introduce new diversification methods for zero-one optimization that significantly extend strategies previously introduced in the setting of metaheuristic search. Our methods incorporate easily implemented strategies for partitioning assignments of values to variables, accompanied by processes called augmentation and shifting which create greater flexibility and generality. We then show how the resulting collection of diversified solutions can be further diversified by means of permutation mappings, which equally can be used to generate diversified collections of permutations for applications such as scheduling and routing. These methods can be applied to non-binary vectors using binarization procedures and by diversification-based learning procedures that provide connections to applications in clustering and machine learning. Detailed pseudocode and numerical illustrations are provided to show the

Fred Glover, Mark Lewis, Gary Kochenberger
European Journal of Operational Research,Vol. 265, Issue 3, Pages: 829-842.
The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and

Jun Huang, Jun Huang, Haibo Wang, Haibo Wang, Gary Kochenberger, Gary Kochenberger
Management Decision,Vol. 55, Issue 5, Pages: 786-807.

Purpose The authors develop a framework to build an early warning mechanism in detecting financial deterioration of Chinese companies. Many studies in the financial distress and bankruptcy prediction literature rarely do they examine the impact of pre-processing financial indicators on the prediction performance. The purpose of this paper is to address this shortcoming. Design/methodology/approach The proposed framework is evaluated by using both original and discretized data, and a least absolute shrinkage and selection …
[Full Text]

Gary Kochenberger, Fred Glover
Networks,Vol. 68, Issue 1, Pages: 3-3.

If you can’t find a tool you’re looking for, please click the link at the top of the page to” Go to old article view”. Alternatively, view our Knowledge Base articles for additional help. Your feedback is important to us, so please let us know if you have comments or ideas for improvement.
[Full Text]

Mark Lewis, Gary Kochenberger
International Journal of Operational Research,Vol. 26, Issue 1, Pages: 13-33.

The unconstrained binary quadratic problem (UBQP) has been shown to be an excellent framework from which to solve many types of problems, both constrained and unconstrained. In this paper we investigate a solution technique for UBQP that is based on perturbing a solution by drawing from the distribution of variables’ estimated effect as determined via an unbiased design of experiments (DOE) sampling of the solution space. Solution perturbation is followed by a steepest ascent local search with path relinking. A …
[Full Text]

Gary Kochenberger, Mark Lewis, Fred Glover, Haibo Wang
Optimization Letters, Volume 9, Issue 7, pp 1331–1339

The generalized vertex cover problem (GVCP) was recently introduced in the literature and modeled as a binary linear program. GVCP extends classic vertex cover problems to include both node and edge weights in the objective function. Due to reported difficulties in finding good solutions for even modest sized problems via the use of exact methods (CPLEX), heuristic solutions obtained from a customized genetic algorithm (GA) were reported by Milanovic (Comput Inf 29:1251–1265, 2010). In this paper we consider an alternative model representation for GVCP that translates the constrained linear (binary) form to an unconstrained quadratic binary program and compare the linear and quadratic models via computations carried out by CPLEX’s branch-and-cut algorithms. For problems comparable to those previously studied in the literature, our results indicate that the quadratic model efficiently yields optimal solutions for many large GVCP problems. Moreover, our quadratic model dramatically outperforms the corresponding linear model in terms of time to reach and verify optimality and in terms of the optimality gap for problems where optimality is unattained.

Fred Glover, Tao Ye, Abraham P. Punnen, Gary Kochenberger
European Journal of Operational Research, Volume 241, Issue 3, 16 March 2015, Pages 697–707

The bipartite boolean quadratic programming problem (BBQP) is a generalization of the well studied boolean quadratic programming problem. The model has a variety of real life applications; however, empirical studies of the model are not available in the literature, except in a few isolated instances. In this paper, we develop efficient heuristic algorithms based on tabu search, very large scale neighborhood (VLSN) search, and a hybrid algorithm that integrates the two. The computational study establishes that effective integration of simple tabu search with VLSN search results in superior outcomes, and suggests the value of such an integration in other settings. Complexity analysis and implementation details are provided along with conclusions drawn from experimental analysis. In addition, we obtain solutions better than the best previously known for almost all medium and large size benchmark instances.

Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, Yang Wang
Journal of Combinatorial Optimization, July 2014, Volume 28, Issue 1, pp 58-81

In recent years the unconstrained binary quadratic program (UBQP) has grown in importance in the field of combinatorial optimization due to its application potential and its computational challenge. Research on UBQP has generated a wide range of solution techniques for this basic model that encompasses a rich collection of problem types. In this paper we survey the literature on this important model, providing an overview of the applications and solution methods.

Mark Lewis, Haibo Wang, Gary Kochenberger
Annals of Data Science, March 2014, Volume 1, Issue 1, pp 15-23

In this paper, we investigate a natural nonlinear alternative to a standard linear model for CCP and compare the two models on a set of test problems. Our results show that moderate sized instances of CCP can in fact be solved optimally with modern exact methods in modest amounts of time and that the quadratic model generally outperformed its equivalent linear alternative in terms of quickly finding optimal or near optimal solutions.

Gary A. Kochenberger, Jin-Kao Hao, Zhipeng Lü, Haibo Wang and Fred Glover
Journal of Heuristics, Volume 19, Issue 4, August 2013, pp 565-571

In recent years many algorithms have been proposed in the literature for solving the Max-Cut problem. In this paper we report on the application of a new Tabu Search algorithm to large scale Max-cut test problems. Our method provides best known solutions for many well-known test problems of size up to 10,000 variables, although it is designed for the general unconstrained quadratic binary program (UBQP), and is not specialized in any way for the Max-Cut problem.

Gary Kochenberger, Fred Glover
Journal of Heuristics,Vol. 19, Issue 4, Pages: 525-528.

The Unconstrained Binary Quadratic Programming (UBQP) problem is notable for encompassing a remarkable range of applications in combinatorial optimization. As observed in Kochenberger et al.(2013), classes of problems that can be formally expressed using UBQP formulations include: Quadratic Assignment Problems, Capital Budgeting Problems, Multiple Knapsack Problems, Task Allocation Problems (distributed computer systems), Maximum Diversity Problems, P-Median Problems, Asymmetric Assignment …
[Full Text]

Mark Lewis and Gary Kochenberger
International Journal of Information Technology & Decision Making. (2013) Vol. 12, Issue 2

In this paper, the cardinality constrained quadratic model for binary quadratic programming is used to model and solve the graph bisection problem as well as its generalization in the form of the task allocation problem with two processors (2-TAP). Balanced graph bisection is an NP-complete problem which partitions a set of nodes in the graph G = (N, E) into two sets with equal cardinality such that a minimal sum of edge weights exists between the nodes in the two separate sets. 2-TAP is graph bisection with the addition of node preference costs in the objective function. We transform the general linear k-TAP model to the cardinality constrained quadratic binary model so that it may be efficiently solved using tabu search with strategic oscillation. On a set of benchmark graph bisections, we improve the best known solution for several problems. Comparison results with the state-of-the-art graph partitioning program METIS, as well as Cplex and Gurobi are presented on a set of randomly generated graphs. This approach is shown to also work well with 2-TAP, comparing favorably to Cplex and Gurobi, providing better solutions in a much shorter time.