-
作者：de Klerk, Etienne; Pasechnik, Dmitrii V.; Schrijver, Alexander
作者单位：Centrum Wiskunde & Informatica (CWI); University of Amsterdam; Tilburg University
摘要：We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix *-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It ...
-
作者：Yaman, H.; Karasan, O. E.; Pinar, M. C.
作者单位：Ihsan Dogramaci Bilkent University
摘要：For the problem of selecting p items with interval objective function coefficients so as to maximize total profit, we introduce the r-restricted robust deviation criterion and seek solutions that minimize the r-restricted robust deviation. This new criterion increases the modeling power of the robust deviation (minmax regret) criterion by reducing the level of conservatism of the robust solution. It is shown that r-restricted robust deviation solutions can be computed efficiently. Results of e...
-
作者：Nayakkankuppam, Madhu V.
作者单位：Bloomberg L.P.
摘要：We describe an approach to the parallel and distributed solution of large-scale, block structured semidefinite programs using the spectral bundle method. Various elements of this approach (such as data distribution, an implicitly restarted Lanczos method tailored to handle block diagonal structure, a mixed polyhedral-semidefinite subdifferential model, and other aspects related to parallelism) are combined in an implementation called LAMBDA, which delivers faster solution times than previously...
-
作者：Laurent, Monique
摘要：We consider the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. When the polynomial equations have a finite set of complex solutions, we can reformulate this problem as a semidefinite programming problem. Our semidefinite representation involves combinatorial moment matrices, which are matrices indexed by a basis of the quotient vector space R[x(1), . . . ,x(n) ]/I, where I is the ideal generated by the polynomial equations in the problem. Moreov...
-
作者：Fukuda, Mituhiro; Braams, Bastiaan J.; Nakata, Maho; Overton, Michael L.; Percus, Jerome K.; Yamashita, Makoto; Zhao, Zhengji
作者单位：Institute of Science Tokyo; Tokyo Institute of Technology; Emory University; University of Tokyo; New York University
摘要：It has been a long-time dream in electronic structure theory in physical chemistry/chemical physics to compute ground state energies of atomic and molecular systems by employing a variational approach in which the two-body reduced density matrix (RDM) is the unknown variable. Realization of the RDM approach has benefited greatly from recent developments in semidefinite programming (SDP). We present the actual state of this new application of SDP as well as the formulation of these SDPs, which ...
-
作者：Sherali, HD; Smith, JC
作者单位：Virginia Polytechnic Institute & State University; University of Arizona
摘要：The traditional vertex packing problem defined on an undirected graph identifies the largest weighted independent set of nodes, that is, a set of nodes whose induced subgraph contains no edges. In this paper, we examine a generalized vertex packing problem (GVP-k) in which k violations to the independent set restriction are permitted, whereby k edges may exist within the subgraph induced by the chosen set of nodes. A particular context in which such problems arise is in the national airspace p...
-
作者：Carr, RD; Greenberg, HJ; Hart, WE; Konjevod, G; Lauer, E; Lin, H; Morrison, T; Phillips, CA
作者单位：United States Department of Energy (DOE); Sandia National Laboratories; University of Colorado System; University of Colorado Denver; Arizona State University; Arizona State University-Tempe; University of New Mexico; University of California System; University of California Berkeley
摘要：We present a series of related robust optimization models for placing sensors in municipal water networks to detect contaminants that are maliciously or accidentally injected. We formulate sensor placement problems as mixed-integer programs, for which the objective coefficients are not known with certainty. We consider a restricted absolute robustness criteria that is motivated by natural restrictions on the uncertain data, and we define three robust optimization models that differ in how the ...
-
作者：Ljubic, I; Weiskircher, R; Pferschy, U; Klau, GW; Mutzel, P; Fischetti, M
作者单位：Technische Universitat Wien; University of Graz; University of Padua
摘要：The Prize-Collecting Steiner Tree Problem (PCST) on a graph with edge costs and vertex profits asks for a subtree minimizing the sum of the total cost of all edges in the subtree plus the total profit of all vertices not contained in the subtree. PCST appears frequently in the design of utility networks where profit generating customers and the network connecting them have to be chosen in the most profitable way. Our main contribution is the formulation and implementation of a branch-and-cut a...
-
作者：Kong, Nan; Schaefer, Andrew J.; Hunsaker, Brady
作者单位：State University System of Florida; University of South Florida; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh
摘要：We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances whose extensiv...
-
作者：Corberan, Angel; Plana, Isaac; Sanchis, Jose M.
作者单位：University of Valencia; Universitat Politecnica de Valencia
摘要：In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed.
