Primal cutting plane algorithms revisited

Dual fractional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful branch-and-cut method. It is rather less well-known that various primal cutting plane algorithms were developed in the 1960s, for example by Young. In a primal algorithm, the main role of the cutting planes is to enable a feasible solution to the original problem to be improved. Research on these algorithms has been almost non-existent.  In this paper we argue for a re-examination of these primal methods. We describe a new primal algorithm for pure 0-1 problems based on strong valid inequalities and give some encouraging computational results. Possible extensions to the case of general mixed-integer programs are also discussed.     

NA列加权乘积和的完全收敛性

本文讨论了NA和几类加权部分和及加权乘积和的完全收敛性，其中部分结果要优于iid列的已知结论。     

Using rank-1 lift-and-project closures to generate cuts for 0–1 MIPs, a computational investigation

Various techniques for building relaxations and generating valid inequalities for pure or mixed integer programming problems without special structure are reviewed and compared computationally. Besides classical techniques such as Gomory cuts, Mixed Integer Rounding cuts, lift-and-project and reformulation–linearization techniques, a new variant is also investigated: the use of the relaxation corresponding to the intersection of simple disjunction polyhedra (i.e. the so-called elementary closure of lift-and-project cuts). Systematic comparative computational results are reported on series of test problems including multidimensional knapsack problems (MKP) and MIPLIB test problems. From the results obtained, the relaxation based on the elementary closure of lift-and-project cuts appears to be one of the most promising.     

关于NA情况下重对数律收敛速度的一般形式

研究了NA序列重对数律收敛速度的一般形式，把Davis和Gut的结果推广到了NA的情形，并使梁汉营等人关于对数律一个结果成为特例；作为推论，得到了关于NA序列重对数律收敛速度的充分条件．     

凹整数规划的分枝定界解法

凹整数规划是一类重要的非线性整数规划问题，也是在经济和管理中有着广泛应用的最优化问题．本文主要研究用分枝定界方法求解凹整数规划问题，这一方法的基本思想是对目标函数进行线性下逼近，然后用乘子搜索法求解连续松弛问题．数值结果表明，用这种分枝定界方法求解凹整数规划是有效的．     

On the counting function of the lattice profile of periodic sequences

The lattice profile analyzes the intrinsic structure of pseudorandom number sequences with applications in Monte Carlo methods and cryptology. In this paper, using the discrete Fourier transform for periodic sequences and the relation between the lattice profile and the linear complexity, we give general formulas for the expected value, variance, and counting function of the lattice profile of periodic sequences with fixed period. Moreover, we determine in a more explicit form the expected value, variance, and counting function of the lattice profile of periodic sequences for special values of the period.     

Some alternating sums of Lucas numbers

We consider alternating sums of squares of odd and even terms of the Lucas sequence and alternating sums of their products. These alternating sums have nice representations as products of appropriate Fibonacci and Lucas numbers.     

Two Convergence Problems for Monotone Sequences

Eight measures of rate of convergence of monotone sequences of real numbers have been proposed and discussed in a paper by Beyer, Ebanks, and Qualls (Acta Appl. Math. 20 (1990), 267–284). These rates arose in discussions of dynamical systems. In the comparisons of these rates, two problems remained. A complete answer is given to one of the problems and a partial answer is given to the other problem.     

Searching for extensible Korobov rules

Extensible lattice sequences have been proposed and studied in [F.J. Hickernell, H.S. Hong, Computing multivariate normal probabilities using rank-1 lattice sequences, in: G.H. Golub, S.H. Lui, F.T. Luk, R.J. Plemmons (Eds.), Proceedings of the Workshop on Scientific Computing (Hong Kong), Singapore, Springer, Berlin, 1997, pp. 209–215; F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138; F.J. Hickernell, H.Niederreiter, The existence of good extensible rank-1 lattices, J. Complexity 19 (2003) 286–300]. For the special case of extensible Korobov sequences, parameters can be found in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C.Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138]. The searches made to obtain these parameters were based on quality measures that look at several projections of the lattice. Because it is often the case in practice that low-dimensional projections are very important, it is of interest to find parameters for these sequences based on measures that look more closely at these projections. In this paper, we prove the existence of “good” extensible Korobov rules with respect to a quality measure that considers two-dimensional projections. We also report results of experiments made on different problems where the newly obtained parameters compare favorably with those given in [F.J. Hickernell, H.S. Hong, P. L’Ecuyer, C. Lemieux, Extensible lattice sequences for quasi-Monte Carlo quadrature, SIAM J. Sci. Comput. 22 (2001) 1117–1138].