A column generation approach for the unconstrained binary quadratic programming problem

This paper proposes a column generation approach based on the Lagrangean relaxation with clusters to solve the unconstrained binary quadratic programming problem that consists of maximizing a quadratic objective function by the choice of suitable values for binary decision variables. The proposed method treats a mixed binary linear model for the quadratic problem with constraints represented by a graph. This graph is partitioned in clusters of vertices forming sub-problems whose solutions use the dual variables obtained by a coordinator problem. The column generation process presents alternative ways to find upper and lower bounds for the quadratic problem. Computational experiments were performed using hard instances and the proposed method was compared against other methods presenting improved results for most of these instances.     

Path relinking for unconstrained binary quadratic programming

This paper presents two path relinking algorithms to solve the unconstrained binary quadratic programming (UBQP) problem. One is based on a greedy strategy to generate the relinking path from the initial solution to the guiding solution and the other operates in a random way. We show extensive computational results on five sets of benchmarks, including 31 large random UBQP instances and 103 structured instances derived from the MaxCut problem. Comparisons with several state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that both algorithms are able to improve the previous best known results for almost 40 percent of the 103 MaxCut instances.     

Several versions of the devour digest tidy-up heuristic for unconstrained binary quadratic problems

The unconstrained binary quadratic minimization problem is known to be NP-hard and due to its computational challenge and application capability, it becomes more and more considered and involved by the recent research studies, including both exact and heuristic solution approaches. Our work is in line with what was suggested by Glover et al. (in Eur. J. Oper. Res. 137, 272–287, 2002) who proposed one pass heuristics as alternatives to the well-known Devour Digest Tidy-up procedure (DDT) of Boros et al. (in RRR 39-89, 1989). The “devour” step sets a term of the current representation to 0 or 1, and the “tidy-up” step substitutes the logical consequences derived from the “digest” step into the current quadratic function. We propose several versions of the DDT constructive heuristic based on the alternative representation of the quadratic function. We also present an efficient implementation of local search using one-flip and two-flip moves that simultaneously change the values of one or two binary variables. Computational experiments performed on instances up to 7000 variables show the efficiency of our implementation in terms of quality improvement and CPU use enhancement.     

New bounds on the unconstrained quadratic integer programming problem

We consider the maximization for a given symmetric . It was shown recently, using properties of zonotopes and hyperplane arrangements, that in the special case that A has a small rank, so that A = VV ^T where with m < n, then there exists a polynomial time algorithm (polynomial in n for a given m) to solve the problem . In this paper, we use this result, as well as a spectral decomposition of A to obtain a sequence of non-increasing upper bounds on γ with no constraints on the rank of A. We also give easily computable necessary and sufficient conditions for the absence of a gap between the solution and its upper bound. Finally, we incorporate the semidefinite relaxation upper bound into our scheme and give an illustrative example.     

Solving the maximum edge weight clique problem via unconstrained quadratic programming

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.     

One-pass heuristics for large-scale unconstrained binary quadratic problems

Many significant advances have been made in recent years for solving unconstrained binary quadratic programs (UQP). As a result, the size of problem instances that can be efficiently solved has grown from a hundred or so variables a few years ago to 2000 or 3000 variables today. These advances have motivated new applications of the model which, in turn, have created the need to solve even larger problems. In response to this need, we introduce several new “one-pass” heuristics for solving very large versions of this problem. Our computational experience on problems of up to 9000 variables indicates that these methods are both efficient and effective for very large problems. The significance of problems of this size is that they not only open the door to solving a much wider array of real world problems, but also that the standard linear mixed integer formulations of the nonlinear models involve over 40,000,000 variables and three times that many constraints. Our approaches can be used as stand-alone solution methods, or they can serve as procedures for quickly generating high quality starting points for other, more sophisticated methods.     

Diversification-driven tabu search for unconstrained binary quadratic problems

This paper describes a Diversification-Driven Tabu Search (D²TS) algorithm for solving unconstrained binary quadratic problems. D²TS is distinguished by the introduction of a perturbation-based diversification strategy guided by long-term memory. The performance of the proposed algorithm is assessed on the largest instances from the ORLIB library (up to 2500 variables) as well as still larger instances from the literature (up to 7000 variables). The computational results show that D²TS is highly competitive in terms of both solution quality and computational efficiency relative to some of the best performing heuristics in the literature.     

Unit integer quadratic binary programming

This paper presents an efficient method of computing $\text{?′}{}_{\mathrm{<mtext>max</mtext>}}\text{=}\text{max}\text{Y}\text{Y}{}^{\mathrm{<mtext>T</mtext>}}\text{AY}$, where Y is an N-dimensional vector of ±1 entries and A is a real symmetric matrix. The ratio of number of computations required by this method to that by the direct method is approximately ($\text{3}\text{2N}$), where the direct method corresponds to computing Y^TAY for all possible Y and then finding the maximum from these. This problem has important applications in operations research, matrix theory, signal processing, communication theory, control theory, and others. Some of these are discussed in this paper.     

An improved lower bound and approximation algorithm for binary constrained quadratic programming problem

This paper presents an improved lower bound and an approximation algorithm based on spectral decomposition for the binary constrained quadratic programming problem. To decompose spectrally the quadratic matrix in the objective function, we construct a low rank problem that provides a lower bound. Then an approximation algorithm for the binary quadratic programming problem together with a worst case performance analysis for the algorithm is provided.     

An unconstrained convex programming approach to solving convex quadratic programming problems

In this paper, we derive an unconstrained convex programming approach to solving convex quadratic programming problems in standard form. Related duality theory is established by using two simple inequalities. An ?-optimal solution is obtained by solving an unconstrained dual convex program. A dual-to-primal conversion formula is also provided. Some preliminary computational results of using a curved search method is included     

A heuristic procedure for solving the quadratic assignment problem

An heuristic approach to the solution of the quadratic assignment problem is presented. A simple procedure is used to get a good feasible starting point, then the problem is solved as a nonlinear program (ignoring the integrality conditions) using MINOS, and lastly the near integer solution is converted into an integer feasible solution using an heuristic procedure. The results compare favourably with other procedures in the literature. A superior solution to the 19 × 19 hospital layout problem is found.     

A dynamic programming heuristic for the P-median problem

A new heuristic algorithm is proposed for the P-median problem. The heuristic restricts the size of the state space of a dynamic programming algorithm. The approach may be viewed as an extension of the myopic or greedy adding algorithm for the P-median model. The approach allows planners to identify a large number of solutions all of which perform well with respect to the P-median objective of minimizing the demand weighted average distance between customer locations and the nearest of the P selected facilities. In addition, the results indicate regions in which it is desirable to locate facilities. Computational results from three test problems are discussed.     

Parametric linear programming techniques for the indefnite quadratic programming problem

In this paper, we discuss a multiparametric technique for findinga global minimum for an indefinite quadratic programming problembased on the spectral decomposition of the matrix of the quadraticform. Special attention is given to the case where this matrixhas only rank 1, where the multiparametric linear program turnsout to be a single-parameter linear program. An extension ofthe traditional linear parametric procedure is introduced whichin general solves this problem efficiently. However, an exampleis presented showing that this technique may take an exponentialnumber of steps.     

Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

Quadratic Unconstrained Binary Optimization (QUBO) problems concern the minimization of quadratic polynomials in n{0,1}-valued variables. These problems are NP-complete, but prior work has identified a sequence of polynomial-time computable lower bounds on the minimum value, denoted by C₂,C₃,C₄,…. It is known that C₂ can be computed by solving a maximum flow problem, whereas the only previously known algorithms for computing require solving a linear program. In this paper we prove that C₃ can be computed by solving a maximum multicommodity flow problem in a graph constructed from the quadratic function. In addition to providing a lower bound on the minimum value of the quadratic function on {0,1}ⁿ, this multicommodity flow problem also provides some information about the coordinates of the point where this minimum is achieved. By looking at the edges that are never saturated in any maximum multicommodity flow, we can identify relational persistencies: pairs of variables that must have the same or different values in any minimizing assignment. We furthermore show that all of these persistencies can be detected by solving single-commodity flow problems in the same network.     

A sequential quadratically constrained quadratic programming method for unconstrained minimax problems

In this paper, a sequential quadratically constrained quadratic programming (SQCQP) method for unconstrained minimax problems is presented. At each iteration the SQCQP method solves a subproblem that involves convex quadratic inequality constraints and a convex quadratic objective function. The global convergence of the method is obtained under much weaker conditions without any constraint qualification. Under reasonable assumptions, we prove the strong convergence, superlinearly and quadratic convergence rate.     

On active-set methods for the quadratic programming problem

The active-set Newton method developed earlier by the authors for mixed complementarity problems is applied to solving the quadratic programming problem with a positive definite matrix of the objective function. A theoretical justification is given to the fact that the method is guaranteed to find the exact solution in a finite number of steps. Numerical results indicate that this approach is competitive with other available methods for quadratic programming problems.     

A splitting method for quadratic programming problem

1. IntroductionThe quadratic programming (QP) problem is the most simple one in nonlinear pro-gramming and plays a very important role in optimization theory and applications.It is well known that matriX splitting teChniques are widely used for solving large-scalelinear system of equations very successfully. These algorithms generate an infinite sequence,in contrast to the direct algorithms which terminate in a finite number of steps. However,iterative algorithms are considerable simpler tha…