整数线性规划问题的一个新算法

本文给出求解整数线性规划问题的一个算法。基本思想是通过求出其伴随线性规划问题的最优单纯形表,把整数线性规划化成正整数系数的不定方程,然后从不定方程的非负整数解集中选取一组满足整数线性规划的约束条件的解,作为整数线性规划的最优解。     

模糊机会约束规划在雷达干扰资源优化分配中的应用

应用模糊机会约束规划理论,研究了不确定环境下的雷达干扰资源优化分配问题。在对雷达目标进行整合的基础上,综合考虑雷达干扰资源分配过程中的不确定因素,建立了双层模糊机会约束混合整数规划模型。并根据可能性测度理论得到双层混合整数规划模型,通过求解混合整数线性规划来获取模型的最优解。计算实例表明方法的优越性和有效性。     

一种求解武器-目标分配问题的启发式方法

武器-目标分配问题是一种NP问题。结合武器-目标分配问题的特点,提出了一种求解武器-目标分配问题的启发式方法。首先给定问题的初始解作为当前最优解,然后采用多点调整方法在当前最优解的邻域内搜索最优解,其后采用重复迭代策略逐步改进初始解,直到得到较好的近似解。实验研究发现,多点调整方法只是一种局部优化方法,由不同初始解出发获得的近似解对应目标值可能不同。把多起点策略、多点调整方法和重复迭代搜索策略相结合,可得到求解武器-目标分配问题的一种有效方法。实验结果表明,提出的启发式方法计算所得解的质量较高,是求解武器-目标分配问题的一种有效方法。     

指挥信息系统非线性最优化问题的混沌搜索解法

指挥信息系统进行辅助决策很多情况下是一个求解最优化问题的过程,指挥信息系统遇到的很多问题具有非线性,同时指挥信息系统对算法的适应性和收敛速度要求相当严格。对此,普通的优化技术只能求出局部最优解。基于混沌搜索技术的计算智能具有全局搜索能力强、算法简洁、计算量小、收敛速度快的特点,成为一种求解非线性最优化问题全局最优的有效方法。算例表明,当搜索次数达到一定数量时,混沌搜索方法可以保证算法收敛到全局最优解,且计算效率很高。     

约束最短链路不相交路径的启发式算法

文章研究约束最短链路不相交路径(CSDP(k))问题,该问题分为两类:CSDP(k)-和CSDP(k)-。首先引入问题的整数规划模型,通过拉格朗日乘子将复杂约束引入到目标函数中,接着给出了求解CSDP(k)-的一种快速启发式算法FHABIP,并给出了改进的搜索方案。算法实验结果表明该算法快速有效,能得到最优解或很好的近似最优解。     

搜索路径给定时的搜索对策问题及其应用

搜索路径给定时的最优搜索方案问题,也可以理解为是关于搜索者和目标的二人对策问题,主要讨论了当搜索路径给定时的单个搜索者和单个目标的搜索对策问题。首先根据问题的特点,利用动态规划和迭代的方法,确定关于目标逃逸路径混合策略的最优分区,证明该分区是多面体凸集;针对目标不同逃逸路径的分区,求出搜索者的最大期望收益,再将问题转化为二人有限零和对策,计算出搜索者的支付矩阵,确定最优搜索策略。最后结合海军护航行动,对我舰载直升机搜索小型海盗船进行分析和计算,说明搜索路径给定时的最优搜索对策对于双方的资源分配和提高搜索效率具有一定的应用价值。     

军队人力资源培训问题的整数线性规划模型

文章研究了军队人力资源培训问题,并基于时间和费用两个指标,建立了一个满足培训时间约束且费用最省的0-1整数线性规划模型,给出了基于Lagrange松驰分解的模型求解算法。在算法中,采用一种简单可行的Lagrange乘子更新方法代替传统的次梯度法。另外,文章证明了算法获得最优解的两个充分条件,计算实例初步表明给出的算法是行之有效的。     

求解武器目标分配问题的一个近似最优方法

文章研究在作战领域中应用非常广泛的武器目标分配(WTA)问题。这一问题研究如何将一类武器分配给打击目标,使得被打击目标总的损毁效果最大。WTA问题难以找到多项式时间解,目前不存在求最优解的精确算法。文章利用WTA模型中目标函数的特点,使用线性函数来替代原问题中的非线性目标函数,近而将非线性整数规划问题转化为线性整数规划问题。在CPLEX下的数值试验显示,在较短时间内,这一线性整数规划模型可以得到一个好的次优解。     

面向多最优解组合优化问题的决策求解算法

针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(mⁿ)的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。     

基于MOEO的电子侦察卫星多目标规划方法

分析了电子侦察卫星任务规划问题的内涵,基于合理假设建立了问题的多目标规划模型;设计了一种基于MOEO(Multi-objective Extremal Optimization)的多目标极值优化算法对模型进行求解,提出了一种针对电子侦察卫星规划问题的随机交换变异算子对解空间进行搜索;同时,为防止Pareto近似最优解的...     

All-integer linear programming — a new approach via dynamic programming

An exact method for solving all-integer linear-programming problems is presented. Dynamic-programming methodology is used to search efficiently candidate hyperplanes for the optimal feasible integer solution. The explosive storage requirements for high-dimensional dynamic programming are avoided by the development of an analytic representation of the optimal allocation at each stage. Computational results for problems of small to moderate size are also presented.     

A finite algorithm for concave minimization over a polyhedron

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.     

兵力展开问题研究

如何将基地的兵力以最短时间展开到多个阵地中,是运输问题中的一种。为解决此问题对著名的兵力展开问题进行了研究。建立了兵力展开问题的数学模型,此模型是一个混合整数规划模型。提出了一种求解方法,该方法可解决类似的混合整数规划问题。最后给出了一个实例。     

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.     

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.     

Models and algorithms for shuffling problems in steel plants

In this article, we study item shuffling (IS) problems arising in the logistics system of steel production. An IS problem here is to optimize shuffling operations needed in retrieving a sequence of steel items from a warehouse served by a crane. There are two types of such problems, plate shuffling problems (PSP) and coil shuffling problems (CSP), considering the item shapes. The PSP is modeled as a container storage location assignment problem. For CSP, a novel linear integer programming model is formulated considering the practical stacking and shuffling features. Several valid inequalities are constructed to accelerate the solving of the models. Some properties of optimal solutions of PSP and CSP are also derived. Because of the strong NP‐hardness of the problems, we consider some special cases of them and propose polynomial time algorithms to obtain optimal solutions for these cases. A greedy heuristic is proposed to solve the general problems and its worst‐case performances on both PSP and CSP are analyzed. A tabu search (TS) method with a tabu list of variable length is proposed to further improve the heuristic solutions. Without considering the crane traveling distance, we then construct a rolling variable horizon heuristic for the problems. Numerical experiments show that the proposed heuristic algorithms and the TS method are effective. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

一种基于0-1整数规划的全局数据分布优化方法

数据分布是影响并行程序在分布主存多处理机上执行性能的重要因素.针对分布主存多处理机中的数据分布问题,提出了一种基于0-1整数规划、利用数据变换技术进行有效数据分布的方法.该方法通过数据变换技术改变数据的存储布局,以使得数据能被有效地分布,并且该方法还利用数据分布图描述程序被并行的情况及其所含数组被访问的情况,并将全局数据分布优化问题转换为求解数据分布图中最优路径的问题,从而可用0-1整数规划求解最优路径问题.该方法能对多个嵌套循环中具有仿射数组下标的任意维数组进行有效的数据分布,并且也能使嵌套循环的并行度尽可能地大.另外,该方法也考虑了偏移常量的对准问题,从而能使数据通信量尽量地小.实验结果验证了该方法的有效性.     

A bounded dual (all-integer) integer programming algorithm with an objective cut

In this article, we describe a new algorithm for solving all-integer, integer programming problems. We generate upper bounds on the decision variables, and use these bounds to create an advanced starting point for a dual all-integer cutting plane algorithm. In addition, we use a constraint derived from the objective function to speed progress toward the optimal solution. Our basic vehicle is the dual all-integer algorithm of Gomory, but we incorporate certain row- and column-selection criteria which partially avoid the problem of dual-degenerate iterations. We present the results of computational testing.     

Hyperbolic integer programming

The hyperbolic integer program is treated as a special case of a hyperbolic program with a finite number of feasible points. The continuous hyperbolic program also belongs to this class since its solution can be obtained by considering only the extreme points of the feasible set. A general algorithm for solving the hyperbolic integer program which reduces to solving a sequence of linear integer problems is proposed. When the integer restriction is removed, this algorithm is similar to the Isbell-Marlow procedure. The geometrical aspects of the hyperbolic problem are also discussed and several cutting plane algorithms are given.     

两段探测目标的传感器任务调度问题0-1规划模型及算法

为解决指挥系统控制中的调度困难,研究了一类特殊的传感器资源调度问。主要分析了跟踪目标的探测次数、时间间隔和传感器资源等约束条件。用跟踪目标的重要程度之和作为目标函数,建立了一个0-1规划的数学模型,再利用变换将其转化为0-1线性整数规划模型。利用割平面法求解得出最优调度策略,其能在工作量饱和的情况下合理调度传感器资源。为提高求解速度,提出了对应的模拟退火算法。通过对一些不同规模实例的求解,在资源利用率和算法的求解速度等指标上,与割平面法及遗传算法进行对比分析,验证了模型的有效性和模拟退火算法求解的高效性。