一类多乘积规划的加速算法

针对一类多乘积规划问题(MP),给出一个加速算法.首先导出一个与(MP)等价的逆凸问题(RCP),然后构造问题(RCP)的线性松弛化问题.算法的主要特点是提出了两个加速技巧,这些技巧可以用于改善算法的收敛速度.数值算例表明算法是可行的.     

Retraction closure property

We say that an algebra ${\mathcal{A}}$ has the retraction closure property (RCP) if the set of all retractions of ${\mathcal{A}}$ is closed with respect to fundamental operations of ${\mathcal{A}}$ applied pointwise. In this paper we investigate this property, both “locally” (one algebra) and “globally” (in some variety of algebras), especially emphasizing the case of groupoids. We compare the retraction closure property with the endomorphism closure property on both levels and prove that a necessary and sufficient condition for a variety V of algebras to have RCP is that V is a variety of entropic algebras that satisfy the diagonal identities.     

Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization

Disjunctive Programs can often be transcribed as reverse convex constrained problems with nondifferentiable constraints and unbounded feasible regions. We consider this general class of nonconvex programs, called Reverse Convex Programs (RCP), and show that under quite general conditions, the closure of the convex hull of the feasible region is polyhedral. This development is then pursued from a more constructive standpoint, in that, for certain special reverse convex sets, we specify a finite linear disjunction whose closed convex hull coincides with that of the special reverse convex set. When interpreted in the context of convexity/intersection cuts, this provides the capability of generating any (negative edge extension) facet cut. Although this characterization is more clarifying than computationally oriented, our development shows that if certain bounds are available, then convexity/intersection cuts can be strengthened relatively inexpensively.     

Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies

The Frequency Assignment Problem (FAP) in radio networks is the problem of assigning frequencies to transmitters exploiting frequency reuse while keeping signal interference to acceptable levels. The FAP is usually modelled by variations of the graph coloring problem. A Radiocoloring (RC) of a graph G(V,E) is an assignment function such that |Λ(u)−Λ(v)|2, when u,v are neighbors in G, and |Λ(u)−Λ(v)|1 when the distance of u,v in G is two. The discrete number of frequencies used is called order and the range of frequencies used, span. The optimization versions of the Radiocoloring Problem (RCP) are to minimize the span (min span RCP) or the order (min order RCP).In this paper, we deal with an interesting, yet not examined until now, variation of the radiocoloring problem: that of satisfying frequency assignment requests which exhibit some periodic behavior. In this case, the interference graph (modelling interference between transmitters) is some (infinite) periodic graph. Infinite periodic graphs usually model finite networks that accept periodic (in time, e.g. daily) requests for frequency assignment. Alternatively, they can model very large networks produced by the repetition of a small graph.A periodic graph G is defined by an infinite two-way sequence of repetitions of the same finite graph G_i(V_i,E_i). The edge set of G is derived by connecting the vertices of each iteration G_i to some of the vertices of the next iteration G_i+1, the same for all G_i. We focus on planar periodic graphs, because in many cases real networks are planar and also because of their independent mathematical interest.We give two basic results:

• We prove that the min span RCP is PSPACE-complete for periodic planar graphs.

• We provide an O(n(Δ(G_i)+σ)) time algorithm (where|V_i|=n, Δ(G_i) is the maximum degree of the graph G_i and σ is the number of edges connecting each G_i to G_i+1), which obtains a radiocoloring of a periodic planar graph G that approximates the minimum span within a ratio which tends to as Δ(G_i)+σ tends to infinity.

We remark that, any approximation algorithm for the min span RCP of a finite planar graph G, that achieves a span of at most αΔ(G)+constant, for any α and where Δ(G) is the maximum degree of G, can be used as a subroutine in our algorithm to produce an approximation for min span RCP of asymptotic ratio α for periodic planar graphs.

Sequential heuristic for the two-dimensional bin-packing problem

A heuristic approach for the two-dimensional bin-packing problem is proposed. The algorithm is based on the sequential heuristic procedure that generates each pattern to produce some items and repeats until all items are produced. Both guillotine and non-guillotine patterns can be used. Each pattern is obtained from calling a pattern-generation procedure, where the objective is to maximize the pattern value. The item values are adjusted after the generation of each pattern using a value correction formula. The algorithm is compared with five published algorithms, using 50 groups of benchmark instances. The results indicate that the algorithm is the most efficient in improving solution quality.     

幂零-中心化方法的一个应用

试图丰富谱任意符号模式矩阵类.给出了一个新的含有2n个非零元的符号模式矩阵,并运用幂零-中心化方法与幂零-雅可比方法分别研究了该模式的所有母模式是谱任意的.进一步证明了该模式是极小谱任意的.最后比较了两种证明方法的联系与区别.     

刚性挡墙绕底转动时的非极限主动土压力数值解北大核心CSCD

刚性挡土墙在下部受限时往往呈现绕墙底转动的位移模式,该模式下不同深度土体所处非极限状态不同,给土压力计算带来了困难.在已有研究基础上,推导了适用于绕墙底转动模式下土体强度参数与墙体位移的函数关系;假定墙后土体形成圆弧形土拱,滑裂面为不确定的曲面,将墙后土体按小步长水平分层,构建了绕墙底转动模式下非极限主动土压力的数值迭代格式,给出了该模式下非极限主动土压力的数值计算方法.该数值解既能确定墙后滑裂面的形状,又能计算非极限主动土压力的强度、合力及作用点.将数值解与模型试验结果、现有解析解进行了对比,发现墙后滑裂面为一曲面,该解计算结果与模型试验结果的契合度比现有解析解更高.这提供了刚性挡土墙绕底转动时非极限主动土压力的更精确解答,对这类挡土墙设计具有现实指导价值.     

银行对公存款模型探索

对公款是银行各项存款的重要组成部分，是银行信贷资金的主要来源之一，探索对公存款的活动规律已引起金融部门的高度重视．本文从某市近五年的实际数据出发，通过多元线性回归的方法，建立了对公存款活动规律的数学模型，并对模型进行了各种检验，结果表明模型合格可用，利用它对未来五年的活动规律进行了预测、取得了令人满意的结果．     

The henomeric types of 2-sided patterns in the plane

We extend the classification of pattern types by Grünbaum and Shephard to the 2-sided plane to include patterns having layered or interlaced motifs. Such patterns may have symmetries that turn the plane over. There are 17 infinite families of pattern types for 2-sided rosettes (twelve 1-parameter families and five 2-parameter families), 68 types of 2-sided frieze pattern, and 264 types of 2-sided periodic pattern. The definition of ‘henomeric’ is clarified to ensure that two of the periodic patterns are distinguished.      

Pattern formation and geometry of the manifold

The objective of the present work is to investigate how pattern formation in the Cahn–Hilliard system can be influenced by geometry of the manifold. This is in contrast to control methods in which the physical field is modified and the pattern formation of the original system changes in response to control inputs. The idea begins with the cylindrical manifold symmetry leading to circumferential rolls while the torus manifold can be used to produce and control helical rolls. The next step is to search for a weaker restriction on the geometry of the manifold in order to reduce its dimension. In particular a short amplitude sinusoidal modulation on a flat surface is studied. At the final step a sequential pattern formation is presented.     

On the Index of Necklaces

We consider the following two classes of simple graphs: open necklaces and closed necklaces, consisting of a finite number of cliques of fixed orders arranged in path-like pattern and cycle-like pattern, respectively. In these two classes we determine those graphs whose index (the largest eigenvalue of the adjacency matrix) is maximal.     

Gaps in the base set of primitive nonpowerful sign patterns

For a primitive nonpowerful square sign pattern A, the base of A, denoted by l(A), is the least positive integer l such that every entry of A ^l is #. In this article, we consider the base set of the primitive nonpowerful sign pattern matrices. Some useful results about the bases for the sign pattern matrices are presented there. Some special sign pattern matrices with given bases are characterized and more ‘gaps’ in the base set are shown.     

On rogue wave in the Kundu-DNLS equation

In this paper, the determinant representation of the n-fold Darboux transformation (DT) of the Kundu-DNLS equation is given. Based on our analysis, the soliton solutions, positon solutions and breather solutions of the Kundu-DNLS equation are given explicitly. Further, we also construct the rogue wave solutions which are given by using the Taylor expansion of the breather solution. Particularly, these rogue wave solutions possess several free parameters. With the help of these parameters, these rogue waves constitute several patterns, such as fundamental pattern, triangular pattern, circular pattern.     

Monitoring the stability of the triangular factorization of a sparse matrix

We propose a method for bounding the numerical instability in Gaussian elimination which may result from the use of interchanges calculated from the sparsity pattern alone or calculated for another matrix having the same sparsity pattern. The computational cost of obtaining the bound is small compared with that of the elimination. Also we propose the use of a variant of iterative refinement to estimate the accuracy of the solution obtained.     

A reduction theorem for the linear complementarity problem with a certain patterned matrix

Matrices with a certain pattern are defined and their properties are studied. A reduction theorem is stated and proved which can be used to reduce the size of the linear complementarity problem defined by a matrix with the pattern. The identification of the pattern and the reduction theorem provide a mathematical model for a problem in structural mechanics when a certain symmetry prevails in the structural problem to be analyzed.     

Perceptual-learning machines and the brain

A short review is given of the necessity for, and evidence of, synaptic facilitation as a mechanism which organises the microcircuitry of the brain as a result of experience. Conditional probability statistics described this process and perceptual learning machines illustrate it. A brief review of animal and machine pattern recognition and learning is given. A simple model is described which simulates learning and pattern recognition. It is suggested that certain brain processes and perceptual learning machines are homologous rather than just analogous.     

细长体截面绕流的稳定性及扰动的影响

应用拓扑结构的稳定性理论,分析了细长旋成体截面绕流的结构稳定性．在分析时取极限流线作为流场的内边界,并证明极限流线的鞍点-鞍点连接是拓扑结构稳定的A·D2通过分析发现,由于旋成体背涡的发展,导致截面流场拓扑结构变化,由稳定对称旋涡流态变成不稳定对称旋涡流态．此时流场中存在空间的鞍点-鞍点连接的不稳定拓扑结构,在小扰动下出现分叉,变成稳定非对称旋涡流态,形成非对称背涡．并应用开折理论分析了扰动对流场结构的影响．     

考虑区间值的相对隶属函数与传统模糊分布函数的比较

通过分析比较,揭示了可变集理论中考虑区间值的相对隶属函数与传统的线性模糊分布函数之间的一些区别与联系,即传统的线性模糊分布函数是考虑区间值的相对隶属函数的一些特例,考虑区间值的相对隶属函数在描述模糊现象的模糊性时更具有普适性;同时指出了应用考虑区间值的相对隶属函数时应当注意的问题.     

Pattern definition of the p-efficiency concept

This study revisits the celebrated p-efficiency concept introduced by Prékopa (Z.?Oper. Res. 34:441?C461, 1990) and defines a p-efficient point (pLEP) as a combinatorial pattern. The new definition uses elements from the combinatorial pattern recognition field and is based on the combinatorial pattern framework for stochastic programming problems proposed in Lejeune (Stochastic programming e-print series (SPEPS) 2010-5, 2010). The approach is based on the binarization of the probability distribution, and the generation of a consistent partially defined Boolean function representing the combination (F,p) of the binarized probability distribution F and the enforced probability level p. A combinatorial pattern provides a compact representation of the defining characteristics of a pLEP and opens the door to new methods for the generation of pLEPs. We show that a combinatorial pattern representing a pLEP constitutes a strong and prime pattern and we derive it through the solution of an integer programming problem. Next, we demonstrate that the (finite) collection of pLEPs can be represented as a disjunctive normal form (DNF). We propose a mixed-integer programming formulation allowing for the construction of the DNF that is shown to be prime and irreducible. We illustrate the proposed method on a problem studied by Prékopa (Stochastic programming: handbook in operations research and management science, vol.?10, Elsevier, Amsterdam, 2003).     

Simple block patterns for the two-dimensional cutting problem

This paper presents an algorithm for the unconstrained two-dimensional cutting problem of rectangular pieces. It proposes the simple block (SB) pattern consisting of simple blocks. The SB pattern is defined recursively. Each cut on the stock plate produces just one simple block. A horizontal cut produces a horizontal block with width equal to that of the leftmost piece in the block. A vertical cut produces a vertical block with length equal to that of the bottommost piece in the block. The algorithm generates the optimal SB pattern recursively, and selects optimally the first piece in each block. It uses upper bound to prune some unpromising branches during the searching process. The computational results indicate that the algorithm is highly efficient in improving material utilization, and the computation time is reasonable.