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.     

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.     

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.     

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).     

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.     

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.     

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.     

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.     

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.     

Multifractal analysis of the divergence of Fourier series: The extreme cases

We study the size, in terms of the Hausdorff dimension, of the subsets of T such that the Fourier series of a generic function in L ¹(T), L ^p (T), or C(T) may behave badly. Genericity is related to the Baire Category Theorem or the notion of prevalence. This paper is a continuation of [3].     

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.     

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.     

On ray shooting in convex polytopes

LetP be a convex polytope withn facets in the Euclidean space of a (small) fixed dimensiond. We consider themembership problem forP (given a query point, decide whether it lies inP) and theray shooting problem inP (given a query ray originating insideP, determine the first facet ofP hit by it). It was shown in [AM2] that a data structure for the membership problem satisfying certain mild assumptions can also be used for the ray shooting problem, with a logarithmic overhead in query time. Here we show that some specific data structures for the membership problem can be used for ray shooting in a more direct way, reducing the overhead in the query time and eliminating the use of parametric search. We also describe an improved static solution for the membership problem, approaching the conjectured lower bounds more tightly.     

A modification of the DIRECT method for Lipschitz global optimization for a symmetric function

In this paper, we consider a global optimization problem for a symmetric Lipschitz continuous function. An efficient modification of the well-known DIRECT (DIviding RECTangles) method called SymDIRECT is proposed for solving this problem. The method is illustrated and tested on several standard test functions. The application of this method to solving complex center-based clustering problems for the data having only one feature is particularly presented.     

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). IIof periodic functions by Fourier sums (small smoothness). II

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 ? 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.     

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.     

An entire space polynomial-time algorithm for linear programming

We propose an entire space polynomial-time algorithm for linear programming. First, we give a class of penalty functions on entire space for linear programming by which the dual of a linear program of standard form can be converted into an unconstrained optimization problem. The relevant properties on the unconstrained optimization problem such as the duality, the boundedness of the solution and the path-following lemma, etc, are proved. Second, a self-concordant function on entire space which can be used as penalty for linear programming is constructed. For this specific function, more results are obtained. In particular, we show that, by taking a parameter large enough, the optimal solution for the unconstrained optimization problem is located in the increasing interval of the self-concordant function, which ensures the feasibility of solutions. Then by means of the self-concordant penalty function on entire space, a path-following algorithm on entire space for linear programming is presented. The number of Newton steps of the algorithm is no more than $O(nL\log (nL/ {\varepsilon }))$ , and moreover, in short step, it is no more than $O(\sqrt{n}\log (nL/{\varepsilon }))$ .     

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).