Test sets of integer programs

This article is a survey about recent developments in the area of test sets of families of linear integer programs. Test sets are finite subsets of the integer lattice that allow to improve any given feasible non-optimal point of an integer program by one element in the set. There are various possible ways of defining test sets depending on the view that one takes: theGraver test set is naturally derived from a study of the integral vectors in cones; theScarf test set (neighbors of the origin) is strongly connected to the study of lattice point free convex bodies; the so-calledreduced Gröbner basis of an integer program is obtained from a study of generators of polynomial ideals. This explains why the study of test sets connects various branches of mathematics. We introduce in this paper these three kinds of test sets and discuss relations between them. We also illustrate on various examples such as the minimum cost flow problem, the knapsack problem and the matroid optimization problem how these test sets may be interpreted combinatorially. From the viewpoint of integer programming a major interest in test sets is their relation to the augmentation problem. This is discussed here in detail. In particular, we derive a complexity result of the augmentation problem, we discuss an algorithm for solving the augmentation problem by computing the Graver test set and show that, in the special case of an integer knapsack problem with 3 coefficients, the augmentation problem can be solved in polynomial time.Supported by a Gerhard-Hess-Forschungsförderpreis of the German Science Foundation (DFG).     

The Kolkata Paise Restaurant problem and resource utilization

We study the dynamics of the “Kolkata Paise Restaurant problem”. The problem is the following: In each period, N agents have to choose between N restaurants. Agents have a common ranking of the restaurants. Restaurants can only serve one customer. When more than one customer arrives at the same restaurant, one customer is chosen at random and is served; the others do not get the service. We first introduce the one-shot versions of the Kolkata Paise Restaurant problem which we call one-shot KPR games. We then study the dynamics of the Kolkata Paise Restaurant problem (which is a repeated game version of any given one shot KPR game) for large N. For statistical analysis, we explore the long time steady state behavior. In many such models with myopic agents we get under-utilization of resources, that is, we get a lower aggregate payoff compared to the social optimum. We study a number of myopic strategies, focusing on the average occupation fraction of restaurants.     

基于SRLG约束和资源共享的交迭段保护机制研究

通过对共享风险链路组约束机制和交迭段保护机制的分析,将两者相结合并根据工作和保护路径分别采用动态链路权重调整,提出了一种基于共享风险链路组不相关的交迭段共享保护算法.交迭段共享保护算法在共享风险链路组不相关的约束条件下,为整个工作路由提供了多个交迭的保护段,并给出了一种能够合理有效选择这些交迭保护段的方法.对交迭段共享保护算法的分析和仿真结果表明,与以往保护算法相比,交迭段共享保护算法不但大大提高了网络连接的可靠性,而且还通过不同交迭保护段间资源的合理共享,有效地提高了网络资源的利用率.     

Optimal server resource reservation policies for priority classes of users under cyclic non-homogeneous markov modeling

Resource availability optimization is studied on a server–client system where different users are partitioned into priority classes. The aim is to provide higher resource availability according to the priority of each class. For this purpose, resource reservation is modeled by a homogeneous continuous time Markov chain (CTMC), but also by a cyclic non-homogeneous Markov chain (CNHMC) as there is a cyclic behavior of the users’ requests for resources. The contribution of the work presented consists in the formulation of a multiobjective optimization problem for both the above cases that aims to determine the optimal resource reservation policy providing higher levels of resource availability for all classes. The optimization problem is solved either with known methods or with a proposed kind of heuristic algorithm. Finally, explicit generalized approximate inverse preconditioning methods are adopted for solving efficiently sparse linear systems that are derived, in order to compute resource availability.     

A fast Petrov–Galerkin method for solving the generalized airfoil equation

In this paper we develop a fast Petrov–Galerkin method for solving the generalized airfoil equation using the Chebyshev polynomials. The conventional method for solving this equation leads to a linear system with a dense coefficient matrix. When the order of the linear system is large, the computational complexity for solving the corresponding linear system is huge. For this we propose the matrix truncation strategy, which compresses the dense coefficient matrix into a sparse matrix. We prove that the truncated method preserves the optimal order of the approximate solution for the conventional method. Moreover, we solve the truncated equation using the multilevel augmentation method. The computational complexity for solving this truncated linear system is estimated to be linear up to a logarithmic factor.     

Coalitional strategy-proofness and resource monotonicity for house allocation problems

We consider the problem of allocating houses to agents when monetary compensations are not allowed. We present a simple and independent proof of a result due to Ehlers and Klaus (Int J Game Theory 32:545–560, 2004) that characterizes the class of rules satisfying efficiency, strategy-proofness, resource monotonicity and nonbossiness. I am very much indebted to William Thomson for his invaluable suggestions.     

A selective view of stochastic inference and modeling problems in nanoscale biophysics

Advances in nanotechnology enable scientists for the first time to study biological processes on a nanoscale molecule-by-molecule basis. They also raise challenges and opportunities for statisticians and applied probabilists. To exemplify the stochastic inference and modeling problems in the field, this paper discusses a few selected cases, ranging from likelihood inference, Bayesian data augmentation, and semi- and non-parametric inference of nanometric biochemical systems to the utilization of stochastic integro-differential equations and stochastic networks to model single-molecule biophysical processes. We discuss the statistical and probabilistic issues as well as the biophysical motivation and physical meaning behind the problems, emphasizing the analysis and modeling of real experimental data. This work was supported by the United States National Science Fundation Career Award (Grant No. DMS-0449204)     

高超声速可压缩流中粗糙壁热流研究

用计算流体力学（CFD）数值模拟和理论方法对高超声速可压缩湍流中粗糙壁面热增量进行研究. 着重考虑粗糙单元密度和粗糙单元形状对粗糙表面热流的影响. 结果表明： ①粗糙单元密度变化时, CFD数值方法计算所得的粗糙单元等效热流随着粗糙单元密度的降低而增加, 理论方法预测结果的规律随方法不同而不同;②在相同粗糙单元密度和高度时,如果粗糙单元形状改变,CFD计算结果也随之发生改变. 理论预测方法所得结果不发生变化.