Tag Archives: Kochenberger

Distressed Chinese firm prediction with discretized data

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]

Preface to the 2nd Special Issue on metaheuristics in network optimization

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]

Probabilistic multistart with path relinking for solving the unconstrained binary quadratic problem

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]

Integrating tabu search and VLSN search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs

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.

Exact solutions to generalized vertex covering problems: a comparison of two models

Gary Kochenberger, Mark Lewis, Fred Glover, Haibo Wang
Optimization Letters, In Press

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.

The unconstrained binary quadratic programming problem: a survey

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.

Exact Solutions to the Capacitated Clustering Problem: A Comparison of Two Models

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.

Solving large scale Max Cut problems via tabu search

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.

Introduction to special xQx issue

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]

Graph Bisection Modeled As Cardinality Constrained Binary Quadratic Task Allocation

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.

A computational study on the quadratic knapsack problem with multiple constraints

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.

Polynomial unconstrained binary optimisation ? Part 2

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.

Polynomial unconstrained binary optimisation – Part 1

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.

A two-stage approach to solving large capacitated task allocation problems

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.

A note on optimal solutions to quadratic knapsack 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.

Theorems Supporting r-flip search for Pseudo-boolean optimization

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.

Computationally attractive non-linear models for combinatorial optimisation

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.

Simulation Optimization: Applications In Risk Management

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.

Simple and fast Surrogate Constraint Heuristics for the Maximum Independent Set Problem

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.

A new approach for modeling and solving set packing 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.