Renata Sotirov 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
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
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
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
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
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
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
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
Semidefinite Programming (SDP) has recently turned out to be a very powerful tool for approximating some NP-hard problems. The nature of the Quadratic Assignment Problem suggests SDP as a way to derive tractable relaxation. We recall some SDP relaxations of QAP and solve them approximately using the Bundle Method. The computational results demonstrate the efficiency … Read more
Semidefinite Programming (SDP) provides strong bounds for many NP-hard combinatorial problems. Arguably the most popular/efficient search direction for solving SDPs using a primal-dual interior point (p-d i-p) framework is the {\em HKM direction}. This direction is a Newton direction found from the linearization of a symmetrized version of the optimality conditions. For many of the … Read more