Generalized Nonlinear Lagrangian Formulation for Bounded Integer Programming

Several nonlinear Lagrangian formulations have been recently proposed for bounded integer programming problems. While possessing an asymptotic strong duality property, these formulations offer a success guarantee for the identification of an optimal primal solution via a dual search. Investigating common features of nonlinear Lagrangian formulations in constructing a nonlinear support for nonconvex piecewise constant perturbation function, this paper proposes a generalized nonlinear Lagrangian formulation of which many existing nonlinear Lagrangian formulations become special cases.     

Scheduling Personal Finances via Integer Programming

Personal financial planning is the preparation of a series of ongoing target-oriented decisions concerning personal assets, incomes and expenses. An important task of personal financial planning is the generation of a financial schedule defining suitable times for realization of the expenses and incomes at a given point of time. We describe an integer programming model and algorithms for scheduling personal finances via the examination of a linear combination of the weighted objectives to be maximized. Solving the integer programming problem provides an optimal financial schedule which reflects an individual’s goals and preferences. We describe a worst-case scenario for a personal financial schedule with respect to possible variation of credit and interest rates. Computational results demonstrate the largest problems that are solvable via the algorithm based on schedule enumeration which is needed for a stability analysis.     

有界变量线性规划的一种简易解法

本文在[1]的基础上，较系统地叙述了有界变量线性规划一种简易解法的基本思路、方法步骤、理论分析和应用举例。指出，因变量有界所引起的种种麻烦在这里通过单纯形表的小小变动便加以解决了。     

A Note on Reducing the Number of Variables in Integer Programming Problems

A necessary and sufficient condition for identification of dominatedcolumns, which correspond to one type of redundant integer variables,in the matrix of a general Integer Programming problem, isderived. The given condition extends our recent work on eliminatingdominated integer variables in Knapsack problems, and revises arecently published procedure for reducing the number of variables ingeneral Integer Programming problems given in the literature. Areport on computational experiments for one class of large scaleKnapsack problems, illustrating the function of this approach, isincluded.     

Hyperspheric Integer Programming

This paper develops an efficient method for finding the optimal solution to linear mathematical programs on 0–1 variables. It is shown that the lattice (0–1) points satisfying some linear constraint of dimension n can equally be represented by those lying in a hypersphere of the same dimension. The lattice points satisfying two linear constraints can be represented by a hypersphere which contains the intersection of the hyperspheres of the two constraints. The method for finding the optimal solution consists of enumerating lattice points which are close to the center of the hypersphere corresponding to the constraints. As soon as a better value of the objective function has been found, than some lower bound, we find a new hypersphere which contains the lattice points of the constraints at which the objective function remains higher than the best known value. We continue in this manner until we have at some stage enumerated all lattice points within a given hypersphere and found none which give a better value.     

The Elimination of Integer Variables

It is pointed out that the projection of a Linear Programme (LP) into a lower dimension still results in an LP. For an Integer Programme (IP) this is not generally the case. Circumstances in which the projection (after eliminating integer variables) is still an IP are given.     

Survey of Integer Programming

The paper surveys the progress that has been made with the problem of solving linear programming problems when some or all variables are required to take integer values. It is pointed out that there are now four distinct approaches capable of solving real problems of this type: cutting plane methods, primal methods, branch and bound methods, and partial enumeration methods. Each approach is explained briefly. A detailed bibliography is attached.     

Integer Programming Duality in Multiple Objective Programming

The weighted sums approach for linear and convex multiple criteria optimization is well studied. The weights determine a linear function of the criteria approximating a decision makers overall utility. Any efficient solution may be found in this way. This is not the case for multiple criteria integer programming. However, in this case one may apply the more general e-constraint approach, resulting in particular single-criteria integer programming problems to generate efficient solutions. We show how this approach implies a more general, composite utility function of the criteria yielding a unified treatment of multiple criteria optimization with and without integrality constraints. Moreover, any efficient solution can be found using appropriate composite functions. The functions may be generated by the classical solution methods such as cutting plane and branch and bound algorithms.     

Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs

We consider discrete bilevel optimization problems where the follower solves an integer program with a fixed number of variables. Using recent results in parametric integer programming, we present polynomial time algorithms for pure and mixed integer bilevel problems. For the mixed integer case where the leader’s variables are continuous, our algorithm also detects whether the infimum cost fails to be attained, a difficulty that has been identified but not directly addressed in the literature. In this case, it yields a “better than fully polynomial time” approximation scheme with running time polynomial in the logarithm of the absolute precision. For the pure integer case where the leader’s variables are integer, and hence optimal solutions are guaranteed to exist, we present an algorithm which runs in polynomial time when the total number of variables is fixed.     

Hypergeometric Polynomials and Integer Programming

We examine connections between A-hypergeometric differential equations and the theory of integer programming. In the first part, we develop a hypergeometric sensitivity analysis for small variations of constraint constants with creation operators and b-functions. In the second part, we study the indicial polynomial (b-function) along the hyperplane xi=0 via a correspondence between the optimal value of an integer programming problem and the roots of the indicial polynomial. Gröbner bases are used to prove theorems and give counter examples.     

邻域整点搜索法求解整数规划

从剖析线性规划的优化机理入手,将纯整数规划分为标准型和非标型两类.首先以标准型纯整数规划为突破口,提出一种新的解法,并在理论上加以证明,然后将其拓广延伸,用于求解非标准型纯整数规划和混合整数规划.这种新解法命名为松驰最优解邻域整点搜索法,属于常规解法,但在简捷高效方面,远胜过现有的两种常规解法—分枝定界法和割平面法.     

Logical Processing for Integer Programming

This paper reviews tools which have great potential for reducing the difficulty of solving IP (and also MIP) problems, if well implemented in solvers. Recent experiments with Branch and Bound solvers, in connection with “Short Start Features”, have shown that implementations need and can still be improved. Concepts which are likely to be specially important for (0,1) MIP are pointed out.     

Planning Urban Recreational Facilities with Integer Goal Programming

Urban planners are often involved in the determination of where recreational facilities (i.e. pools, gymnasia, tennis courts, etc.) should be located within the city. This problem is complicated by the planners' desire to realize certain goals in the allocation process. They desire to build only facilities for which there are sufficient construction funds and which can be operated within a predetermined budget. In addition they desire to satisfy the demands of the residents of the city for different facilities. However, these demands are often conflicting since many urban areas are somewhat segregated with the inner city being predominantly minority/lower income and the outer city consisting of white/upper income groups. These different groups enjoy different types of recreation, and, thus, demand different facilities. Since this is basically an allocation problem with multiple conflicting objectives, goal programming surfaces as an appropriate solution technique. This paper describes an integer (0-1) goal programming model for the recreational allocation problem and demonstrates its use via a case example. The model results specify the facilities which should be constructed that best meet the conflicting goals.     

混合幂次为2和3的整数变量非线性型的整数部分

证明了:假设λ_1,…,λ_6是正实数,λ_1/λ_2是无理数,Dirichlet L函数满足黎曼猜想,x_1,…,x_6是正整数,那么,λ_1x_1~2+λ_2x_2~2+λ_3x_3~3+λ_4x_4~3+λ_5x_2~3+λ_3x_3~3的整数部分可表示无穷多素数.     

整数规划中的正则分解

In this paper, we study the problem of regular decomposition in integer programming. We apply the radical of binomial ideal and universal Gr¨obner bases to get the regular decomposition forms of a finite integer lattice point set. We indicate the relationship between state polytope and regular decompositions, i.e., an edge of state polytope corresponds to a binomial which decides one of regular decomposition forms of a finite integer lattice point set.     

幂次为2,3和4的整变量非线性型的整数部分

假设λ_1,λ_2,λ_2,λ_4是正实数,λ_i/λ_j(1≤ij≤4)至少有一个是无理数.那穇,对于正整数x_1,x_2,x_3,x_4,λ_1x_1~2+λ_2x_2~3+λ_3x_3~4+λ_4x_4~4的整数部分可表示无穷多素数.这个证明极大改进了以前的结果.     

具有模糊变量的线性规划问题

讨论含模糊变量的线性规划问题，研究了其求解方法。利用新定义的模糊数序关系，将它转换成一个多目标线性规划问题，然后进一步转换成两层多目标线性规划问题，进而利用分层规划法求解。     

Convex Separable Minimization Subject to Bounded Variables

A minimization problem with convex and separable objective function subject to a separable convex inequality constraint and bounded variables is considered. A necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. Convex minimization problems subject to linear equality/linear inequality constraint, and bounds on the variables are also considered. A necessary and sufficient condition and a sufficient condition, respectively, are proved for a feasible solution to be an optimal solution to these two problems. Algorithms of polynomial complexity for solving the three problems are suggested and their convergence is proved. Some important forms of convex functions and computational results are given in the Appendix.