Scalable Effective Approaches for Quadratic Assignment Problems Based on Conic Optimization and Applications

Abstract

This project deals with quadratic assignment problems (QAP) that arise from a broad range of applications such as target tracking, resource allocation and communications. The main endeavor of the project is to explore the structure of the associated data matrix of the underlying problem, combining with various matrix splitting schemes, to derive strong and yet cheap to compute convex optimization relaxations. The new relaxation can be further used to obtain a good approximation to the original problem or help the development of exact algorithms. The efficacy of the proposed approaches has been demonstrated via both theoretical and numerical comparisons with other existing approaches in the literature, and the techniques developed through the project have been successfully applied to large scale QAPs from communications and information processing.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 09, 2012
Accession Number
ADA564202

Entities

People

  • Hans D. Mittelmann
  • Jiming Peng

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Biological Sciences
  • Computations
  • Computer Programming
  • Data Analysis
  • Data Mining
  • Evolutionary Algorithms
  • Information Processing
  • Information Science
  • Information Theory
  • Literature
  • Mathematical Programming
  • Mathematics
  • Optimization
  • Splitting
  • Systems Engineering
  • Two Dimensional

Readers

  • Distributed Systems and Data Platform Development
  • Operations Research