关于P.Crawleg和R.P.Dilworth的公开问题

本文讨论了P.Crawleg和R.P.Dilworth提出的一个公开问题,研究了偏序集的带有固定点的保序映射,并且给出了若干充分或必要条件,使得一个偏序集的每一个保序映射都至少有一个固定点。     

求解带有三元函数的广义半均衡问题的预测校正法

本文介绍一类新的均衡问题--带有三元函数的广义半均衡问题.借助于辅助原理法提出了求解此类问题的一个三步预测-校正迭代法,并分析了算法的收敛性.     

关于双随机循环矩阵中的素元(英文)

非负矩阵中的素元分类问题在控制和系统论中有重要的应用.本文将研究由G.Picci等所提出的关于双随机循环矩阵中素元的一个问题和一个猜想,得到了一个判别具有位数5的n阶双随机循环矩阵不是素元的充要条件,给出了猜想成立的一些充分条件.     

关于有限p-群特征标值的一个注记(英文)

本文考虑了Yakov berkovich提出的一个研究问题.利用特征标理论的初等技巧,得到每个不可约特征标至多有p个不同值的有限p-群一定是初等交换p-群,这部分回答了Yakov berkovich的研究问题.     

关于整函数和亚纯函数的渐近值

本文主要是肯定地回答了Haymsn在1964年提出的关于整函数和亚纯函数的渐近值方面的四个问题.对其中的一个问题即引言中的问题4)的解决,我们附加了整函数的级为有穷的条件.     

求解带组换装时间单机调度问题的禁忌搜索算法

以包头某钢铁线材企业生产实际调度问题为背景,研究了一类带组换装时间的单机调度问题.由于该问题是NP难的,本文提出了一类适合该问题的禁忌搜索算法.此外,本文将问题性质引入了禁忌搜索算法以进一步提高算法寻优性能,降低算法运行时间.本文提出的算法在随机问题和实际问题上均进行了测试,实验结果表明,本文提出的算法能在不到10秒的时间内获得实际问题的一个近似最优解.     

求线性多乘积规划问题的分支定界算法（英文）

为求解线性多乘积规划问题(LMP),本文提出一个新的全局优化算法.首先,利用二阶导数信息,给出了一个新的线性化松弛方法.其次,为了改进算法的收敛速度,提出一个区域删除技巧.最后,为求解LMP,设计了一个分支定界算法.理论上证明了算法的收敛性.数值实验结果显示本文方法是有效可行的.     

求线性二层规划∈-全局最优解的一种方法

本文研究了线性二层规划问题.利用下层问题的KKT最优性条件将其转化为一个具有互补约束的数学规划问题,提出了一种新的求解方法.该方法仅仅需要求解若干个双线性规划问题,便可以获得原问题的∈-全局最优解.最后,通过一个算例说明了所提出方法的可行性.     

矿藏分布型函数描述的特殊性及其插值模型

矿藏描述所提出的插值问题有二个特点,一是数据分布通常是不规则的;二是数据可能只是被讨论函数的一个泛函,所以一般的插值方法都有所不足.本文提出的插值模型能较好地处理这个问题.     

由数学问题2268引发的研究

供题人柳冉同学给出的解答技巧性较强,过程曲折精彩.崔志荣老师在文[2]中从揭示问题的本质出发给出了另外一种解答,很有启发性,并在文末提出了2个猜想.黄盛清老师在文[3]中另辟蹊径,从方程的角度给出了又一个精彩解答,并在文末再次提出了能否将(1)式一般化的问题.本文首先给出一个更为直接的证明,然后将(1)式一般化,从而也证明了文[2]提出的猜想.     

Automatic computation of partial derivatives and rounding error estimates with applications to large-scale systems of nonlinear equations

Recently, a new approach has been proposed to efficiently compute the accurate values of partial derivatives of a function or functions, and simultaneously to estimate the rounding errors in the computed function values. In this paper the use of the method in the solution of nonlinear equations is investigated.The method makes use of the computational graph and, when applied to the evaluation of a function, traverses it from the top ( = the function node) down to the bottom ( = the input variable nodes). A remarkable analogy is observed between the partial derivatives and the shortest paths on the computational graph. The top-down traversing on the computational graph has the following advantages over the existing algorithms using the bottom-up traversing: (1) The gradient of a function can be computed within the same complexity as that of the evaluation of the function alone (the complexity being independent of the number of input variables); (2) A fairly sharp estimate of the rounding error in the function evaluation is obtained, on the basis of which a computationally meaningful norm may be introduced in the space of residuals to afford a convergence criterion for an iterative method of solving the system of nonlinear equations. As an example, a system of nonlinear equations with 108 variables for a distillation tower of a chemical plant is numerically analyzed in detail. It is shown that by the use of the proposed method we could satisfactorily resolve two main problems encountered in computing a numerical solution of the system of nonlinear equations, i.e., how to compute the accurate Jacobian matrix and when we should stop the iteration.     

Parallel multi-frontal solver for p adaptive finite element modeling of multi-physics computational problems

The paper presents a parallel direct solver for multi-physics problems. The solver is dedicated for solving problems resulting from adaptive finite element method computations. The concept of finite element is actually replaced by the concept of the node. The computational mesh consists of several nodes, related to element vertices, edges, faces and interiors. The ordering of unknowns in the solver is performed on the level of nodes. The concept of the node can be efficiently utilized in order to recognize unknowns that can be eliminated at a given node of the elimination tree. The solver is tested on the exemplary three-dimensional multi-physics problem involving the computations of the linear acoustics coupled with linear elasticity. The three-dimensional tetrahedral mesh generation and the solver algorithm are modeled by using graph grammar formalism. The execution time and the memory usage of the solver are compared with the MUMPS solver.     

Linear arrangement problems on recursively partitioned graphs

We analyze the complexity of the restrictions of linear arrangement problems that are obtained if the legal permutations of the nodes are restricted to those that can be obtained by orderings of a binary tree structuring the nodes of the graph, the so-called p-tree. These versions of the linear arrangement problems occur in several places in current circuit layout systems. There the p-tree is the result of a recursive partitioning process of the graph. We show that the MINCUT LINEAR ARRANGEMENT problem and the OPTIMAL LINEAR ARRANGEMENT problem can be solved in polynomial time, if the p-tree is balanced. All other versions of the linear arrangement problems we analyzed are NP-complete.     

Bi-Objective Median Subtree Location Problems

A number of network design problems can be built on the following premise: given an undirected tree network, T, with node set, V, identify a single subtree, t, containing nodes, v, so that the subtree is located optimally with respect to the remaining, subset of unconnected nodes {V–v}. Distances between unconnected nodes and nodes in the subtree t can be defined on paths that are restricted to lie in the larger tree T (the restricted case), or can be defined on paths in an auxiliary complete graph G (the unrestricted case). The unrestricted case represents a class of problems that is not explicitly recognized in the literature, which is of intermediate complexity relative to the widely studied restricted case, and the general problem in which the underlying graph is general. This paper presents the Median Subtree Location Problem (MSLP), formulated as a bicriterion problem that trades off the cost of a subtree, t, against the population-weighted travel distance from the unconnected nodes to nodes on the subtree where both objectives are to be minimized. Integer programs were formulated for the travel restricted and travel unrestricted cases and were tested using linear programming and branch and bound to resolve fractions. Tradeoff curves between cost and travel burden were developed for sample networks.     

Influence diagrams with super value nodes involving imprecise information

The concept of super value nodes was established to allow dynamic programming to be performed within the theory of influence diagrams and to reduce the computational complexity in solving problems by means of influence diagrams. This paper is focused on how influence diagrams with super value nodes are affected by the presence of imprecise information. We analyze how to reduce the complexity when evaluating an influence diagram in this framework by modelling these kinds of nodes and random magnitudes in terms of fuzzy random variables. Finally, an applied example of the theoretical results is developed.     

Graphs as navigational infrastructure for high dimensional data spaces

We propose using graph theoretic results to develop an infrastructure that tracks movement from a display of one set of variables to another. The illustrative example throughout is the real-time morphing of one scatterplot into another. Hurley and Oldford (J Comput Graph Stat 2010) made extensive use of the graph having variables as nodes and edges indicating a paired relationship between them. The present paper introduces several new graphs derivable from this one whose traversals can be described as particular movements through high dimensional spaces. These are connected to known results in graph theory and the graph theoretic results applied to the problem of visualizing high-dimensional data.     

A framework and a mean-field algorithm for the local control of spatial processes

The Markov Decision Process (MDP) framework is a tool for the efficient modelling and solving of sequential decision-making problems under uncertainty. However, it reaches its limits when state and action spaces are large, as can happen for spatially explicit decision problems. Factored MDPs and dedicated solution algorithms have been introduced to deal with large factored state spaces. But the case of large action spaces remains an issue. In this article, we define graph-based Markov Decision Processes (GMDPs), a particular Factored MDP framework which exploits the factorization of the state space and the action space of a decision problem. Both spaces are assumed to have the same dimension. Transition probabilities and rewards are factored according to a single graph structure, where nodes represent pairs of state/decision variables of the problem. The complexity of this representation grows only linearly with the size of the graph, whereas the complexity of exact resolution grows exponentially. We propose an approximate solution algorithm exploiting the structure of a GMDP and whose complexity only grows quadratically with the size of the graph and exponentially with the maximum number of neighbours of any node. This algorithm, referred to as MF-API, belongs to the family of Approximate Policy Iteration (API) algorithms. It relies on a mean-field approximation of the value function of a policy and on a search limited to the suboptimal set of local policies. We compare it, in terms of performance, with two state-of-the-art algorithms for Factored MDPs: SPUDD and Approximate Linear Programming (ALP). Our experiments show that SPUDD is not generally applicable to solving GMDPs, due to the size of the action space we want to tackle. On the other hand, ALP can be adapted to solve GMDPs. We show that ALP is faster than MF-API and provides solutions of similar quality for most problems. However, for some problems MF-API provides significantly better policies, and in all cases provides a better approximation of the value function of approximate policies. These promising results show that the GMDP model offers a convenient framework for modelling and solving a large range of spatial and structured planning problems, that can arise in many different domains where processes are managed over networks: natural resources, agriculture, computer networks, etc.     

Global Optimization: Local Minima and Transition Points

We consider the minimization of smooth functions of the Euclidean space with a finite number of stationary points having moderate asymptotic behavior at infinity. The crucial role of transition points of first order (i.e., saddle points of index 1) is emphasized. It is shown that (generically) any two local minima can be connected via an alternating sequence of local minima and transition points of first order. In particular, the graph with local minima as its nodes and first order transition points representing the edges turns out to be connected (Theorem A). On the other hand, any connected (finite) graph can be realized in the above sense by means of a smooth function of three variables having a minimal number of stationary points (Theorem B).     

Solving Graph Coloring Problems with the Douglas-Rachford Algorithm

We present the Douglas-Rachford algorithm as a successful heuristic for solving graph coloring problems. Given a set of colors, these types of problems consist in assigning a color to each node of a graph, in such a way that every pair of adjacent nodes are assigned with different colors. We formulate the graph coloring problem as an appropriate feasibility problem that can be effectively solved by the Douglas-Rachford algorithm, despite the nonconvexity arising from the combinatorial nature of the problem. Different modifications of the graph coloring problem and applications are also presented. The good performance of the method is shown in various computational experiments.     

Star partitions on graphs

Given an undirected graph, a star partition is a partition of the nodes into subsets with at least two nodes so that the subgraph induced by each subset has a spanning star. Star partitions are related to well-known problems concerning domination in graphs and edge covering. We focus on the Constrained Star Partition Problem (CSP) that asks for finding a star partition of given cardinality. The problem is new and presents interesting peculiarities. We explore the relation between the cardinalities of star partitions and domatic bipartitions, showing that there are star partitions of any cardinality between minimum and maximum values, and that a similar but weaker result holds for domatic bipartitions. We study the computational complexity of different versions of star partition and domatic bipartition problems, proving that most of them, in particular CSP, constrained domatic bipartition and balanced domatic bipartition, are NP-complete. We also show that star partition problems are polynomial on trees and, more generally, on bounded treewidth graphs. We introduce an integer linear programming formulation that defines a polytope containing all the star partitions of a graph, showing that its vertices have only integral components for trees, which implies that linear programming can be used to solve weighted star partition problems on trees.