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

Additive problems for integers with a given number of prime divisors

The asymptotics of sums of the form Στ(|bn−a|) (summation overn<N, ω(n)=k) is studied, whereω(n) is the number of distinct prime divisors ofn, andτ(n) is the number of all divisors. Translated fromMatematicheskie Zametki, Vol. 63, No. 5, pp. 749–762, May, 1998. In conclusion, the author wishes to express his gratitude to Professor N. M. Timofeev for valuable advice. This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00502.     

Optimal Control of the Obstacle for an Elliptic Variational Inequality

An optimal control problem for an elliptic obstacle variational inequality is considered. The obstacle is taken to be the control and the solution to the obstacle problem is taken to be the state. The goal is to find the optimal obstacle from H ¹ ₀ (Ω) so that the state is close to the desired profile while the H ¹ (Ω) norm of the obstacle is not too large. Existence, uniqueness, and regularity as well as some characterizations of the optimal pairs are established. Accepted 11 September 1996     

A Hybrid Smoothing Method for Mixed Nonlinear Complementarity Problems

In this paper, we describe a new, integral-based smoothing method for solving the mixed nonlinear complementarity problem (MNCP). This approach is based on recasting MNCP as finding the zero of a nonsmooth system and then generating iterates via two types of smooth approximations to this system. Under weak regularity conditions, we establish that the sequence of iterates converges to a solution if the limit point of this sequence is regular. In addition, we show that the rate is Q-linear, Q-superlinear, or Q-quadratic depending on the level of inexactness in the subproblem calculations and we make use of the inexact Newton theory of Dembo, Eisenstat, and Steihaug. Lastly, we demonstrate the viability of the proposed method by presenting the results of numerical tests on a variety of complementarity problems.     

On Three-Dimensional Dynamic Problems of Generalized Thermoelasticity

Lord–;Shulman's system of partial differential equations of generalized thermoelasticity [1] is considered, in which the finite velocity of heat propagation is taken into account by introducing a relaxation time constant. General aspects of the theory of boundary value and initial-boundary value problems and representation of solutions by series and quadratures are considered using the method of a potential.     

自反Banach空间中的相补问题

在自反Banach空间中证明了相补问题解的存在性定理，改进了[1]中的一个主要结果．     

指派问题匈牙利解法的又两个注记

本文就指派问题匈牙利解法中的一些方法提出两个注记，且为此提供一个较为简单的解法。     

具线性退化特征场对角型方程组Goursat问题的奇性形成机制

For an inhomogeneous quasilinear hyperbolic system of diagonal form, under the assumptions that the system is linearly degenerate and the C^1 norm of the boundary data is bounded, we show that the mechanism of the formation of singularities of C^1 classical solution to the Goursat problem with C^1 compatibility conditions at the origin must be an ODE type. The similar result is also obtained for the weakly discontinuous solution with C^0 compatibility conditions at the origin.     

带有p-Laplacian算子的高阶微分方程组边值问题多个正解的存在性

利用五个泛函的不动点定理,证明了带有p-Laplacian算子的高阶微分方程组边值问题多组正解的存在性.其中n≥2,Φ_p(s)=|s|~(p~(-2))s,p>1.