Solution to the quadratic assignment problem usingsemi-Lagrangian relaxation

The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.

Backbone analysis and algorithm design for the quadratic assignment problem

As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.

Robust ACO-Based Landmark Matching and Maxillofacial Anomalies Classification

Imagery assessment is an efficient method for detecting craniofacial anomalies.A cephalometric landmark matching approach may help in orthodontic diagnosis,craniofacial growth assessment and treatment planning.Automatic landmark matching and anomalies detection helps face the manual labelling lim-itations and optimize preoperative planning of maxillofacial surgery.The aim of this study was to develop an accurate Cephalometric Landmark Matching method as well as an automatic system for anatomical anomalies classification.First,the Active Appearance Model(AAM)was used for the matching process.This pro-cess was achieved by the Ant Colony Optimization(ACO)algorithm enriched with proximity information.Then,the maxillofacial anomalies were classified using the Support Vector Machine(SVM).The experiments were conducted on X-ray cephalograms of 400 patients where the ground truth was produced by two experts.The frameworks achieved a landmark matching error(LE)of 0.50±1.04 and a successful landmark matching of 89.47%in the 2 mm and 3 mm range and of 100%in the 4 mm range.The classification of anomalies achieved an accuracy of 98.75%.Compared to previous work,the proposed approach is simpler and has a comparable range of acceptable matching cost and anomaly classification.Results have also shown that it outperformed the K-nearest neigh-bors(KNN)classifier.

Global Optimization of a Class of Nonconvex Quadratically Constrained Quadratic Programming Problems

In this paper we study a Class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.