Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.01.025 Byline: Etienne de Klerk Keywords: Semidefinite programming; Chordal sparsity; Algebraic symmetry Abstract: Semidefinite programming (SDP) may be seen as a generalization of linear programming (LP). In particular, one may extend interior point algorithms for LP to SDP, but it has proven much more difficult to exploit structure in the SDP data during computation. We survey three types of special structures in SDP data: 1. A common 'chordal' sparsity pattern of all the data matrices. This structure arises in applications in graph theory, and may also be used to deal with more general sparsity patterns in a heuristic way. 2. Low rank of all the data matrices. This structure is common in SDP relaxations of combinatorial optimization problems, and SDP approximations of polynomial optimization problems. 3. The situation where the data matrices are invariant under the action of a permutation group, or, more generally, where the data matrices belong to a low dimensional matrix algebra. Such problems arise in truss topology optimization, particle physics, coding theory, computational geometry, and graph theory. We will give an overview of existing techniques to exploit these structures in the data. Most of the paper will be devoted to the third situation, since it has received the least attention in the literature so far. Author Affiliation: Department of Econometrics and OR, Tilburg University, Tilburg, The Netherlands Article History: Received 19 September 2008; Accepted 16 January 2009

The article gives an algorithm to compute decomposition for ternary forms (n=3). The algorithm involves the solution of a series of system of linear matrix inequalities (LMI's).

Abstract: When the matrix of distances between cities is symmetric and circulant, the traveling salesman problem (TSP) reduces to the so-called symmetric circulant traveling salesman problem (SCTSP), that has applications in the design of reconfigurable networks, and in minimizing wallpaper waste. The complexity of the SCTSP is open, but conjectured to be NP-hard, and we compare different lower bounds on the optimal value that may be computed in polynomial time. We derive a new linear programming (LP) relaxation of the SCTSP from the semidefinite programming (SDP) relaxation in [E. de Klerk, D.V. Pasechnik, R. Sotirov, On semidefinite programming relaxation of the traveling salesman problem, SIAM Journal of Optimization 19 (4) (2008) 1559–1573]. Further, we discuss theoretical and empirical comparisons between this new bound and three well-known bounds from the literature, namely the Held-Karp bound [M. Held, R.M. Karp, The traveling salesman problem and minimum spanning trees, Operations Research 18 (1970) 1138–1162], the 1-tree bound, and the closed-form bound for SCTSP proposed in [J.A.A. van der Veen, Solvable cases of TSP with various objective functions, Ph.D. Thesis, Groningen University, The Netherlands, 1992]. [Copyright &y& Elsevier]