The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures i...
详细信息
The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a variety of mathematical structures including, for example, algebraic connectivity, permutation matrices, and association schemes. The main results of this paper are twofold. First, de Klerk and Sotirov [de Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. programming 133(1):75-91.] present a semidefinite program (SDP) based on permutation matrices and symmetry reduction;they show that it is incomparable to the subtour elimination linear program but generally dominates it on small instances. We provide a family of simplicial TSP instances that shows that the integrality gap of this SDP is unbounded. Second, we show that these simplicial TSP instances imply the unbounded integrality gap of every SDP relaxation of the TSP mentioned in the survey on SDP relaxations of the TSP in section 2 of Sotirov [Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds., Handbook on Semi-definite, Conic and Polynomial Optimization (Springer, New York), 795-819.]. In contrast, the subtour linear program performs perfectly on simplicial instances. The simplicial instances thus form a natural litmus test for future SDP relaxations of the TSP.
A semidefinite programming (SDP) relaxation approach is proposed to solve multiuser detection problems in systems with M-ary quadrature amplitude modulation (M-QAM). In the proposed approach, the optimal M-ary maximum...
详细信息
A semidefinite programming (SDP) relaxation approach is proposed to solve multiuser detection problems in systems with M-ary quadrature amplitude modulation (M-QAM). In the proposed approach, the optimal M-ary maximum likelihood (ML) detection is carried out by converting the associated M-ary integer programming problem into a binary integer programming problem. Then a relaxation approach is adopted to convert the binary integer programming problem into an SDP problem. This relaxation process leads to a detector of much reduced complexity. A multistage approach is then proposed to improve the performance of the SDP relaxation based detectors. Computer simulations demonstrate that the symbol-error rate (SER) performance offered by the proposed multistage SDP relaxation based detectors outperforms that of several existing suboptimal detectors.
For q, n, d is an element of N, let A(q)(L) (n, d) denote the maximum cardinality of a code C subset of Z(q)(n) with minimum Lee distance at least d, where Z(q) denotes the cyclic group of order q. We consider a semid...
详细信息
For q, n, d is an element of N, let A(q)(L) (n, d) denote the maximum cardinality of a code C subset of Z(q)(n) with minimum Lee distance at least d, where Z(q) denotes the cyclic group of order q. We consider a semidefinite programming bound based on triples of codewords, which bound can be computed efficiently using symmetry reductions, resulting in several new upper bounds on A(q)(L)(n, d). The technique also yields an upper bound on the independent set number of the nth strong product power of the circular graph C-d,C-q, which number is related to the Shannon capacity of C-d,C-q. Here C-d,C-q is the graph with vertex set Z(q), in which two vertices are adjacent if and only if their distance (mod q) is strictly less than d. The new bound does not seem to improve significantly over the bound obtained from Lovasz theta-function, except for very small n. (C) 2019 Elsevier B.V. All rights reserved.
We initiate study of the Terwilliger algebra and related semidefinite programming techniques for the conjugacy scheme of the symmetric group Sym(n). In particular, we compute orbits of ordered pairs on Sym(n) acted up...
详细信息
We initiate study of the Terwilliger algebra and related semidefinite programming techniques for the conjugacy scheme of the symmetric group Sym(n). In particular, we compute orbits of ordered pairs on Sym(n) acted upon by conjugation and inversion, explore a block diagonalization of the associated algebra, and obtain improved upper bounds on the size M(n, D) of permutation codes of lengths n = 6, 7. For instance, these techniques detect the nonexistence of the projective plane of order six via M(6, 5) < 30 and yield a new upper bound M(7, 4) < 535 for a challenging open case. Each of these represents an improvement on earlier Delsarte linear programming results. (C) 2014 Elsevier B.V. All rights reserved.
作者：
Wang, XinXie, WeiDuan, RunyaoUniv Technol Sydney
Fac Engn & Informat Technol Ctr Quantum Software & Informat Ultimo NSW 2007 Australia Chinese Acad Sci
Acad Math & Syst Sci UTS AMSS Joint Res Lab Quantum Computat & Quantum Beijing 100190 Peoples R China
We investigate the classical communication over quantum channels when assisted by no-signaling and positive-partial-transpose-preserving (PPT) codes, for which both the optimal success probability of a given transmiss...
详细信息
We investigate the classical communication over quantum channels when assisted by no-signaling and positive-partial-transpose-preserving (PPT) codes, for which both the optimal success probability of a given transmission rate and the one-shot epsilon-error capacity are formalized as semidefinite programs (SDPs). Based on this, we obtain improved SDP finite blocklength converse bounds of general quantum channels for entanglement-assisted codes and unassisted codes. Furthermore, we derive two SDP strong converse bounds for the classical capacity of general quantum channels: for any code with a rate exceeding either of the two bounds of the channel, the success probability vanishes exponentially fast as the number of channel uses increases. In particular, applying our efficiently computable bounds, we derive an improved upper bound on the classical capacity of the amplitude damping channel. We also establish the strong converse property for the classical and private capacities of a new class of quantum channels. We finally study the zero-error setting and provide efficiently computable upper bounds on the one-shot zero-error capacity of a general quantum channel.
For a given schedule of a round-robin tournament and a matrix of distances between homes of teams, an optimal home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance....
详细信息
ISBN:
(纸本)3540262245
For a given schedule of a round-robin tournament and a matrix of distances between homes of teams, an optimal home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance. We propose a technique to transform the problem to MIN RES CUT. We apply Goemans and Williamson's 0.878-approximation algorithm for MAX RES CUT, which is based on a positive semidefinite programming relaxation, to the obtained MIN RES CUT instances. Computational experiments show that our approach quickly generates solutions of good approximation ratios.
This paper presents a unified binary semidefinite programming (BSDP) model with binary decision variables, for optimal placement of phasor measurement units, considering the impact of pre-existing conventional and syn...
详细信息
ISBN:
(纸本)9788894105124
This paper presents a unified binary semidefinite programming (BSDP) model with binary decision variables, for optimal placement of phasor measurement units, considering the impact of pre-existing conventional and synchronized phasor measurements as well as the limited channel capacity of phasor measurement units. A linear objective function is minimized subject to linear matrix inequality observability constraints. The developed method is solved with an outer approximation scheme based on binary integer linear programming. The proposed method is illustrated using the IEEE 14-bus test system. Simulations are conducted on the IEEE 57-bus and 118-bus test systems to prove the validity of the proposed method.
We describe an SDP relaxation based method for the position estimation problem in wireless sensor networks. The optimization problem is set up so as to minimize the error in sensor positions to fit distance measures. ...
详细信息
ISBN:
(纸本)1581138466
We describe an SDP relaxation based method for the position estimation problem in wireless sensor networks. The optimization problem is set up so as to minimize the error in sensor positions to fit distance measures. Observable gauges are developed to check the quality of the point estimation of sensors or to detect erroneous sensors. The performance of this technique is highly satisfactory compared to other techniques. Very few anchor nodes are required to accurately estimate the position of all the unknown nodes in a network. Also the estimation errors are minimal even when the anchor nodes are not suitably placed within the network or the distance measurements are noisy.
Many problems of interest can be solved by means of semidefinite programming (SDP). The potential applications range from telecommuni- cations, electrical power systems, game theory and many more fields. Ad- ditionall...
详细信息
Many problems of interest can be solved by means of semidefinite programming (SDP). The potential applications range from telecommuni- cations, electrical power systems, game theory and many more fields. Ad- ditionally, the fact that SDP is a subclass of convex optimization brings a set of theoretical guarantees that makes SDP very appealing. However, among all sub-classes of convex optimization, SDP remains one of the most challenging in practice. State-of-the-art semidefinite programming solvers still do not e? ciently solve large scale instances. In this regard, this thesis proposes a novel algorithm for solving SDP problems. The main contribu- tion of this novel algorithm is to achieve a substantial speedup by exploiting the low-rank property inherent to several SDP problems. The convergence of the new methodology is proved by showing that the novel algorithm reduces to a particular case of the Approximated Proximal Point Algorithm. Along with the theoretical contributions, an open source numerical solver, called ProxSDP, is made available with this work. The performance of ProxSDP in comparison to state-of-the-art SDP solvers is evaluated on three case studies.
暂无评论