An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach Compact Quadratic Convex Reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general non-linear solver BARON (Sahinidis and Tawarmalani, User??s manual, 2010) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the Constrained Task Assignment Problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.     

Using RngStreams for parallel random number generation in C++ and R

The RngStreams software package provides one viable solution to the problem of creating independent random number streams for simulations in parallel processing environments. Techniques are presented for effectively using RngStreams with C++ programs that are parallelized via OpenMP or MPI. Ways to access the backbone generator from RngStreams in R through the parallel and rstream packages are also described. The ideas in the paper are illustrated with both a simple running example and a Monte Carlo integration application.     

Narrowness implies uniformity

This paper is about varietiesV of universal algebras which satisfy the following numerical condition on the spectrum: there are only finitely many prime integersp such thatp is a divisor of the cardinality of some finite algebra inV. Such varieties are callednarrow. The variety (or equational class) generated by a classK of similar algebras is denoted by V(K)=HSPK. We define Pr (K) as the set of prime integers which divide the cardinality of a (some) finite member ofK. We callK narrow if Pr (K) is finite. The key result proved here states that for any finite setK of finite algebras of the same type, the following are equivalent: (1) SPK is a narrow class. (2) V(K) has uniform congruence relations. (3) SK has uniform congruences and (3) SK has permuting congruences. (4) Pr (V(K))= Pr(SK). A varietyV is calleddirectly representable if there is a finite setK of finite algebras such thatV= V(K) and such that all finite algebras inV belong to PK. An equivalent definition states thatV is finitely generated and, up to isomorphism,V has only finitely many finite directly indecomposable algebras. Directly representable varieties are narrow and hence congruence modular. The machinery of modular commutators is applied in this paper to derive the following results for any directly representable varietyV. Each finite, directly indecomposable algebra inV is either simple or abelian.V satisfies the commutator identity [x,y]=x·y·[1,1] holding for congruencesx andy over any member ofV. The problem of characterizing finite algebras which generate directly representable varieties is reduced to a problem of ring theory on which there exists an extensive literature: to characterize those finite ringsR with identity element for which the variety of all unitary leftR-modules is directly representable. (In the terminology of [7], the condition is thatR has finite representation type.) We show that the directly representable varieties of groups are precisely the finitely generated abelian varieties, and that a finite, subdirectly irreducible, ring generates a directly representable variety iff the ring is a field or a zero ring.     

Simple algebras of Weyl type

Over a fieldF of arbitrary characteristic, we define the associative and the Lie algebras of Weyl type on the same vector spaceA[D] =A?F[D] from any pair of a commutative associative algebra,A with an identity element and the polynomial algebraF[D] of a commutative derivation subalgebraD ofA We prove thatA[D], as a Lie algebra (modulo its center) or as an associative algebra, is simple if and only ifA isD-simple andA[D] acts faithfully onA. Thus we obtain a lot of simple algebras.     

Quasi-factors in ergodic theory

Motivated by the notion of quasi-factor in topological dynamics, we introduce an analogous notion in the context of ergodic theory. For two processes,X andY , we haveX?Y if and only ifY has a factor which is isomorphic to a quasi-factor ofX. On the other hand, weakly mixing processes can have nontrivial quasifactors which are not w.m. We characterize those ergodic processes which admit only trivial continuous ergodic quasi-factors, and use this characterization to conclude that a process with minimal selfjoinings is of this type. From this we derive the fact that for every suchX and any ergodicY eitherX ⊥Y orY extends some symmetric product ofX.     

Ein Approximationssatz für holomorphe Funktionen auf nicht-kompakten Riemannschen Flächen

Let R be a non-compact Riemann surface andO(R) the algebra of all holomorphic functions on R. A subalgebraA ?O(R) is calledfull (“voll”), if (F1) for every point ??R there is a function f∈A with a simple zero at ? and no other zeros; (F2) if f, g∈A and f/g has no poles, then f/∈A. In 1971 Ian RICHARDS set the problem whether full subalgebras are dense inO(R), with respect to the topology of compact convergence. We answer this question in the positive, using a lemma of I. RICHARDS and theorems of R. ARENS and the author. Does this approximation theorem remain true for Stein manifolds of dimension n>1, if one modifies condition (F1) in a natural way? A counterexample is provided by a domain of holomorphy G??² and a full, but not dense subalgebraA ?O(G).     

Two results for monocompact measures

For every finite measure space (Ω,A, P) whereA is K₁-generated we prove the equivalence of compactness and monocompactness for P . Moreover, we prove the existence of a perfect, not monocompaot probability, thus answering an open question in [6]. Let P be a charge on the algebraA andK ?A be a monocompact class. We show that P is o-additive ifK ^S P-approximatesK ^S, the family of finite unions inK , needs not to be monocompact.     

A computational study and survey of methods for the single-row facility layout problem

The single-row facility layout problem (SRFLP) is an NP-hard combinatorial optimization problem that is concerned with the arrangement of n departments of given lengths on a line so as to minimize the weighted sum of the distances between department pairs. (SRFLP) is the one-dimensional version of the facility layout problem that seeks to arrange rectangular departments so as to minimize the overall interaction cost. This paper compares the different modelling approaches for (SRFLP) and applies a recent SDP approach for general quadratic ordering problems from Hungerländer and Rendl to (SRFLP). In particular, we report optimal solutions for several (SRFLP) instances from the literature with up to 42 departments that remained unsolved so far. Secondly we significantly reduce the best known gaps and running times for large instances with up to 110 departments.     

Index formulae for subspaces of Kreîn spaces

For a subspaceS of a Kreîn spaceK and an arbitrary fundamental decompositionK=K ^?[+]K ⁺ ofK, we prove the index formula $$\kappa ^ - \left( \mathcal{S} \right) + \dim \left( {\mathcal{S}^ \bot \cap \mathcal{K}^ + } \right) = \kappa ^ + \left( {\mathcal{S}^ \bot } \right) + \dim \left( {\mathcal{S} \cap \mathcal{K}^ - } \right)$$ where κ^±(S) stands for the positive/negative signature ofS. The difference dim(S∩K ^?)?dim(S ^⊥∩K ⁺), provided it is well defined, is called the index ofS. The formula turns out to unify other known index formulac for operators or subspaces in a Kreîn space.     

SpeeDP: an algorithm to compute SDP bounds for very large Max-Cut instances

We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained $\{-1,1\}$ quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the non-convex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function and we define an efficient and globally convergent algorithm, called SpeeDP, for finding critical points of the LRSDP problem. We provide evidence of the effectiveness of SpeeDP by comparing it with other existing codes on an extended set of instances of the Max-Cut problem. We further include SpeeDP within a simply modified version of the Goemans?CWilliamson algorithm and we show that the corresponding heuristic SpeeDP-MC can generate high-quality cuts for very large, sparse graphs of size up to a million nodes in a few hours.     

Expansion of open sets and decomposition of continuous mappings

The notion of expansionA of open sets is introduced. ThenA-expansion continuous mappingf:X→Y is defined. The main result of this note is that a mappingf is continuous if and only if it is bothA-expansion continuous andB-expansion continuous, whereA-expansion,B-expansion are two mutually dual expansions.     

Approximation of \bar \psi - integrals of periodic functions by Fourier sums (small smoothness). Iof periodic functions by Fourier sums (small smoothness). I

We investigate the rate of convergence of Fourier series on the classes $L^{\bar \psi } $ N in the uniform and integral metrics. The results obtained are extended to the case where the classes $L^{\bar \psi } $ N are the classes of convolutions of functions from N with kernels with slowly decreasing coefficients. In particular, we obtain asymptotic equalities for the upper bounds of deviations of the Fourier sums on the sets $L^{\bar \psi } $ N which are solutions of the Kolmogorov-Nikol’skii problem. In addition, we establish an analog of the well-known Lebesgue inequality.     

LU-Factorization Versus Wiener-Hopf Factorization for Markov Chains

Our initial motivation was to understand links between Wiener-Hopf factorizations for random walks and LU-factorizations for Markov chains as interpreted by Grassman (Eur. J. Oper. Res. 31(1):132–139, 1987). Actually, the first ones are particular cases of the second ones, up to Fourier transforms. To show this, we produce a new proof of LU-factorizations which is valid for any Markov chain with a denumerable state space equipped with a pre-order relation. Factors have nice interpretations in terms of subordinated Markov chains. In particular, the LU-factorization of the potential matrix determines the law of the global minimum of the Markov chain. For any matrix, there are two main LU-factorizations according as you decide to enter 1 in the diagonal of the first or of the second factor. When we factorize the generator of a Markov chain, one factorization is always valid while the other requires some hypothesis on the graph of the transition matrix. This dissymmetry comes from the fact that the class of sub-stochastic matrices is not stable under transposition. We generalize our work to the class of matrices with spectral radius less than one; this allows us to play with transposition and thus with time-reversal. We study some particular cases such as: skip-free Markov chains, random walks (this gives the WH-factorization), reversible Markov chains (this gives the Cholesky factorization). We use the LU-factorization to compute invariant measures. We present some pathologies: non-associativity, non-unicity; these can be cured by smooth assumptions (e.g. irreductibility).     

Criteria for the injectivity of analytic sheaves

It is shown that a moduleL over the sheafO of germs of holomorphic functions on a domain G of Cⁿ is injective if and only if the following conditions are satisfied; a)L is flabby; b) for every closed set S ?G and every point z λ G, the stalk se _z of the sheafS ^L;U1→Γ S ^(U:L) is an injectiveO _z -module. It follows in particular that the sheaf of germs of hyperfunctions is injective over the sheaf of germs of analytic functions.     

Properties of some stochastic processes arising in estimation theory

Sample functions of random processes are used to make inferences about the properties of estimators. In particular, it is proved that optimal equivariant sequential estimation designs with stopping timet such that Εt n ₁, are better than optimal equivariant estimation of the location parameter for samples of sizen, with largen. It is assumed that the density has cusps of first or second kind.     

When is the radical associated with a module a torsion?

For an arbitrary R-module M we consider the radical (in the sense of Maranda)G _M, namely, the largest radical among all radicalsG, such thatG(M). We determine necessary and sufficient on M in order for the radicalG(M) to be a torsion. In particular,G(M) is a torsion if and only if M is a pseudo-injective module.     

A generalization of the katona theorem for crosst-intersecting families

LetX be ann-element set and letA and? be families of subsets ofX. We say thatA and? are crosst-intersecting if |A ∩ B| ≥ t holds for all A ∈A and for allB ∈ ?. Suppose thatA and ? are crosst-intersecting. This paper first proves a crosst-intersecting version of Harper's Theorem:

1. There are two crosst-intersecting Hamming spheresA ₀,? ₀ with centerX such that |A| ≤ |A ₀| and|?| ≤ |? ₀| hold.
2. Suppose thatt ≥ 2 and that the pair of integers (|A) is maximal with respect to direct product ordering among pairs of crosst-intersecting families. Then,A and? are Hamming spheres with centerX.

Using these claims, the following conjecture of Frankl is proven:

1. Ifn + t = 2k ? 1 then |A| |?| ≤ max \(\left\{ {\left( {K_k^n + \left( {_{k - 1}^{n - 1} } \right)} \right)^2 ,K_k^n K_{k - 1}^n } \right\}\) holds, whereK _l ⁿ is defined as \(\left( {_n^n } \right)\left( {_{n - 1}^n } \right) + \cdots + \left( {_l^n } \right).\)
2. Ifn + t = 2k then |A| |? ≤ (K _k ⁿ )² holds.

The extremal configurations are also determined.     

Eine explizite Einbettung für Möbius-Geometrien endlicher Dimension

A new and explicit embedding is given for geometries ?(R,L) of Möbius type (i.e.L any extension field ofR) and finite dimension n = (L:R). The image of a chain is an algebraic curve. Till now explicit embeddings of Möbius geometries have been known only in the case n = 2.