quadratic assignment problem

Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems

  • Etienne de Klerk
  • Marianna Eisenberg-Nagy
  • Renata Sotirov
  • Uwe Truetsch
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The reformulation-linearization technique (RLT), introduced in [W.P. Adams, H.D. Sherali, A tight linearization and an algorithm for zero-one quadratic programming problems, Management Science, 32(10):1274–1290, 1986], provides a way to compute linear programming bounds on the optimal values of NP-hard combinatorial optimization problems. In this paper we show that, in the presence of suitable algebraic symmetry … Read more

    A LINEAR TIME ALGORITHM FOR THE KOOPMANS-BECKMANN QAP LINEARIZATION AND RELATED PROBLEMS

  • Santosh N. Kabadi
  • Abraham Punnen
    • Categories Combinatorial Optimization Tags , ,

    An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in O(n4) … Read more

    On semidefinite programming bounds for graph bandwidth

  • Etienne de Klerk
  • Marianna Eisenberg-Nagy
  • Renata Sotirov
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We propose two new lower bounds on graph bandwidth and cyclic bandwidth based on semidefinite programming (SDP) relaxations of the quadratic assignment problem. We compare the new bounds with two other SDP bounds in [A. Blum, G. Konjevod, R. Ravi, and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Theoretical Computer Science, … Read more

    A Feasible method for Optimization with Orthogonality Constraints

  • Zaiwen Wen
  • Wotao Yin
    • Categories Approximation Algorithms, Nonlinear Optimization Tags , , , , , , , , , ,

    Minimization with orthogonality constraints (e.g., $X^\top X = I$) and/or spherical constraints (e.g., $\|x\|_2 = 1$) has wide applications in polynomial optimization, combinatorial optimization, eigenvalue problems, sparse PCA, p-harmonic flows, 1-bit compressive sensing, matrix rank minimization, etc. These problems are difficult because the constraints are not only non-convex but numerically expensive to preserve during iterations. … Read more

    SDP relaxations for some combinatorial optimization problems

  • Renata Sotirov
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    In this chapter we present recent developments on solving various combinatorial optimization problems by using semidefinite programming (SDP). We present several SDP relaxations of the quadratic assignment problem and the traveling salesman problem. Further, we show the equivalence of several known SDP relaxations of the graph equipartition problem, and present recent results on the bandwidth … Read more

    Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers

  • Cesar Beltran-Royo
  • Liang Ma
  • Huizhen Zhang
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags ,

    The Quadratic Assignment Problem (QAP) can be solved by linearization, where one formulates the QAP as a mixed integer linear programming (MILP) problem. On the one hand, most of these linearization are tight, but hardly exploited within a reasonable computing time because of their size. On the other hand, Kaufman and Broeckx formulation [1] is … Read more

    Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry

  • Etienne de Klerk
  • Renata Sotirov
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced in: [Q. Zhao, S.E. Karisch, F. Rendl, and H. Wolkowicz. Semidefinite Programming Relaxations for the Quadratic Assignment Problem. Journal of Combinatorial Optimization, 2,71–109, 1998.] Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP … Read more

    Effective formulation reductions for the quadratic assignment problem

  • Cesar Beltran-Royo
  • Miguel Constantino
  • Huizhen Zhang
    • Categories Combinatorial Optimization Tags , , ,

    In this paper we study two formulation reductions for the quadratic assignment problem (QAP). In particular we apply these reductions to the well known Adams and Johnson [2] integer linear programming formulation of the QAP, which we call formulation IPQAP-I. We analyze two cases: In the first case, we study the effect of constraint reduction. … Read more

    Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem

  • Etienne de Klerk
  • Renata Sotirov
    • Categories Semi-definite Programming Tags ,

    We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB – a quadratic assignment problem … Read more

    Graph Modeling for Quadratic Assignment Problem Associated with the Hypercube

  • Hans D Mittelmann
  • Jiming Peng
  • Xiaolin Wu
    • Categories Applications - Science and Engineering, Graphs and Matroids, Telecommunications Tags

    In the paper we consider the quadratic ssignment problem arising from channel coding in communications where one coefficient matrix is the adjacency matrix of a hypercube in a finite dimensional space. By using the geometric structure of the hypercube, we first show that there exist at least $n$ different optimal solutions to the underlying QAPs. … Read more