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.     

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.     

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     

Massively parallel tabu search for the quadratic assignment problem

A new heuristic algorithm to perform tabu search on the Quadratic Assignment Problem (QAP) is developed. A massively parallel implementation of the algorithm on the Connection Machine CM-2 is provided. The implementation usesn ² processors, wheren is the size of the problem. The elements of the algorithm, calledPar_tabu, include dynamically changing tabu list sizes, aspiration criterion and long term memory. A new intensification strategy based on intermediate term memory is proposed and shown to be promising especially while solving large QAPs. The combination of all these elements gives a very efficient heuristic for the QAP: the best known or improved solutions are obtained in a significantly smaller number of iterations than in other comparative studies. Combined with the implementation on CM-2, this approach provides suboptimal solutions to QAPs of bigger dimensions in reasonable time.     

Ranking scalar products to improve bounds for the quadratic assignment problem

The eigenvalue bound for the quadratic assignment problem (QAP) is successively improved by considering a set of k-best scalar products, related to the QAP. An efficient procedure is proposedto find such a set of k-best scalar products. A class of QAPs is described for which this procedure in general improves existing lower bounds and at the same time generates good suboptimal solutions. The method leaves the user with a large flexibility in controlling the quality of the bound. However, since the method is sensitive to input data it should only be used in combination with other bounding rules.     

Solving Large Quadratic Assignment Problems in Parallel

Quadratic Assignment problems are in practice among the mostdifficult to solve in the class of NP-complete problems. Theonly successful approach hitherto has been Branch-and-Bound-basedalgorithms, but such algorithms are crucially dependent on good boundfunctions to limit the size of the space searched. Much work hasbeen done to identify such functions for the QAP, but with limitedsuccess.Parallel processing has also been used in order to increase the sizeof problems solvable to optimality. The systems used have, however, oftenbeen systems with relatively few, but very powerful vector processors, andhave hence not been ideally suited for computations essentially involving non-vectorizable computations on integers.In this paper we investigate the combination of one of the best bound functions for a Branch-and-Bound algorithm (the Gilmore-Lawler bound) and various testing, variable binding and recalculation of bounds between branchings when used in aparallel Branch-and-Bound algorithm. The algorithm has been implemented on a 16-processor MEIKO Computing Surface with Intel i860processors. Computational results from the solution of a number of large QAPs, including the classical Nugent 20 are reported.     

Pivoting for Size and Sparsity in Linear Programming Inversion Routes

^* Present address: The Operations Research Department, Stanford University, Stanford, California 94305, U.S.A. This note reports some experimental results on the inversionof real linear programming bases, with particular emphasis onthe compromise between minimum density and maximum numericalstability. The general features of a linear programming inversionroutine are outlined and the special structure of linear programsconsidered. The main result is a suitable and apparently safe"pivot tolerance" level, together with more general data onthe nature and behaviour of the problems.     

Lower bounds for the quadratic assignment problem via triangle decompositions

We consider transformations of the (metric) Quadratic Assignment Problem (QAP) that exploit the metric structure of a given instance. We show in particular how the structural properties of rectangular grids can be used to improve a given lower bound. Our work is motivated by previous research of Palubetskes (1988), and it extends a bounding approach proposed by Chakrapani and Skorin-Kapov (1993). Our computational results indicate that the present approach is practical; it has been applied to problems of dimension up ton = 150. Moreover, the new approach yields by far the best lower bounds on most of the instances of metric QAPs that we considered.The authors gratefully acknowledge financial support by the Christian Doppler Laboratorium für Diskrete Optimierung.     

A robust Lagrangian-DNN method for a class of quadratic optimization problems

The Lagrangian-doubly nonnegative (DNN) relaxation has recently been shown to provide effective lower bounds for a large class of nonconvex quadratic optimization problems (QAPs) using the bisection method combined with first-order methods by Kim et al. (Math Program 156:161–187, 2016). While the bisection method has demonstrated the computational efficiency, determining the validity of a computed lower bound for the QOP depends on a prescribed parameter \(\epsilon > 0\). To improve the performance of the bisection method for the Lagrangian-DNN relaxation, we propose a new technique that guarantees the validity of the computed lower bound at each iteration of the bisection method for any choice of \(\epsilon > 0\). It also accelerates the bisection method. Moreover, we present a method to retrieve a primal-dual pair of optimal solutions of the Lagrangian-DNN relaxation using the primal-dual interior-point method. As a result, the method provides a better lower bound and substantially increases the robustness as well as the effectiveness of the bisection method. Computational results on binary QOPs, multiple knapsack problems, maximal stable set problems, and quadratic assignment problems illustrate the robustness of the proposed method. In particular, a tight bound for QAPs with size \(n=50\) could be obtained.     

Well-posedness results for a class of partial differential equations with hysteresis arising in electromagnetism

We consider an evolutionary PDE motivated by models for electromagnetic processes in ferromagnetic materials. Magnetic hysteresis is represented by means of a hysteresis operator. Under suitable assumptions, an existence and uniqueness theorem is obtained, together with the Lipschitz continuous dependence on the data and some further regularity results. The discussion of the behaviour of the solution in dependence on physical parameters of the problem is also outlined.     

‘Strange’ phenomena in dynamical systems and their physical implications

Some recent developments in dynamical systems theory are outlined and their physical implications are discussed. In particular we introduce the concept of ‘strange attractors’: motions which arise as solutions of deterministic dynamical systems but which have extremely complicated and apparently random structures. We suggest that the behaviour of such motions has serious consequences for dynamical modelling exercises.     

The rotor dynamics of reeling machinery

Wide-faced rotors for high-speed reeling operations such as those employed in paper manufacture, printing, coating and laminating are considered, and the torsional behaviour of these units is investigated. Modelling, simulation and analysis techniques are involved enabling the prediction of the torsional vibrational signature of high-speed assemblies under acceleration and braking conditions. The results outlined show that simulated response characteristics can be easily obtained, and the effect of varying the rotor geometry can be routinely accommodated. The transient conditions presented for a reeling machine are commented upon with particular reference to the angular velocity and shear stress variation following torque changes. The effect on volume production is discussed.     

On the Applicability of Lower Bounds for Solving Rectilinear Quadratic Assignment Problems in Parallel

The quadratic assignment problem (QAP) belongs to the hard core of NP-hard optimization problems. After almost forty years of research only relatively small instances can be solved to optimality. The reason is that the quality of the lower bounds available for exact methods is not sufficient. Recently, lower bounds based on decomposition were proposed for the so called rectilinear QAP that proved to be the strongest for a large class of problem instances. We investigate the strength of these bounds when applied not only at the root node of a search tree but as the bound function used in a Branch-and-Bound code solving large scale QAPs.     

Generating quadratic assignment test problems with known optimal permutations

The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem of which the travelling-salesman problem is a special case. Although the QAP has been extensively studied during the past three decades, this problem remains very hard to solve. Problems of sizes greater than 15 are generally impractical to solve. For this reason, many heuristics have been developed. However, in the literature, there is a lack of test problems with known optimal solutions for evaluating heuristic algorithms. Only recently Paulubetskis proposed a method to generate test problems with known optimal solutions for a special type of QAP. This paper concerns the generation of test problems for the QAP with known optimal permutations. We generalize the result of Palubetskis and provide test-problem generators for more general types of QAPs. The test-problem generators proposed are easy to implement and were also tested on several well-known heuristic algorithms for the QAP. Computatinal results indicate that the test problems generated can be used to test the effectiveness of heuristic algorithms for the QAP. Comparison with Palubetskis' procedure was made, showing the superiority of the new test-problem generators. Three illustrative test problems of different types are also provided in an appendix, together with the optimal permutations and the optimal objective function values.     

Expert knowledge and computer-aided group decision making: Some pragmatic reflections

Based on a simple outranking method of multi-attribute decision making (MADM), called Dichotomy-Cut, developed in recent years and published elsewhere, this paper describes how to reliably elicit the necessary decision knowledge for implementing various decision modes via this method and its computerized support - UNIDAS 2. The most important features of this method are outlined, namely, how to compose the preference ordered matrices and which are the basic decision rules. Special attention should be paid to specific interactive group decision behaviour of experts. Two examples plainly explain the contents discussed.     

Exploration of Internal Response Sensitivities of Materially Nonlinear Structures

In this paper the idea of design exploration in the context of structural design sensitivity analysis considering elastoplastic material behaviour is outlined. Sensitivity information involves the influence of history dependent material behaviour and is obtained analytically by means of a variational approach. Applying singular value decomposition (SVD) to response sensitivities provides deep insight into sensitivity information and can be used to identify design changes with major influence on structural response. With this additional information, it is possible to refine an optimisation problem and reduce its complexity. (© 2017 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Recent advances in the solution of quadratic assignment problems

 The quadratic assignment problem (QAP) is notoriously difficult for exact solution methods. In the past few years a number of long-open QAPs, including those posed by Steinberg (1961), Nugent et al. (1968) and Krarup (1972) were solved to optimality for the first time. The solution of these problems has utilized both new algorithms and novel computing structures. We describe these developments, as well as recent work which is likely to result in the solution of even more difficult instances. Received: February 13, 2003 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words. quadratic assignment problem – discrete optimization – branch and bound Mathematics Subject Classification (1991): 90C27, 90C09, 90C20     

Characterisation and Modelling of Piezoceramic Actuator Hystereses

Piezoelectric ceramics are often used as actuators in smart structures technology. In the vast majority of papers dealing with this topic only linear constitutive relations are used. However, the electric field-strain relations of such actuators show hysteretic behaviour, which means that the piezoelectric coupling coefficient is not constant. In this study the hysteresis of a mechanically unconstrained actuator is obtained using the Michelson interferometry. The hysteretic behaviour is modelled by a Preisach model. Using these experimental data, for the modelling of an active structure with embedded piezoelectric actuators the actual coupling coefficient can then be determined with the help of the Preisach model. With this procedure the actuation strain of an embedded actuator, including the physical nonlinearities, can be calculated using the material characteristics obtained for an unconstrained actuator. For an experimental validation of the method outlined above, a Lead Zirconate Titanate (PZT) actuator is characterised experimentally and then glued to a cantilever beam. Then, the tip displacement of the actuated beam is determined experimentally and simulated numerically using the above method. The experimental and numerical results agree reasonably well if the shear lag due to the bonding layer between the actuator and the structure is taken into consideration. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Hydraulic fracturing with a simplified fluid model and XFEM

In hydraulic fracturing, the pressure exerted by the fracking fluid onto the surrounding solid, is typically obtained from solving the Reynolds equation. This is not always robust and leads to a complex behaviour at the crack front (toughness or viscous regimes). In the presented work, the Reynolds equation is replaced by a simplified fluid model, where pre-defined pressure distributions are assumed which lead to a simpler and robust coupled problem. The surface integration of the fluid pressure onto the surrounding solid is outlined without any limitations on the distributions. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)