-
作者：Laurent, Monique
摘要：We give a hierarchy of semidefinite upper bounds for the maximum size A(n,d) of a binary code of word length n and minimum distance at least d. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in n; this is based on a result of de Klerk et al. (Math Program, 2006) about the regular *-representation for matrix *-algebras. The Delsarte bound for A(n,d) is the first bound in the hierarchy, and the new bound of Schrijver (IEEE Trans. Inf...
-
作者：Avella, Pasquale; Sassano, Antonio; Vasil'ev, Igor
作者单位：University of Sannio; Sapienza University Rome; University of Salerno; Irkutsk Science Centre of the Russian Academy of Sciences; Russian Academy of Sciences; Matrosov Institute for System Dynamics & Control Theory SB RAS
摘要：Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a Branch-and-Cut-and-Price algorithm yielding provably good solutions for instances with vertical bar V vertical bar <= 3795. Key ingredients of the algorithm are a delayed column-and-row generation technique, exploiting the special structure of the formulation, to solve the LP-relaxation, and cutting planes to streng...
-
作者：Sim, Chee-Khian; Zhao, Gongyun
作者单位：National University of Singapore; National University of Singapore
摘要：An interior point method defines a search direction at each interior point of the feasible region. The search directions at all interior points together form a direction field, which gives rise to a system of ordinary differential equations (ODEs). Given an initial point in the interior of the feasible region, the unique solution of the ODE system is a curve passing through the point, with tangents parallel to the search directions along the curve. We call such curves off-central paths. We stu...
-
作者：Anitescu, Mihai; Tseng, Paul; Wright, Stephen J.
作者单位：United States Department of Energy (DOE); Argonne National Laboratory; University of Washington; University of Washington Seattle; University of Wisconsin System; University of Wisconsin Madison
摘要：The elastic-mode formulation of the problem of minimizing a nonlinear function subject to equilibrium constraints has appealing local properties in that, for a finite value of the penalty parameter, local solutions satisfying first- and second-order necessary optimality conditions for the original problem are also first- and second-order points of the elastic-mode formulation. Here we study global convergence properties of methods based on this formulation, which involve generating an (exact o...
-
作者：Freund, Robert M.; Ordonez, Fernando; Toh, Kim-Chuan
作者单位：University of Southern California; Massachusetts Institute of Technology (MIT); National University of Singapore; Singapore-MIT Alliance for Research & Technology Centre (SMART); Massachusetts Institute of Technology (MIT); Nanyang Technological University
摘要：We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the (Renegar-) condition measure C(d) of the data instance, (iii) a measure of the near-absence of strict complementarity of the o...
-
作者：Pap, Gyula
作者单位：Eotvos Lorand University
摘要：Even factors and square-free 2-factors are restricted matching problems for which it seems to be difficult to generalize Edmonds' matching algorithm directly. Here, we present a slight modification of Edmonds' algorithm, which adapts to these restricted matching problems. Thus, we construct algorithms for these problems which do not use alternating forests.
-
作者：So, Anthony Man-Cho; Ye, Yinyu
作者单位：Stanford University; Stanford University
摘要：We analyze the semidefinite programming (SDP) based model and method for the position estimation problem in sensor network localization and other Euclidean distance geometry applications. We use SDP duality and interior-point algorithm theories to prove that the SDP localizes any network or graph that has unique sensor positions to fit given distance measures. Therefore, we show, for the first time, that these networks can be localized in polynomial time. We also give a simple and efficient cr...
-
作者：Krokhmal, Pavlo A.; Grundel, Don A.; Pardalos, Panos M.
作者单位：University of Iowa; United States Department of Defense; United States Air Force; State University System of Florida; University of Florida
摘要：The Multidimensional Assignment Problem (MAP) is a higher-dimensional version of the Linear Assignment Problem that arises in the areas of data association, target tracking, resource allocation, etc. This paper elucidates the question of asymptotical behavior of the expected optimal value of the large-scale MAP whose assignment costs are independent identically distributed random variables with a prescribed probability distribution. We demonstrate that for a broad class of continuous distribut...
-
作者：Kocvara, Michal; Stingl, Michael
作者单位：Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences; Czech Technical University Prague; University of Erlangen Nuremberg
摘要：The limiting factors of second-order methods for large-scale semidefinite optimization are the storage and factorization of the Newton matrix. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable alternative for problems with a large number of variables and modest size of the constrained matrix. We further propose to a...
-
作者：Dukanovic, Igor; Rendl, Franz
作者单位：University of Klagenfurt; University of Maribor
摘要：The semidefinite programming formulation of the Lovasz theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number chi(G) or the clique number omega(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either chi(G) or omega(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be comp...
