A new relaxation framework for quadratic assignment problems based on matrix splitting

Quadratic assignment problems (QAPs) are known to be among the hardest discrete optimization problems. Recent study shows that even obtaining a strong lower bound for QAPs is a computational challenge. In this paper, we first discuss how to construct new simple convex relaxations of QAPs based on various matrix splitting schemes. Then we introduce the so-called symmetric mappings that can be used to derive strong cuts for the proposed relaxation model. We show that the bounds based on the new models are comparable to some strong bounds in the literature. Promising experimental results based on the new relaxations are reported.     

Semi-definite programming techniques for structured quadratic inverse eigenvalue problems

In the past decade or so, semi-definite programming (SDP) has emerged as a powerful tool capable of handling a remarkably wide range of problems. This article describes an innovative application of SDP techniques to quadratic inverse eigenvalue problems (QIEPs). The notion of QIEPs is of fundamental importance because its ultimate goal of constructing or updating a vibration system from some observed or desirable dynamical behaviors while respecting some inherent feasibility constraints well suits many engineering applications. Thus far, however, QIEPs have remained challenging both theoretically and computationally due to the great variations of structural constraints that must be addressed. Of notable interest and significance are the uniformity and the simplicity in the SDP formulation that solves effectively many otherwise very difficult QIEPs.     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in Zhao et?al. (J Comb Optim 2:71–109, 1998). Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown in Klerk and Sotirov (Math Program A, 122(2), 225–246, 2010). Continuing in the same vein, we show how one may obtain stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate our approach, we compute improved lower bounds for several instances from the QAP library QAPLIB.     

Lower bounds based on linear programming for the quadratic assignment problem

In this paper we prove that the Classical Gilmore-Lawler lower bound for the quadratic assignment problem is equivalent to a solution of a certain linear programming problem. By adding additional constraints to this linear programming problem we derive a lower bound which is at least as good as the Gilmore-Lawler lower bound.Some of this research was done while the author was on sabbatical leave at the Department of Management, The Hong Kong University of Science and Technology, Kowloon, Hong Kong.     

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…     

Nonnegative definite matrices and their applications to matrix quadratic programming problems

In this paper, the concept that a matrix is nonnegative definite over a subspace and the tool of generalized inverse are used to express a general form of matrix quadratic programming. Several fundamental conclusions are obtained. An application to the common penalty method for handling constrained minimization problem is given.     

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the ratio is dependent on the data of the problem with α being a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least α δd if every weight is strictly positive,where δd ＞ 0 is a constant depending on the problem dimension and data.     

Nonnegative definite matrices and their applications to matrix quadratic programming problems

In this paper, the concept that a matrix is nonnegative definite over a subspace and the tool of generalized inverse are used to express a general form of matrix quadratic programming. Several fundamental conclusions are obtained. An application to the common penalty method for handling constrained minimization problem is given.     

A contribution to quadratic assignment problems

We discuss special eases of the quadratic assignment problem (QAP) being polynomially solvable. In particular we give an algebraic condition for the cost; Matrices of a QAP which guarantees that it is equivalent with a linear assignment problem. Based on these results we develop an approximation algorithm for QAPs with non-negative symmetric cost matrices.     

On random quadratic bottleneck assignment problems

The relative error between best and worst solution of quadratic bottleneck assignment problems with cost coefficientsd _ijpq =a _ip b _jq is considered, wherea _ip is either arbitrarily given or corresponds to a distance in the plane. It is shown that the relative error is bounded by a function(m), tending to zero, with probability tending to one asm , provided the data are uniformly distributed. This implies that any algorithm for the above mentioned problems yields asymptotically an arbitrarily small relative error with probability tending to one.     

Partial Lagrangian relaxation for general quadratic programming

We give a complete characterization of constant quadratic functions over an affine variety. This result is used to convexify the objective function of a general quadratic programming problem (Pb) which contains linear equality constraints. Thanks to this convexification, we show that one can express as a semidefinite program the dual of the partial Lagrangian relaxation of (Pb) where the linear constraints are not relaxed. We apply these results by comparing two semidefinite relaxations made from two sets of null quadratic functions over an affine variety.      

Solving large quadratic assignment problems on computational grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n = 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using a state-of-the-art branch-and-bound algorithm running on a federation of geographically distributed resources known as a computational grid. Solution of QAPs of unprecedented complexity, including the nug30, kra30b, and tho30 instances, is reported. Received: September 29, 2000 / Accepted: June 5, 2001?Published online October 2, 2001     

A relaxation modulus-based matrix splitting iteration method for solving linear complementarity problems

In this paper, a relaxation modulus-based matrix splitting iteration method is established, which covers the known general modulus-based matrix splitting iteration methods. The convergence analysis and the strategy of the choice of the parameters are given. Numerical examples show that the proposed methods are efficient and accelerate the convergence performance with less iteration steps and CPU times.     

Fuzzy costs in quadratic programming problems

Although quadratic programming problems are a special class of nonlinear programming, they can also be seen as general linear programming problems. These quadratic problems are of the utmost importance in an increasing variety of practical fields. As, in addition, ambiguity and vagueness are natural and ever-present in real-life situations requiring operative solutions, it makes perfect sense to address them using fuzzy concepts formulated as quadratic programming problems with uncertainty, i.e., as Fuzzy Quadratic Programming problems. This work proposes two novel fuzzy-sets-based methods to solve a particular class of Fuzzy Quadratic Programming problems which have vagueness coefficients in the objective function. Moreover, two other linear approaches are extended to solve the quadratic case. Finally, it is shown that the solutions reached from the extended approaches may be obtained from two proposed parametric multiobjective approaches.     

Ranking in quadratic integer programming problems

The present paper develops an algorithm for ranking the integer feasible solutions of a quadratic integer programming (QIP) problem. A linear integer programming (LIP) problem is constructed which provides bounds on the values of the objective function of the quadratic problem. The integer feasible solutions of this related integer linear programming problem are systematically scanned to rank the integer feasible solutions of the quadratic problem in non-decreasing order of the objective function values. The ranking in the QIP problem is useful in solving a nonlinear integer programming problem in which some other complicated nonlinear restrictions are imposed which cannot be included in the simple linear constraints of QIP, the objective function being still quadratic.     

Solving convex quadratic bilevel programming problems using an enumeration sequential quadratic programming algorithm

In this paper, we present an original method to solve convex bilevel programming problems in an optimistic approach. Both upper and lower level objective functions are convex and the feasible region is a polyhedron. The enumeration sequential linear programming algorithm uses primal and dual monotonicity properties of the primal and dual lower level objective functions and constraints within an enumeration frame work. New optimality conditions are given, expressed in terms of tightness of the constraints of lower level problem. These optimality conditions are used at each step of our algorithm to compute an improving rational solution within some indexes of lower level primal-dual variables and monotonicity networks as well. Some preliminary computational results are reported.     

QPCOMP: A quadratic programming based solver for mixed complementarity problems

QPCOMP is an extremely robust algorithm for solving mixed nonlinear complementarity problems that has fast local convergence behavior. Based in part on the NE/SQP method of Pang and Gabriel [14], this algorithm represents a significant advance in robustness at no cost in efficiency. In particular, the algorithm is shown to solve any solvable Lipschitz continuous, continuously differentiable, pseudo-monotone mixed nonlinear complementarity problem. QPCOMP also extends the NE/SQP method for the nonlinear complementarity problem to the more general mixed nonlinear complementarity problem. Computational results are provided, which demonstrate the effectiveness of the algorithm. This material is based on research supported by National Science Foundation Grant CCR-9157632, Department of Energy Grant DE-FG03-94ER61915, and the Air Force Office of Scientific Research Grant F49620-94-1-0036.     

A class of continuous quadratic programming problems

Summary The present paper deals with some duality relations of a class of continuous quadratic programming problems. The analysis is developed by use of technique ofDorn for quadratic programming problems.

---

Zusammenfassung Die vorliegende Arbeit beschäftigt sich mit verschiedenen Dualitätsrelationen für eine Klasse von stetigen quadratischen Optimierungsproblemen. Die Untersuchung basiert auf einem vonDorn entwickelten Verfahren für quadratische Optimierungsprobleme.

     

An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints

In this paper, we propose a branch-and-bound algorithm for finding a global optimal solution for a nonconvex quadratic program with convex quadratic constraints (NQPCQC). We first reformulate NQPCQC by adding some nonconvex quadratic constraints induced by eigenvectors of negative eigenvalues associated with the nonconvex quadratic objective function to Shor’s semidefinite relaxation. Under the assumption of having a bounded feasible domain, these nonconvex quadratic constraints can be further relaxed into linear ones to form a special semidefinite programming relaxation. Then an efficient branch-and-bound algorithm branching along the eigendirections of negative eigenvalues is designed. The theoretic convergence property and the worst-case complexity of the proposed algorithm are proved. Numerical experiments are conducted on several types of quadratic programs to show the efficiency of the proposed method.