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.

Haibo Wang, Gary Kochenberger and Fred Glover
Computers & Operations Research, Vol. 39, Issue 1, Pages 3–11

The quadratic knapsack problem (QKP) has been the subject of considerable research in recent years. Despite notable advances in special purpose solution methodologies for QKP, this problem class remains very difficult to solve. With the exception of special cases, the state-of-the-art is limited to addressing problems of a few hundred variables and a single knapsack constraint.

In this paper we provide a comparison of quadratic and linear representations of QKP based on test problems with multiple knapsack constraints and up to eight hundred variables. For the linear representations, three standard linearizations are investigated. Both the quadratic and linear models are solved by standard branch-and-cut optimizers available via CPLEX. Our results show that the linear models perform well on small problem instances but for larger problems the quadratic model outperforms the linear models tested both in terms of solution quality and solution time by a wide margin. Moreover, our results demonstrate that QKP instances larger than those previously addressed in the literature as well as instances with multiple constraints can be successfully and efficiently solved by branch and cut methodologies.

Fred Glover, Jin-Kao Hao, and Gary Kochenberger
International Journal of Metaheuristics Vol. 1, Num. 4, Pages: 317-354

The class of problems known as quadratic zero-one (binary) unconstrained optimisation has provided access to a vast array of combinatorial optimisation problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. To bridge this gap, we provide methods for efficiently executing core search processes for the general polynomial unconstrained binary (PUB) optimisation problem. A variety of search algorithms for quadratic optimisation can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. Part 1 of this paper (Glover et al., 2011) provided fundamental results for carrying out the transformations and described coding and decoding procedures relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In the present part 2 paper, we provide special algorithms and data structures for taking advantage of the basic results of part 1. We also disclose how our designs can be used to enhance existing quadratic optimisation algorithms.

Fred Glover, Jin-Kao Hao, and Gary Kochenberger
International Journal of Metaheuristics, Vol. 1, Num. 3, Pages: 232-256

The class of problems known as quadratic zero-one (binary) unconstrained optimisation has provided access to a vast array of combinatorial optimisation problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. To bridge this gap, we provide methods for efficiently executing core search processes for optimisation problems in the general polynomial unconstrained binary (PUB) domain. A variety of search algorithms for quadratic optimisation can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. In this Part 1 paper, we give fundamental results for carrying out the transformations. We also describe coding and decoding procedures that are relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In a sequel to this paper, Part 2, we provide special algorithms and data structures for taking advantage of the basic results of Part 1. We also disclose how our designs can be used to enhance existing quadratic optimisation algorithms.

Mark Lewis and Gary Kochenberger
International Journal of Mathematical Modelling and Numerical Optimisation, Vol. 1, Issue 4, Pages: 259-273

This paper presents a simple, two-stage method, implemented in the commonly available Excel spreadsheet program, for quickly finding high quality solutions to larger, more difficult instances of the capacitated task allocation problem (CTAP) than have been previously reported. In Stage 1, an innovative modification of the approximation method of Griffith and Stewart is used to reformulate CTAP and find a near-integer solution. Based on the partial solution from Stage 1, the remaining tasks are allocated in a greatly reduced quadratic CTAP solved in Stage 2. Our results show that this approach yields very good solutions relatively quickly to very large problems (1,000 binary variables and 49,500 quadratic terms in the objective function). Ours is the first paper to modify the continuous approximation method of Griffith and Stewart to solve 0/1 problems and the first article to demonstrate the successful use of an Excel-based approach for solving very large CTAP problems.

Haibo Wang, Gary Kochenberger, and Yaquan Xu
International Journal of Mathematical Modelling and Numerical Optimisation Volume 1, Number 4, Pages: 344-351

In this note we report our success in applying CPLEX’s mixed integer quadratic programming (MIQP) solver to a set of standard quadratic knapsack test problems. The results we give show that this general purpose, commercial code outperformed a leading special purpose method reported in the literature by a wide margin.

Bahram Alidaee, Gary Kochenberger, and Haibo Wang
International Journal of Applied Metaheuristic Computing, Vol. 1 Issue 1, Pages 93-109

Modern metaheuristic methodologies rely on well defined neighborhood structures and efficient means for evaluating potential moves within these structures. Move mechanisms range in complexity from simple 1-flip procedures where binary variables are “flipped” one at a time, to more expensive, but more powerful, r-flip approaches where “r” variables are simultaneously flipped. These multi-exchange neighborhood search strategies have proven to be effective approaches for solving a variety of combinatorial optimization problems. In this article, we present a series of theorems based on partial derivatives that can be readily adopted to form the essential part of r-flip heuristic search methods for Pseudo-Boolean optimization. To illustrate the use of these results, we present preliminary results obtained from four simple heuristics designed to solve a set of Max 3-SAT problems.

B. Alidaee, G.A. Kochenberger, K. Lewis, M. Lewis, and H. Wang
International Journal of Mathematics in Operational Research Vol. 1, Issue 1-2, p. 9 – 19

A common approach to many combinatorial problems is to model them as 0/1 linear programs. This approach enables the use of standard linear program-based optimisation methodologies that are widely employed by the operation research community. While this methodology has worked well for many problems, it can become problematic in cases where the linear programs generated become excessively large. In such cases, linear models can lose their computational viability. In recent years, several articles have explored the computational attractiveness of non-linear alternatives to the standard linear models typically adopted to represent such problems. In many cases, comparative computational testing yields results favouring the non-linear models by a wide margin. In this article, we summarise some of these successes in an effort to encourage a broader view of model construction than the conventional wisdom, i.e. linear modelling, typically affords.

Better, Marco, Glover, Fred, Kochenberger, Gary, And Wang, Haibo
International Journal of Information Technology & Decision Making Vol. 7, Issue 4, p. 571-587

Simulation optimization is providing solutions to important practical problems previously beyond reach. This paper explores how new approaches are significantly expanding the power of simulation optimization for managing risk. Recent advances in simulation optimization technology are leading to new opportunities to solve problems more effectively. Specifically, in applications involving risk and uncertainty, simulation optimization surpasses the capabilities of other optimization methods not only in the quality of solutions but also in their interpretability and practicality. In this paper, we demonstrate the advantages of using a simulation optimization approach to tackle risky decisions, by showcasing the methodology on two popular applications from the areas of finance and business process design.