On Compact Formulations for Integer Programs Solved by Column Generation

Column generation has become a powerful tool in solving large scale integer programs. It is well known that most of the often reported compatibility issues between pricing subproblem and branching rule disappear when branching decisions are based on imposing constraints on the subproblem's variables. This can be generalized to branching on variables of a so-called compact formulation. We constructively show that such a formulation always exists under mild assumptions. It has a block diagonal structure with identical subproblems, each of which contributes only one column in an integer solution. This construction has an interpretation as reversing a Dantzig-Wolfe decomposition. Our proposal opens the way for the development of branching rules adapted to the subproblem's structure and to the linking constraints.     

Stabilized plethysms for the classical Lie groups

The plethysms of the Weyl characters associated to a classical Lie group by the symmetric functions stabilize in large rank. In the case of a power sum plethysm, we prove that the coefficients of the decomposition of this stabilized form on the basis of Weyl characters are branching coefficients which can be determined by a simple algorithm. This generalizes in particular some classical results by Littlewood on the power sum plethysms of Schur functions. We also establish explicit formulas for the outer multiplicities appearing in the decomposition of the tensor square of any irreducible finite-dimensional module into its symmetric and antisymmetric parts. These multiplicities can notably be expressed in terms of the Littlewood-Richardson coefficients.     

Branching formula for q-Littlewood–Richardson coefficients

A generalized inversion statistic is introduced on k-tuples of semistandard tableaux. It is shown that the cospin of a semistandard k-ribbon tableau is equal to the generalized inversion number of its k-quotient. This leads to a branching formula for the q-analogue of Littlewood–Richardson coefficients defined by Lascoux, Leclerc, and Thibon. This branching formula generalizes a recurrence of Garsia and Procesi involving Kostka–Foulkes polynomials.     

�лָ������ɷ�֧���̵�Feller����

首先, 当$Q$是一个拟单调的q矩阵的时候, 我们找出最小的$Q$函数是一个Feller的转移函数的准则. 然后我们把这个结论应用于生成分支q矩阵并得到相应的生成分支过程的Feller准则. 特别地, 设$\theta$是分支q矩阵中的非线性数, 总是存在一个分点$\theta_0$满足$1\leq\theta_0\leq2$或$\theta_0<+\infty$使得 生成分支过程是否是Feller的要依据$\theta<\theta_0$或者$\theta>\theta_0$.     

Terme constant de fonctions sur un espace symétrique réductif p-adique

We generalize Casselman's pairing to p-adic reductive symmetric spaces and study the asymptotic behaviour of certain generalized coefficients. We also prove an analogue of a lemma due to Langlands which allows us to prove a disjunction result for the Cartan decomposition of the p-adic reductive symmetric spaces.     

Nonsingular systems of generalized Sylvester equations: An algorithmic approach

We consider the uniqueness of solution (i.e., nonsingularity) of systems of r generalized Sylvester and ?‐Sylvester equations with n×n coefficients. After several reductions, we show that it is sufficient to analyze periodic systems having, at most, one generalized ?‐Sylvester equation. We provide characterizations for the nonsingularity in terms of spectral properties of either matrix pencils or formal matrix products, both constructed from the coefficients of the system. The proposed approach uses the periodic Schur decomposition and leads to a backward stable O(n³r) algorithm for computing the (unique) solution.     

The Plancherel decomposition for a reductive symmetric space. II. Representation theory

We obtain the Plancherel decomposition for a reductive symmetric space in the sense of representation theory. Our starting point is the Plancherel formula for spherical Schwartz functions, obtained in part I. The formula for Schwartz functions involves Eisenstein integrals obtained by a residual calculus. In the present paper we identify these integrals as matrix coefficients of the generalized principal series.     

Decomposition approximation of queueing-network control models with tree structures

We devise a decomposition approximation method for a general branching queueing network with service-rate controls. The decomposition method, which reduces and simplifies computation routines considerably, results from the conditions for monotone optimal control policies in induction arguments. We first isolate each branch of connected queues as a subnetwork and then link the subnetworks through branching nodes to approximate the optimal control policies for the global network. The numerical results for a wide class of cost models show that the approximated optimal policies from the decomposed problems are sufficiently close to the optimal policies of the global problem.     

A robust two-level domain decomposition preconditioner for systems of PDEs

Coarse spaces are instrumental in obtaining scalability for domain decomposition methods. However, it is known that most popular choices of coarse spaces perform rather weakly in presence of heterogeneities in the coefficients in the partial differential equations, especially for systems. Here, we introduce in a variational setting a new coarse space that is robust even when there are such heterogeneities. We achieve this by solving local generalized eigenvalue problems which isolate the terms responsible for slow convergence. We give a general theoretical result and then some numerical examples on a heterogeneous elasticity problem.     

Solving generalized eigenvalue problems on the interfaces to build a robust two-level FETI method

FETI is a very popular method, which has proved to be extremely efficient on many large-scale industrial problems. One drawback is that it performs best when the decomposition of the global problem is closely related to the parameters in equations. This is somewhat confirmed by the fact that the theoretical analysis goes through only if some assumptions on the coefficients are satisfied. We propose here to build a coarse space for which the convergence rate of the two-level method is guaranteed regardless of any additional assumptions. We do this by identifying the problematic modes using generalized eigenvalue problems.     

Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps

Coarse spaces are instrumental in obtaining scalability for domain decomposition methods for partial differential equations (PDEs). However, it is known that most popular choices of coarse spaces perform rather weakly in the presence of heterogeneities in the PDE coefficients, especially for systems of PDEs. Here, we introduce in a variational setting a new coarse space that is robust even when there are such heterogeneities. We achieve this by solving local generalized eigenvalue problems in the overlaps of subdomains that isolate the terms responsible for slow convergence. We prove a general theoretical result that rigorously establishes the robustness of the new coarse space and give some numerical examples on two and three dimensional heterogeneous PDEs and systems of PDEs that confirm this property.     

Estimates for polynomials in logarithms of some rational numbers

The Hermite-Pade approximations of the second type for algebra generated by a generalized Nikishin system of Markov functions corresponding to an infinite branching graph are investigated. Arithmetical applications of this construction are given. Namely, lower estimates for polynomials with integer coefficients in logarithms of some rational numbers are obtained. These estimates partially refine some known results obtained earlier by the Siegel method. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 6, pp. 179–194, 2005.     

A Characterization of Sparse Nonstationary Gabor Expansions

We investigate the problem of constructing sparse time–frequency representations with flexible frequency resolution, studying the theory of nonstationary Gabor frames (NSGFs) in the framework of decomposition spaces. Given a painless NSGF, we construct a compatible decomposition space and prove that the NSGF forms a Banach frame for the decomposition space. Furthermore, we show that the decomposition space norm can be completely characterized by a sparseness condition on the frame coefficients and we prove an upper bound on the approximation error occurring when thresholding the frame coefficients for signals belonging to the decomposition space.     

Proprietà di secondo ordine di un riferimento generalizzato

We consider a relativistic frame of reference, generalized in the polar sense [1]–[2],and the adapted non-holonomic techniques;then, we extend to non-orthogonal case second order propertiesof a standard frame of reference: Riemann tensor decomposition, Lie derivatives of the Ricci rotation coefficients, commutation formulae and spatial Bianchi identity.     

Generalized solution of a one-dimensional quasilinear boundary value problem of the hydriding type with nonlinear boundary conditions and state evolution

We consider a quasilinear parabolic boundary value problem of the third kind on an interval. The coefficients of the partial differential equation and the right-hand sides in the boundary conditions and the evolution equation for the state vector nonlinearly depend on time, the point, the state vector, and the values of the solution at the endpoints. This problem generalizes a number of models of formation and decomposition of metal hydrides. For the simplest finite-difference scheme, we prove the uniform convergence to a continuous generalized solution of the boundary value problem. A sample model is given.     

Small value probabilities for continuous state branching processes with immigration

We consider the small value probability of supercritical continuous state branching processes with immigration.From Pinsky(1972) it is known that under regularity condition on the branching mechanism and immigration mechanism,the normalized population size converges to a non-degenerate finite and positive limit W as t tends to infinity.We provide sharp estimate on asymptotic behavior of P(W≤ε) as ε→ 0+ by studying the Laplace transform of W.Without immigration,we also give a simpler proof for the small value probability in the non-subordinator case via the prolific backbone decomposition.     

ASYMPTOTIC BEHAVIOR OF POSITIVE RADIAL SOLUTIONS FOR THE GENERALIZED EMDEN-FOWLER EQUATION WITH APPLICATION

In this paper, we consider a class of semilinear parabolic differential equation where nonlinear term has local bounded coefficients. Under some assumptions, we get the existence and uniqueness of solution. Terminate to the time variable, we obtain the so called generalized Emden-Fowler equation and the asymptotic behavior of positive radial solutions have been given in all dimensions. At the end of this paper, we give its application to critical branching Brownian motion (also called measure-valued branching processes).     

Proprietà di 20 ordine di un riferimento isotropo

We extend to the isotropic case, by adapted non-holonomic techniques [1], 2^° order properties of a relativistic frame of reference, generalized in the polar sense [2,3]: Riemann and gravitational tensors decomposition, Lie derivative of the Ricci rotation coefficients, commutation formulae and finally Bianchi identity. All the decomposition tensors are formally invariant (as regards the standard case), by means of the longitudinal derivative extension. Received: June 14, 2000?Published online: October 2, 2001     

The Cauchy problem for Schr?dinger-type partial differential operators with generalized functions in the principal part and as data

We set-up and solve the Cauchy problem for Schr?dinger-type differential operators with generalized functions as coefficients, in particular, allowing for distributional coefficients in the principal part. Equations involving such kind of operators appeared in models of deep earth seismology. We prove existence and uniqueness of Colombeau generalized solutions and analyze the relations with classical and distributional solutions. Furthermore, we provide a construction of generalized initial values that may serve as square roots of arbitrary probability measures.     

The Cauchy problem for Schrödinger-type partial differential operators with generalized functions in the principal part and as data

We set-up and solve the Cauchy problem for Schrödinger-type differential operators with generalized functions as coefficients, in particular, allowing for distributional coefficients in the principal part. Equations involving such kind of operators appeared in models of deep earth seismology. We prove existence and uniqueness of Colombeau generalized solutions and analyze the relations with classical and distributional solutions. Furthermore, we provide a construction of generalized initial values that may serve as square roots of arbitrary probability measures.