An algorithm (GIPC2) for solving integer programming problems with separable nonlinear objective functions

This paper presents an algorithm for solving the integer programming problem possessing a separable nonlinear objective function subject to linear constraints. The method is based on a generalization of the Balas implicit enumeration scheme. Computational experience is given for a set of seventeen linear and seventeen nonlinear test problems. The results indicate that the algorithm can solve the nonlinear integer programming problem in roughly the equivalent time required to solve the linear integer programming problem of similar size with existing algorithms. Although the algorithm is specifically designed to solve the nonlinear problem, the results indicate that the algorithm compares favorably with the Branch and Bound algorithm in the solution of linear integer programming problems.     

A branch and bound algorithm for allocation problems in which constraint coefficients depend upon decision variables

A branch and bound algorithm is developed for a class of allocation problems in which some constraint coefficients depend on the values of certain of the decision variables. Were it not for these dependencies, the problems could be solved by linear programming. The algorithm is developed in terms of a strategic deployment problem in which it is desired to find a least-cost transportation fleet, subject to constraints on men/materiel requirements in the event of certain hypothesized contingencies. Among the transportation vehicles available for selection are aircraft which exhibit the characteristic that the amount of goods deliverable by an aircraft on a particular route in a given time period (called aircraft productivity and measured in kilotons/aircraft/month) depends on the ratio of type 1 to type 2 aircraft used on that particular route. A model is formulated in which these relationships are first approximated by piecewise linear functions. A branch and bound algorithm for solving the resultant nonlinear problem is then presented; the algorithm solves a sequence of linear programming problems. The algorithm is illustrated by a sample problem and comments concerning its practicality are made.     

基于反馈线性化及滑模控制的俯冲机动制导方法

以高超声速飞行器为研究对象,针对俯冲段精确制导及机动突防问题,基于反馈线性化与滑模控制研究了机动突防滑模跟踪制导方法。首先设计纵向俯冲及侧向机动弹道,其次利用反馈线性化将非线性运动方程转化为线性方程,基于该线性方程利用滑模控制对已设计的弹道进行跟踪,最终将线性跟踪制导律转换到非线性系统中获得非线性滑模跟踪制导律,该制导律完全基于飞行器当前运动状态,所需的相对运动信息大大减少。CAV-H飞行器制导实例仿真表明,该方法能够实现俯冲段精确制导及机动飞行,且对初始及过程偏差具有较强的鲁棒性,能够为高超声速飞行器俯冲段制导提供有益参考。     

A note on duality in homogeneous fractional programming

For a linear fractional programming problem, Sharma and Swarup have constructed a dual problem, also a linear fractional program, in which the objective functions of both primal and dual problems are the same. Craven and Mond have extended this result to a nonlinear fractional programming problem with linear constraints, and a dual problem for which the objective function is the same as that of the primal. This theorem is now further extended from linear to differentiable convex constraints.     

The payment scheduling problem

Large complicated projects with interdependent activities can be described by project networks. Arcs represent activities, nodes represent events, and the network's structure defines the relation between activities and events. A schedule associates an occurrence time with each event: the project can be scheduled in several different ways. We assume that a known amount of cash changes hands at each event. Given any schedule the present value of all cash transactions can be calculated. The payment scheduling problem looks for a schedule that maximizes the present value of all transactions. This problem was first introduced by Russell [2]; it is a nonlinear program with linear constraints and a nonconcave objective. This paper demonstrates that the payment scheduling problem can be transformed into an equivalent linear program. The linear program has the structure of a weighted distribution problem and an efficient procedure is presented for its solution. The algorithm requires the solution of triangular systems of equations with all matrix coefficients equal to ± or 0.     

基于旋量方法的高超声速飞行器三维非线性伪最优制导律设计

针对高超声速飞行器制导过程中的通道耦合问题,设计一种基于旋量方法的三维非线性伪最优制导律。引入角度矢量、视线旋量、视线旋量速度等概念,通过等价性证明,得出视线旋量、视线旋量速度控制分别与视线方位、视线角速度控制具有一致性的结论,从而将制导问题转化为视线旋量和旋量速度的控制问题;基于旋量方法构建弹目视线旋量、视线旋量速度模型,构建得到飞行器制导的三维非线性模型;为避免直接求解Riccati微分方程过程的复杂性,引入伪控制变量,将三维非线性制导模型转化为线性制导模型;分别针对无终端约束和有终端约束情况,基于二次型最优方法得到三维非线性伪最优制导律。该制导律避免了通道解耦,其制导参数又满足一定物理意义下的最优性。仿真结果验证了所设计制导律的有效性。     

Rank‐Cluster‐and‐Prune: An algorithm for generating clusters in complex set partitioning problems

Clustering problems are often difficult to solve due to nonlinear cost functions and complicating constraints. Set partitioning formulations can help overcome these challenges, but at the cost of a very large number of variables. Therefore, techniques such as delayed column generation must be used to solve these large integer programs. The underlying pricing problem can suffer from the same challenges (non‐linear cost, complicating constraints) as the original problem, however, making a mathematical programming approach intractable. Motivated by a real‐world problem in printed circuit board (PCB) manufacturing, we develop a search‐based algorithm (Rank‐Cluster‐and‐Prune) as an alternative, present computational results for the PCB problem to demonstrate the tractability of our approach, and identify a broader class of clustering problems for which this approach can be used. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

基于正交最小二乘估计的非线性时间序列的预测

在对非线性时间序列的短期预测中经常采用局部线性化的预测算法 ,原有的算法使用普通最小二乘法 (LS)估计近似线性模型的参数。对于存在噪声的数据 ,该算法的数值稳定性较差。本文在对非线性空间进行局部线性化的基础上 ,采用正交最小二乘方法 (OLS)对线性模型同时进行结构选择与参数辨识 ,改善了数值的病态特性 ,增强了算法的稳定性     

An algorithm for solving general fractional interval programming problems

A Linear Fractional Interval Programming problem (FIP) is the problem of extremizing a linear fractional function subject to two-sided linear inequality constraints. In this paper we develop an algorithm for solving (FIP) problems. We first apply the Charnes and Cooper transformation on (FIP) and then, by exploiting the special structure of the pair of (LP) problems derived, the algorithm produces an optimal solution to (FIP) in a finite number of iterations.     

Capacity improvement,penalties, and the fixed charge transportation problem

Capacity improvement and conditional penalties are two computational aides for fathoming subproblems in a branch‐and‐bound procedure. In this paper, we apply these techniques to the fixed charge transportation problem (FCTP) and show how relaxations of the FCTP subproblems can be posed as concave minimization problems (rather than LP relaxations). Using the concave relaxations, we propose a new conditional penalty and three new types of capacity improvement techniques for the FCTP. Based on computational experiments using a standard set of FCTP test problems, the new capacity improvement and penalty techniques are responsible for a three‐fold reduction in the CPU time for the branch‐and‐bound algorithm and nearly a tenfold reduction in the number of subproblems that need to be evaluated in the branch‐and‐bound enumeration tree. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 341–355, 1999     

Postoptimality analysis in nonlinear integer programming: The right-hand side case

An algorithm is presented to gain postoptimality data about the family of nonlinear pure integer programming problems in which the objective function and constraints remain the same except for changes in the right-hand side of the constraints. It is possible to solve such families of problems simultaneously to give a global optimum for each problem in the family, with additional problems solved in under 2 CPU seconds. This represents a small fraction of the time necessary to solve each problem individually.     

利用迭代线性约束最小二乘方法实现不规则阵列的方向图综合

研究了用自适应波束形成技术实现不规则阵列的方向图综合问题,改进了应用于方向图综合的迭代线性约束最小二乘方法,改进后的算法提高了数值稳定性和对随机稀疏阵的适应性。对特定的阵列如果指定的理想方向图无法达到,该算法可以获得最好的逼近。仿真结果验证了算法的性能。     

基于T-S模型的非线性系统主从控制器设计

针对同时具有输出和输入非线性的系统,通过中间虚拟控制量的设置,转化为两个非线性子系统的串联,从而简化系统结构并解决最终控制量不宜直接获取的问题。针对无人水面艇的航迹和横摇控制,设计了基于反演控制的从控制器,实现了输入非线性中虚拟控制量到舵角的映射,通过T-S模型将输出非线性系统,转化为线性时变系统,并考虑舵机的角度与角速度约束,设计了广义预测主控制器。该方法不仅简化了系统结构,同时仿真结果表明,所设计的主从控制器可以获得较好的控制效果。     

求解非线性规划的小生境遗传模拟退火算法

提出了用小生境遗传模拟退火算法求解带复杂约束的非线性规划问题。首先分析了遗传算法＂早熟＂收敛以及局部搜索能力弱的不足,由此引入小生境以增加种群多样性,并抑制＂早熟＂收敛现象,同时引入模拟退火算法以增强局部搜索能力,改进进化后期收敛速度慢的不足,最后结合典型非线性规划算例验证了混合算法的效率、精度和可靠性。     

Variations on a cutting plane method for solving concave minimization problems with linear constraints

A cutting plane method for solving concave minimization problems with linear constraints has been advanced by Tui. The principle behind this cutting plane has been applied to integer programming by Balas, Young, Glover, and others under the name of convexity cuts. This paper relates the question of finiteness of Tui's method to the so-called generalized lattice point problem of mathematical programming and gives a sufficient condition for terminating Tui's method. The paper then presents several branch-and-bound algorithms for solving concave minimization problems with linear constraints with the Tui cut as the basis for the algorithm. Finally, some computational experience is reported for the fixed-charge transportation problem.     

汽油调合优化模型

为了提高炼油厂制订成品油调合方案的科学性,研究了汽油调合优化的非线性规划模型,给出了目标函数和约束条件的具体形式。根据模型特征,选用模拟退火算法对模型求解。最后,通过某炼油厂的一个应用实例验证了上述成品油调合优化模型的有效性。     

求最大数目不相交多约束QoS路由的一种新方法

针对多约束QoS路由问题中从资源点到目的点的最大数目的不相交路由,文章给出了一种基于罚函数与整数规划的求满足QoS约束的最大数目的互不相交路由算法。该算法利用了路由模型的结构特性,使整数规划问题转化为线性规划问题,初步的算例表明算法是有效的。     

Quadratic programming with quadratic constraints

A program with a quadratic objective function and quadratic constraints is considered. Two duals to such programs are provided, and an algorithm is presented based upon approximations to the duals. The algorithm consists of a sequence of linear programs and programs involving the optimization of a quadratic function either unconstrained or constrained to the nonnegative orthant. An example involving production planning is presented.     

同参数估计对偶的自适应控制新算法

把线性系统和非线性系统统一处理,从自适应控制算法与参数估计算法的对偶性出发,提出了自适应控制算法的一种新的统一格式,它改进了已有文献中控制算法的跟踪性能,并在未增加任何条件的情况下,仍然使控制误差一致足够小．     

An exact branch-and-bound procedure for the quadratic-assignment problem

The quadratic-assignment problem is a difficult combinatorial problem which still remains unsolved. In this study, an exact branch-and-bound procedure, which is able to produce optimal solutions for problems with twelve facilities or less, is developed. The method incorporates the concept of stepped fathoming to reduce the effort expended in searching the decision trees. Computational experience with the procedure is presented.