A generalized euclidean procedure for integer linear programs

This paper investigates a new procedure for solving the general-variable pure integer linear programming problem. A simple transformation converts the problem to one of constructing nonnegative integer solutions to a system of linear diophantine equations. Rubin's sequential algorithm, an extension of the classic Euclidean algorithm, is used to find an integer solution to this system of equations. Two new theorems are proved on the properties of integer solutions to linear systems. This permits a modified Fourier-Motzkin elimination method to be used to construct a nonnegative integer solution. An experimental computer code was developed for the algorithm to solve some test problems selected from the literature. The computational results, though limited, are encouraging when compared with the Gomory all-integer algorithm.     

Optimal location of public facilities

Location of both public and private facilities has become an important consideration in today's society. Progress in solution of location problems has been impeded by difficulty of the fixed charge problem and the lack of an efficient algorithm for large problems. In this paper a method is developed for solving large-scale public location problems. An implicit enumeration scheme with an imbedded transportation algorithm forms the basis of the solution technique.     

Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031     

(0, 1) hyperbolic programming problems

In the first part of this paper we study the unconstrained {0, 1} hyperbolic programming problem treated in [1]. We describe a new algorithm for this problem which produces an optimal solution by scanning just once the set of fractions to be analysed. This algorithm shows better computing performance than the one described in [1]. In the second part we study the {0, 1} hyperbolic programming problem with constraints given by inequalities on nondeereasing pseudo-boolean functions. We describe a “branch and bound” type algorithm for this problem.     

A recursive branch and bound algorithm for the multidimensional knapsack problem

This paper presents an efficient branch and bound algorithm for the solution of certain multiconstrained knapsack problems. The key to this algorithm is a rigidly defined tree structure in which branching and bounding may be performed through recursive relationships. The algorithm is particularly useful when only limited amounts of core storage are available as only the current and one previous solution is saved at any one time. Execution speeds compare favorably with other algorithms. A numerical example and computational experience is given.     

多传感器多目标定位与跟踪技术研究

针对炮兵打击目标的特性和获取目标信息所采用的侦察设施 ,研究了多传感器多目标定位和跟踪问题。在闭圆和聚类概念的基础上 ,提出了一种多传感器多目标融合算法 ,并给出了状态估计的最优解。仿真结果证明了这种算法的有效性。这一模型的物理实现正在进一步研究之中。     

基于DCSP的编队武器兼容性约束协调

编队武器兼容性约束协调,是一个典型的求解分布式约束满足问题的过程。针对这一特点,建立了编队武器兼容性约束满足问题模型,提出了一种基于异步回溯的分布式约束满足算法。该算法运用异步回溯获得一个初始可行解,然后以作战效能最优为原则增添新的方案,并进行约束一致性检查,最终得到满意的编队武器运用方案。仿真验证了算法的可行性。     

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.     

An interactive branch-and-bound algorithm for bicriterion nonconvex/mixed integer programming

Although there has been extensive research on interactive multiple objective decision making in the last two decades, there is still a need for specialized interactive algorithms that exploit the relatively simple structure of bicriterion programming problems. This article develops an interactive branch-and-bound algorithm for bicriterion nonconvex programming problems. The algorithm searches among only the set of nondominated solutions since one of them is a most preferred solution that maximizes the overall value function of the decision maker over the set of achievable solutions. The interactive branch-and-bound algorithm requires only pairwise preference comparisons from the decision maker. Based on the decision maker's responses, the algorithm reduces the set of nondominated solutions and terminates with his most preferred nondominated solution. Branching corresponds to dividing the subset of nondominated solutions considered at a node into two subsets. The incumbent solution is updated based on the preference of the decision maker between two nondominated solutions. Fathoming decisions are based on the decision maker's preference between the incumbent solution and the ideal solution of the node in consideration.     

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

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

The knapsack problem with disjoint multiple-choice constraints

In this article we consider the binary knapsack problem under disjoint multiple-choice constraints. We propose a two-stage algorithm based on Lagrangian relaxation. The first stage determines in polynomial time an optimal Lagrange multiplier value, which is then used within a branch-and-bound scheme to rank-order the solutions, leading to an optimal solution in a relatively low depth of search. The validity of the algorithm is established, a numerical example is included, and computational experience is described.     

邻域加强的并行子空间优化过程

针对基于响应面的并行子空间优化(CSSo-RS)过程的不足,提出了基于邻域加强的改进CSSO-RS优化过程.其主要思路是在子空间优化后,在得到的最优解附近进行全部变量的优化,以更好地协调系统级优化与子空间优化.用经典测试函数及通用航空飞机参数优化问题对该算法进行测试,测试结果表明该算法使CSSO-RS优化效率得到较大的...     

并行基因组合型遗传算法求解防空部署优化问题研究

针对防空部署研究的特点,探讨遗传算法求解防空部署优化问题。分析了传统遗传算法求解武器部署优化问题的缺点,提出了并行的基因组合型改进遗传算法,克服了编码不唯一和基因重码的现象,提高了搜索速度和解的质量;利用启发式信息缩小了解空间,并保证了算法寻优的每个个体都是可行解;对遗传操作算子进行了改进,克服了整数编码固有的缺点。该方法应用于求解防空部署优化问题中得到了较好的结果。     

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.     

An algorithm for the solution of a location problem with metric constraints

In many location problems, the solution is constrained to lie within a closed set. In this paper, optimal solutions to a special type of constrained location problem are characterized. In particular, the location problem with the solution constrained to be within a maximum distance of each demand point is considered, and an algorithm for its solution is developed and discussed.     

基于改进遗传算法的反舰导弹航路规划模型研究

针对传统遗传算法在进行复杂的大范围优化问题时容易陷入局部最优和收敛速度慢的局限,提出采用基于混沌的遗传算法进行反舰导弹航路优化问题的求解。在遗传算法操作时加入混沌操作,扩大了搜索范围,提高了优化速度,有效地解决了解空间巨大带来遗传算法的上述局限性。     

The dynamic lot size model with quantity discount: Counterexamples and correction

Federgruen and Lee ([3]) proposed an optimal algorithm for the single-item dynamic lot size model with all-unit discount. In this note we show that their algorithm fails to find the optimal solution for some special cases. We also provide a modification to the algorithm to handle them. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 419–422, 1998     

基于遗传算法的装备维修方案多目标优化

针对装备维修方案规划的特点,构建了以维修费用最低和作战能力最大的多目标装备维修方案优化模型,并提出针对该模型求解的改进多目标遗传优化算法。在遗传算法设计中,为保证解集的均匀性和多样性,避免过早收敛,建立了随机权重适应度函数,引入精英保留机制和小生境技术,通过实例对该模型的求解进行了验证。仿真结果表明,所构建的模型合理可行,算法运行高效,为部队装备维修方案的制定提供了一定的借鉴。     

The fixed charge problem

The fixed charge problem is a nonlinear programming problem of practical interest in business and industry. Yet, until now no computationally feasible exact method of solution for large problems had been developed. In this paper an exact algorithm is presented which is computationally feasible for large problems. The algorithm is based upon a branch and bound approach, with the additional feature that the amount of computer storage required remains constant throughout (for a problem of any given size). Also presented are three suboptimal heuristic algorithms which are of interest because, although they do not guarantee that the true optimal solution will be found, they usually yield very good solutions and are extremely rapid techniques. Computational results are described for several of the heuristic methods and for the branch and bound algorithm.