Extended formulations in mixed integer conic quadratic programming

In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma et al. (INFORMS J Comput 20: 438–450, 2008) and Hijazi et al. (Comput Optim Appl 52: 537–558, 2012) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (Math Oper Res 26(2): 193–205 2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (Math Programm 103(2): 225–249, 2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms for MICQP. We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.     

Representations of Hecke Algebras and Dilations of Semigroup Crossed Products

A family of Hecke C^*-algebras can be realised as crossed productsby semigroups of endomorphisms. It is shown by dilating representationsof the semigroup crossed product that the category of representationsof the Hecke algebra is equivalent to the category of continuousunitary representations of a totally disconnected locally compactgroup.     

Bipartite partial duals and circuits in medial graphs

It is well known that a plane graph is Eulerian if and only if its geometric dual is bipartite. We extend this result to partial duals of plane graphs. We then characterize all bipartite partial duals of a plane graph in terms of oriented circuits in its medial graph.     

Gibbs Sampling with Diffuse Proper Priors: A Valid Approach to Data-Driven Inference?

Abstract

This article demonstrates by example that the use of the Gibbs sampler with diffuse proper priors can lead to inaccurate posterior estimates. Our results show that such inaccuracies are not merely limited to small sample settings.     

The Ramifications of the Centres: Quantised Function Algebras at Roots of Unity

This paper continues the study of quantised function algebrasO[G] of a semisimple group G at an lth root of unity . Thesealgebras were introduced by De Concini and Lyubashenko in 1994,and studied further by De Concini and Procesi and by Gordon,amongst others. Our main purpose here is to increase understandingof the finite-dimensional factor algebras O[G](g), for g G.We determine the representation type and block structure ofthese factors, and (for many g) describe them up to isomorphism.A series of parallel results is obtained for the quantised Borelalgebras and . 2000 Mathematical Subject Classification: 16W35,17B37.     

Dynamics of Decision Making in Animal Group Motion

We analyze a continuous-time model of a multi-agent system motivated by simulation studies on dynamics of decision making in animal groups in motion. Each individual moves at constant speed in the plane and adjusts its heading in response to relative headings of others in the population. The population includes two subgroups that are “informed” such that individuals in each subgroup have a preferred direction of motion. The model exhibits fast and slow time scales allowing for a reduction in the dimension of the problem. The stable solutions for the reduced model correspond to compromise by individuals with conflicting preferences. We study the global phase space for the proposed reduced model by computing equilibria and exploring stability and bifurcations. B. Nabet’s and N.E. Leonard’s work is supported in part by AFOSR grant FA9550-07-1-0-0528 and ONR grants N00014-02-1-0826 and N00014-04-1-0534. I.D. Couzin’s work was supported by the Royal Society, Balliol College and EPSRC grants GR/S04765/01 and GR/T11234/01, a Searle Scholar Award and DARPA grant HR001-05-1-0057. S.A. Levin’s work was supported in part by DARPA grant HR0011-05-1-0057 and NSF grant EF-0434319.     

Subregular Representations of {\mathfrak{s}}{\mathfrak{l}}_n and Simple Singularities of Type A n−1

Alexander Premet has stated the following problem: what is a relation between subregular nilpotent representations of a classical semisimple restricted Lie algebra and non-commutative deformations of the corresponding singularities? We solve this problem for type A.