A specially structured nonlinear integer resource allocation problem

We present an algorithm for solving a specially structured nonlinear integer resource allocation problem. This problem was motivated by a capacity planning study done at a large Health Maintenance Organization in Texas. Specifically, we focus on a class of nonlinear resource allocation problems that involve the minimization of a convex function over one general convex constraint, a set of block diagonal convex constraints, and bounds on the integer variables. The continuous variable problem is also considered. The continuous problem is solved by taking advantage of the structure of the Karush‐Kuhn‐Tucker (KKT) conditions. This method for solving the continuous problem is then incorporated in a branch and bound algorithm to solve the integer problem. Various reoptimization results, multiplier bounding results, and heuristics are used to improve the efficiency of the algorithms. We show how the algorithms can be extended to obtain a globally optimal solution to the nonconvex version of the problem. We further show that the methods can be applied to problems in production planning and financial optimization. Extensive computational testing of the algorithms is reported for a variety of applications on continuous problems with up to 1,000,000 variables and integer problems with up to 1000 variables. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 770–792, 2003.     

基于查表的空间填充曲线映射算法

空间填充曲线是进行数据降维处理的典型方法。首先给出对角线空间填充曲线的映射规则,该规则使得在高维情况下存在唯一曲线,并且每一维度上的格点数目不受限制。然后提出等势面的概念,推导出不同等势面上格点数量的递推关系。在此基础上,给出基于查表的对角线空间填充曲线映射算法,该算法执行快、可扩展性好,其时间复杂度随维度的增加呈线性增长。