求解整数规划代理对偶的一个新方法

考虑如下的整数线性规划问题: (P)min Cx, s.tAx≥b, x≥0,且为整数向量,其中c,b是具有适当维数的行向量或列向量,A是已知的矩阵,c的分量均为正数,且假定(P)是可行的,x是n维变量。 用V(·)表示优化问题(·)的最优值。如果对x放弃整数限制要求,问题(P)的线     

关于二次域理论求解一类Diophantus方程的整数解

本文研究了两个典型Diophantus方程在实二次域中整数解的问题.利用二次域中的理论和二次代数整数环中算术基本定理,得到了该类方程的一般解法和在实二次域中的所有整数解的相关结论,推广了文献[1]和[2]的结果.     

对于方程整数解个数问题的进一步探究

利用隔板法可以解决经典的方程整数解个数问题．本文将对方程整数解问题进行加强和限制,将其推广到更一般的形式．本文在最后还会利用隔板法和方程整数解的思想,对复杂的实际问题进行探究和求解．     

切割定界与整数分枝结合求解整数线性规划

把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( ILP)问题 .它利用目标函数等值面的移动来切去相应 ( LP)的可行域中含其非整数最优解但不含 ( ILP)可行解的“无用部分”,并将对应的目标函数值作为 ( ILP)目标最优值的一个上界 ;最后 ,通过 ( LP)最优解中非整数基变量的整数分枝来获得整数线性规划的最优解 .     

Euclid域中Diophantus方程的整数解

本文研究了两个典型Diophantus方程的整数解的问题.利用二次域中的重要理论和二次代数整数环中算术基本定理,获得了两个典型Diophantus方程在Euclid域中的所有整数解,推广了文献[6]的结果.     

一类超椭圆方程的整数解

设ｍ，ｎ∈Ｎ；ｍ≥２，ｎ≥２，ｍｎ≥６，ｆ（ｘ）＝ｘｍ＋ａ１ｘｍ－１＋…＋ａｍ∈Ｚ［ｘ］，Ｈ＝ｍａｘ（｜ａ１｜，…，｜ａｍ｜）．本文运用组合分析方法证明了：当ｍ≡０（ｍｏｄｎ），ａ１，…，ａｍ不全为零，而且其中第一个非零系数ａｓ与ｎ互素时，方程ｆ（ｘ）＝ｙｎ，ｘ，ｙ∈Ｚ，仅有有限多组解（ｘ，ｙ），而且这些解都满足｜ｘ｜＜（４ｍＨ）２ｍ／ｎ＋１以及｜ｙ｜＜（４ｍＨ）４ｍ２／ｎ２＋ｍ／ｎ＋１     

整数Bottleneck问题的一个算法

文[1]、[2]讨论了极大极小目标函数的规划问题,并举例说明了在军事、经济等许多领域中都有着极其重要的应用,但在实际问题中,又常常遇到变量要求取整数值的瓶颈问题,即出现了如下整数瓶颈问题     

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

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

波动方程柯西问题的新解法

通过分离变量法,将偏微分方程的定解问题化为常微分方程的定解问题,从而可解一维、二维波动方程柯西问题,该方法可以推广到求解高维波动方程柯西问题。     

关于指数型丢番图方程的整数解

本文简要地介绍了有关Ｓ－单位方程、Ｒａｍａｎｕｊａｎ－Ｎａｇｅｌｌ方程、Ｔｈｕｅ－Ｍａｈｌｅｒ方程、ＬｅＶｅｑｕｅ方程、Ｃａｔａｌａｎ方程、Ｐｉｌｌａｉ方程等指数型丢番图方程整数解的最新结果。这些结果大多是用Ｔｈｕｅ－Ｓｉｅｇｌｅ－Ｒｏｔｈ－Ｓｃｈｍｉｄｔ方法和Ｇｅｌ’ｆｏｎｄ－Ｂａｋｅｒ方法得到的。     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

A Semigroup Approach to Nonlinear Equation of Age-dependent Population Dynamics

This paper deals with nonlinear model, of age-dependent population dynamics, with nonautonomous time dependence. Using a nonlinear semigroup approach, the authors prove the existence of the problem under general assumptions.     

一个丢番图方程及其它的整数解

研究丢番图方程x~y+y~z+z~x=0的可解性,并求该方程的所有整数解.本文利用初等方法及整数的整除性质研究这一问题,获得了彻底解决.即就是证明了方程x~y+y~z+z~x=0有且仅有六组整数解(x,y,z)=(-2,1,1),(1,-2,1),(1,1,-2),(1,-1,-2),(-1,-2,1),(-2,1,-1)     

A note on the MIR closure

In 1988, Nemhauser and Wolsey introduced the concept of MIR inequality for mixed integer linear programs. In 1998, Wolsey gave another definition of MIR inequalities. This note points out that the natural concepts of MIR closures derived from these two definitions are distinct. Dash, Günlük and Lodi made the same observation independently.     

A Column Generation Approach to Delivery Planning over Time with Inhomogeneous Service Providers and Service Interval Constraints

We consider a problem of delivery planning over multiple time periods. Deliveries must be made to customers having nominated demand in each time period. Demand must be met in each time period by use of some combination of inhomogeneous service providers. Each service provider has a different delivery capacity, different cost of delivery to each customer, a different utilisation requirement, and different rules governing the spread of deliveries in time. The problem is to plan deliveries so as to minimise overall costs, subject to demand being met and service rules obeyed. A natural integer programming model was found to be intractable, except on problems with loose demand constraints, with gaps between best lower bound and best feasible solution of up to 35.1%, with an average of 15.4% over the test data set. In all but the problem with loosest demand constraints, Cplex 6.5 applied to this formulation failed to find the optimal solution before running out of memory. However a column generation approach improved the lower bound by between 0.6% and 21.9%, with an average of 9.9%, and in all cases found the optimal solution at the root node, without requiring branching.     

Functional Equation Related to Quadratic and Norm Forms

Let T(a ₁, a ₂,..., a _n ) be a norm form of some finite proper extension of ℚ in a certain fixed integral basis, or even some integer form satisfying certain conditions. We are interested in two problems. One is finding all functions f : ℤ → ℂ satisfying the integer functional equation f(T(a ₁, a ₂,..., a _n )) = T(f(a ₁), f(a ₂),..., f(a _n )). Another closely related problem is finding all functions f : ℤ → ℂ such that T(f(a ₁, f(a ₂,..., f(a _n )) depends only on the value of T(a ₁, a ₂,..., a _n ).The second question was studied before for special quadratic forms. We extend these investigations to other types of quadratic forms and, thus, partially solve the second problem for them. The solution of the first problem for one cubic field is also presented. Finally, we give the corresponding conjecture for the first problem and, additionally, several remarks concerning the choice of norm forms.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 2, pp. 153–172, April–June, 2005.     

A Pseudo-Kinetic Approach for Helmholtz Equation

A lattice Boltzmann type pseudo-kinetic model for a non-homogeneous Helmholtz equation is derived in this paper. Numerical results for some model problems show the robustness and efficiency of this lattice Boltzmann type pseudo-kinetic scheme. The computation at each site is determined only by local parameters, and can be easily adapted to solve multiple scattering problems with many scatterers or wave propagation in non-homogeneous medium without increasing the computational cost.     

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.      

求解非线性互补问题的微分方程方法

本文构造了一种求解非线性互补问题的微分方程方法.在一定条件下,证明了微分方程系统的平衡点是非线性互补问题的解并且基于一般微分方程系统的数值积分建立了一个数值算法.在适当的条件下,证明了此算法产生的序列解是收敛的.本文最后给出了数值结果,该结果表明了此微分方程方法的有效性.