Renata Sotirov

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

    A new library of structured semidefinite programming instances

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

    Solvers for semidefinite programming (SDP) have evolved a great deal in the last decade, and their development continues. In order to further support and encourage this development, we present a new test set of SDP instances. These instances arise from recent applications of SDP in coding theory, computational geometry, graph theory and structural design. Most … Read more

    On semidefinite programming relaxations of the traveling salesman problem

  • Etienne de Klerk
  • Renata Sotirov
  • Dmitrii V. Pasechnik
    • Categories Combinatorial Optimization, Semi-definite Programming Tags ,

    We consider a new semidefinite programming (SDP) relaxation of the symmetric traveling salesman problem (TSP), obtained via an SDP relaxation of the more general quadratic assignment problem (QAP). We show that the new relaxation dominates the one in the paper: [D. Cvetkovic, M. Cangalovic and V. Kovacevic-Vucic. Semidefinite Programming Methods for the Symmetric Traveling Salesman … 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

    Exploiting group symmetry in truss topology optimization

  • Yanqin Bai
  • Etienne de Klerk
  • Renata Sotirov
  • Dmitrii V. Pasechnik
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , ,

    We consider semidefinite programming (SDP) formulations of certain truss topology optimization problems, where a lower bound is imposed on the fundamental frequency of vibration of the truss structure. These SDP formulations were introduced in: [M. Ohsaki, K. Fujisawa, N. Katoh and Y. Kanno, Semi-definite programming for topology optimization of trusses under multiple eigenvalue constraints, Comp. … Read more

    On the Lovász theta-number of almost regular graphs with application to Erdös–Rényi graphs

  • Etienne de Klerk
  • Renata Sotirov
  • Michael W. Newman
  • Dmitrii V. Pasechnik
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , ,

    We consider k-regular graphs with loops, and study the Lovász theta-numbers and Schrijver theta’-numbers of the graphs that result when the loop edges are removed. We show that the theta-number dominates a recent eigenvalue upper bound on the stability number due to Godsil and Newman [C.D. Godsil and M.W. Newman. Eigenvalue bounds for independent sets. … Read more

    Clique-based facets for the precedence constrained knapsack problem

  • Andreas Bley
  • Natashia Boland
  • Gary Froyland
  • Renata Sotirov
  • Christopher Fricke
    • Categories 0-1 Programming, Polyhedra

    We consider a knapsack problem with precedence constraints imposed on pairs of items, known as the precedence constrained knapsack problem (PCKP). This problem has applications in management and machine scheduling, and also appears as a subproblem in decomposition techniques for network design and other related problems. We present a new approach for determining facets of … Read more

    A Near Maximum Likelihood Decoding Algorithm for MIMO Systems Based on Semi-Definite Programming

  • Amir K. Khandani
  • Amin Mobasher
  • Renata Sotirov
  • Mahmoud Taherzadeh
    • Categories 0-1 Programming, Quadratic Programming, Telecommunications Tags , , , ,

    In Multi-Input Multi-Output (MIMO) systems, Maximum-Likelihood (ML) decoding is equivalent to finding the closest lattice point in an N-dimensional complex space. In general, this problem is known to be NP hard. In this paper, we propose a quasi-maximum likelihood algorithm based on Semi-Definite Programming (SDP). We introduce several SDP relaxation models for MIMO systems, with … Read more

    Magnetic Resonance Tissue Density Estimation using Optimal SSFP Pulse-Sequence Design

  • Christopher Anand
  • Renata Sotirov
  • Tamás Terlaky
  • Zhuo Zheng
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , ,

    In this paper, we formulate a nonlinear, nonconvex semidefinite optimization problem to select the steady-state free precession (SSFP) pulse-sequence design variables which maximize the contrast to noise ratio in tissue segmentation. The method could be applied to other pulse sequence types, arbitrary numbers of tissues, and numbers of images. To solve the problem we use … Read more

    The Bundle Method in Combinatorial Optimization

  • Ilse Fischer
  • Franz Rendl
  • Renata Sotirov
  • Gerald Gruber
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Nonsmooth Optimization Tags , ,

    We propose a dynamic version of the bundle method to get approximate solutions to semidefinite programs with a nearly arbitrary number of linear inequalities. Our approach is based on Lagrangian duality, where the inequalities are dualized, and only a basic set of constraints is maintained explicitly. This leads to function evaluations requiring to solve a … Read more