An Algorithm for Finding Global Minimum of Nonlinear Integer Programming

A filled function is proposed by R.Ge[2] for finding a global minimizer of a function of several continuous variables. In [4], an approach for finding a global integer minimizer of nonlinear function using the above filled function is given. Meanwhile a major obstacle is met: if $ρ > 0$ is small, and $||x_I-\overset{*}{x}_I||$ is large, where $x_I$ - an integer point, $\overset{*}{x}_I$ - a current local integer minimizer, then the value of the filled function almost equals zero. Thus it is difficult to recognize the size of the value of the filled function and can not find the global integer minimizer of nonlinear function. In this paper, two new filled functions are proposed for finding global integer minimizer of nonlinear function, and the new filled function improves some properties of the filled function proposed by R. Ge [2].Some numerical results are given, which indicate the new filled function (4.1) to find global integer minimizer of nonlinear function is efficient.     

Multi-Box Splines

We construct local generators, comprising r functions, for refinable spaces of bivariate C^n-1 spline functions of degree n on meshes comprising all lines through points of the integer lattice in the directions of n + r + 1 pairwise linearly independent vectors with integer components. The generators are characterised by their Fourier transforms. Their shifts are shown to form a Riesz basis if and only if at most r lines in the mesh intersect other than in the integer lattice, which can occur for n ≤ 2r - 1. The symmetry of these generators is studied and examples are given.     

Cyclic Schedule for Apron Services

This paper presents the underlying ideas and methodology of constructing a cyclic duty line to meet economically the daily staffing requirements for apron crews. The focus is on the formulation of basic patterns (the building blocks of the duty line) for the purpose of allocating days off, and on the assignment of shifts to working days on this duty line. The pattern determination is formulated as an integer programming problem whose special structure affords a quick and efficient solution. A procedure is provided for shift assignment. An illustrative example is also included.     

Poisson thickening

Let × be a Poisson point process of intensity λ on the real line. A thickening of it is a (deterministic) measurable function f such that X∪f(X) is a Poisson point process of intensity λ′ where λ′ > λ. An equivariant thickening is a thickening which commutes with all shifts of the line. We show that a thickening exists but an equivariant thickening does not. We prove similar results for thickenings which commute only with integer shifts and in the discrete and multi-dimensional settings. This answers 3 questions of Holroyd, Lyons and Soo. We briefly consider also a much more general setup in which we ask for the existence of a deterministic coupling satisfying a relation between two probability measures. We present a conjectured sufficient condition for the existence of such couplings.     

Riesz Bases in Subspaces of L2 (R+ )

In a recent investigation [8] concerning the asymptotic behavior of Gram—Schmidt orthonormalization procedure applied to the nonnegative integer shifts of a given function, the problem of determining whether or not such functions form a Riesz system in arose. In this paper, we provide a sufficient condition to determine whether the nonnegative translates form a Riesz system on . This result is applied to identify a large class of functions for which very general translates enjoy the Riesz basis property in . August 5, 1998. Date revised: August 25, 1999. Date accepted: January 11, 2000.     

On the convergence of orthorecursive expansions in nonorthogonal wavelets

The present paper is concerned with orthorecursive expansions which are generalizations of orthogonal series to families of nonorthogonal wavelets, binary contractions and integer shifts of a given function φ. It is established that, under certain not too rigid constraints on the function φ, the expansion for any function f ∈ L ²(?) converges to f in L ²(?). Such an expansion method is stable with respect to errors in the calculation of the coefficients. The results admit a generalization to the n-dimensional case.     

一个包含伪Smarandache函数及其对偶函数的方程

研究一个包含伪Smarandache函数及其对偶函数方程的可解性,利用初等及组合方法给出了该方程的一系列正整数解,并证明了该方程的所有奇数解必为奇素数p（≥5）的方幂.     

Real roots of univariate polynomials and straight line programs

We give a new proof of the NP-hardness of deciding the existence of real roots of an integer univariate polynomial encoded by a straight line program based on certain properties of the Tchebychev polynomials. These techniques allow us to prove some new NP-hardness results related to real root approximation for polynomials given by straight line programs.     

一般整数规划中有效不等式的同步升维

有效不等式在整数规划的定界研究中具有重要的意义.研究了一般整数规划问题的有效不等式的升维方法,引入超加性函数给出同步升维的条件,并给出有效不等式的同步升维的具体方法,算例表明本文提出的方法是有效的.     

The value function of an integer program

We consider integer programs in which the objective function and constraint matrix are fixed while the right-hand side varies. The value function gives, for each feasible right-hand side, the criterion value of the optimal solution. We provide a precise characterization of the closed-form expression for any value function. The class of Gomory functions consists of those functions constructed from linear functions by taking maximums, sums, non-negative multiples, and ceiling (i.e., next highest integer) operations. The class of Gomory functions is identified with the class of all possible value functions by the following results: (1) for any Gomory functiong, there is an integer program which is feasible for all integer vectorsv and hasg as value function; (2) for any integer program, there is a Gomory functiong which is the value function for that program (for all feasible right-hand sides); (3) for any integer program there is a Gomory functionf such thatf(v)≤0 if and only ifv is a feasible right-hand side. Applications of (1)–(3) are also given.     

Distributionally robust simple integer recourse

The simple integer recourse (SIR) function of a decision variable is the expectation of the integer round-up of the shortage/surplus between a random variable with a known distribution and the decision variable. It is the integer analogue of the simple (continuous) recourse function in two-stage stochastic linear programming. Structural properties and approximations of SIR functions have been extensively studied in the seminal works of van der Vlerk and coauthors. We study a distributionally robust SIR function (DR-SIR) that considers the worst-case expectation over a given family of distributions. Under the assumption that the distribution family is specified by its mean and support, we derive a closed form analytical expression for the DR-SIR function. We also show that this nonconvex DR-SIR function can be represented using a mixed-integer second-order conic program.     

Cutting plane algorithms for the inverse mixed integer linear programming problem

We present cutting plane algorithms for the inverse mixed integer linear programming problem (InvMILP), which is to minimally perturb the objective function of a mixed integer linear program in order to make a given feasible solution optimal.     

关于欧拉函数方程？（？（x））=2t的可解性

对任意的正整数 n,函数？（n）为著名的 Euler 函数,即在序列1,2,···, n 中与n 互质的整数的个数。本文利用初等方法研究了方程？（？（x））的可解性,并给出了该方程的全部正整数解。     

整数规划的广义填充函数算法

文[9,10]设计了直接求整数规划问题近似解的填充函数算法,但其所利用的文[2,3]的填充函数均带有参数,需要在算法过程中逐步调节。本文建立整数规划的广义填充函数的定义,说明了文[9,10]所利用的填充函数是整数规划问题的广义填充函数,并构造了一类不带参数的广义填充函数。进而本文设计了整数规划的一类不带参数的广义填充函数算法,数值试验表明算法是有效的。     

An integer linear programming-based heuristic for scheduling heterogeneous,part-time service employees

Scheduling of heterogeneous, part-time, service employees with limited availability is especially challenging because employees have different availability and skills, and work different total work hours in a planning period, e.g., a week. The constraints typically are to meet employee requirements during each hour in a planning period with shifts which have a minimum & maximum length, and do not exceed 5 work days per week for each employee. The objectives typically are to minimize over staffing and to meet the target total work hours for each employee during the planning period. We decompose this problem into (a) determining good shifts and then (b) assigning the good shifts to employees, and use a set of small integer linear programs to solve each part. We apply this method to the data given in a reference paper and compare our results. Also, several random problems are generated and solved to verify the robustness of our solution method.     

Relations between the support of a compactly supported function and the exponential-polynomials spanned by its integer translates

The interrelation between the shape of the support of a compactly supported function and the space of all exponential-polynomials spanned by its integer translates is examined. The results obtained are in terms of the behavior of these exponential-polynomials on certain finite subsets ofZ ^s , which are determined by the support of the given function. Several applications are discussed. Among these is the construction of quasi-interpolants of minimal support and the construction of a piecewise-polynomial whose integer translates span a polynomial space which is not scale-invariant. As to polynomial box splines, it is proved here that in many cases a polynomial box spline admits a certain optimality condition concerning the space of the total degree polynomials spanned by its integer translates: This space is maximal compared with the spaces corresponding to other functions with the same supportCommunicated by Klaus Höllig.     

Some exact solutions to Stefan problems with fractional differential equations

Some exact solutions to the first, second and extended Stefan problems with fractional time derivative described in the Caputo sense are given by means of fractional Green's function and Wright function in this paper. By the aid of simple calculations, many results of differential equations of integer order can be obtained as special cases of the results given by this paper.     

Critical degenerate inequalities¶on the Heisenberg group

Necessary and sufficient conditions are given that answer the following questions: When does an integer valued (real valued) g-additive function have a limit distribution modulo an integer (modulo 1)? When are the limit distributions continuous or uniform? When is a complex valued g-additive function almost periodic? Received: 6 February 2001 / Revised version: 30 May 2001     

A critique of fractional age assumptions

Published mortality tables are usually calibrated to show the survival function of the age at death distribution at exact integer ages. Actuaries make fractional age assumptions when valuing payments that are not restricted to integer ages. A fractional age assumption is essentially an interpolation between integer age values which are accepted as given.Three fractional age assumptions have been widely used by actuaries. These are the uniform distribution of death (UDD) assumption, the constant force assumption and the hyperbolic or Balducci assumption. Under all three assumptions, the interpolated values of the survival function between two consecutive ages depend only on the survival function at those ages. While this has the advantage of simplicity, all three assumptions result in force of mortality and probability density functions with implausible discontinuities at integer ages.In this paper, we examine some families of fractional age assumptions that can be used to correct this problem. To help in choosing specific fractional age assumptions and in comparing different sets of assumptions, we present an optimality criterion based on the length of the probability density function over the range of the mortality table.     

关于方程φ(abc)=2(φ(a)+φ(b)+φ(c))

设n为任意正整数,φ(n)是Euler函数.主要研究了方程φ(abc)=2(φ(a)+φ(b)+φ(c))的可解性问题,利用数论中的理论和方法,获得了该方程的所有正整数解.