Heuristics for the location of inspection stations on a network

This article considers the preventive flow interception problem (FIP) on a network. Given a directed network with known origin‐destination path flows, each generating a certain amount of risk, the preventive FIP consists of optimally locating m facilities on the network in order to maximize the total risk reduction. A greedy search heuristic as well as several variants of an ascent search heuristic and of a tabu search heuristic are presented for the FIP. Computational results indicate that the best versions of the latter heuristics consistently produce optimal or near optimal solutions on test problems. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 287–303, 2000     

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.     

A finite descent theory for linear programming,piecewise linear convex minimization,and the linear complementarity problem

A descent algorithm simultaneously capable of solving linear programming, piecewise linear convex minimization, and the linear complementarity problem is developed. Conditions are given under which a solution can be found in a finite number of iterations using the geometry of the problem. A computer algorithm is developed and test problems are solved by both this method and Lemke's algorithm. Current results indicate a decrease in the number of cells visited but an increase in the total number of pivots needed to solve the problem.     

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.     

PD反馈特征结构配置在最优控制问题中的应用

考虑了二阶线性系统的比例微分(PD)反馈特征结构配置问题以及其在最优控制问题中的应用。基于比例微分特征结构配置参数化方法,将二阶线性系统的最优控制问题转化为一个便于求解的有约束条件的极小值问题,并给出了相应的求解算法。三自由度质量弹簧阻尼系统算例及其仿真结果表明所提算法简单、有效。     

多目标广义指派问题的模糊匈牙利算法求解

提出和讨论了两类多目标的广义指派决策问题,分别给出了它们的多目标整数线性规划数学模型,并结合模糊理论与解决传统指派问题的匈牙利方法提出了一种新的求解算法:模糊匈牙利法.最后给出了一个数值例子.     

The maximum collection problem with time-dependent rewards

We consider a routing problem where the objective is to maximize the sum of the rewards collected at the nodes visited. Node rewards are decreasing linear functions of time. Time is spent when traveling between pairs of nodes, and while visiting the nodes. We propose a penalty-based greedy (heuristic) algorithm and a branch-and-bound (optimal) algorithm for this problem. The heuristic is very effective in obtaining good solutions. We can solve problems with up to 20 nodes optimally on a microcomputer using the branch-and-bound algorithm. We report our computational experience with this problem. © 1996 John Wiley & Sons, Inc.     

The conjugate gradient technique for certain quadratic network problems

We consider a class of network flow problems with pure quadratic costs and demonstrate that the conjugate gradient technique is highly effective for large-scale versions. It is shown that finding a saddle point for the Lagrangian of an m constraint, n variable network problem requires only the solution of an unconstrained quadratic programming problem with only m variables. It is demonstrated that the number of iterations for the conjugate gradient algorithm is substantially smaller than the number of variables or constraints in the (primal) network problem. Forty quadratic minimum-cost flow problems of various sizes up to 100 nodes are solved. Solution time for the largest problems (4,950 variables and 99 linear constraints) averaged 4 seconds on the CBC Cyber 70 Model 72 computer.     

A primal-dual algorithm for the dynamic lotsizing problem with joint set-up costs

In this article the multi-item dynamic lotsizing problem with joint set-up costs (LPJS) is considered. A tight formulation of the problem and the dual of the linear relaxation of this formulation is presented. A procedure to solve this dual problem is developed where the solution provides a strong lower bound for the LPJS. This lower bound is used in a branch and bound procedure to find an optimal solution to the problem. The extensive computational experiments with this procedure revealed that it outperforms the other available branch and bound algorithm in the literature. With the proposed algorithm the average time requirement was about 113 seconds on a 486DX33 processor for solving a difficult class of LPJS problems that have 50 items and 24 periods. © 1995 John Wiley & Sons, Inc.     

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     

基于鲁棒高阶容积滤波的无人机相对导航状态估计方法

由于无人机相对导航系统具有非线性强、噪声非高斯的特点,传统的基于卡尔曼滤波算法设计的相对导航滤波器存在估计失准甚至发散的问题。考虑到高阶容积卡尔曼滤波和最大熵滤波算法分别在解决非线性问题和非高斯问题时的优势,利用最大熵滤波的量测更新方法对高阶容积卡尔曼滤波的测量更新方程进行了改进,将传统的量测更新问题转换成了线性衰退的求解问题,避免了对测量噪声进行高斯假设,同时解决了系统非线性和量测噪声非高斯的问题。进行了相应的数学仿真,仿真结果表明:所提算法的估计精度超过了高阶容积卡尔曼滤波和最大熵滤波算法的,验证了算法的有效性。     

Minimizing sums and products of linear fractional functions over a polytope

In this paper, we develop efficient deterministic algorithms for globally minimizing the sum and the product of several linear fractional functions over a polytope. We will show that an elaborate implementation of an outer approximation algorithm applied to the master problem generated by a parametric transformation of the objective function serves as an efficient method for calculating global minima of these nonconvex minimization problems if the number of linear fractional terms in the objective function is less than four or five. It will be shown that the Charnes–Cooper transformation plays an essential role in solving these problems. Also a simple bounding technique using linear multiplicative programming techniques has remarkable effects on structured problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 583–596, 1999     

A network isolation algorithm

A set of edges D called an isolation set, is said to isolate a set of nodes R from an undirected network if every chain between the nodes in R contains at least one edge from the set D. Associated with each edge of the network is a positive cost. The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. This paper formulates the problem of determining the minimal cost isolation as a 0–1 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual subproblems are minimal cost network flow problems. Computational results are given. The problem is also formulated as a special quadratic assignment problem and an algorithm is presented that finds a local optimal solution. This local solution is used for an initial bound.     

An algorithm for the discrete bilevel programming problem

The bilevel programming problem (BLPP) is an example of a two-stage, noncooperative game in which the first player can influence but not control the actions of the second. This article addresses the linear formulation and presents a new algorithm for solving the zero-one case. We begin by converting the leader's objective function into a parameterized constraint, and then attempt to solve the resultant problem. This produces a candidate solution that is used to find a point in the BLPP feasible reagion. Incremental improvements are sought, which ultimately lead to a global optimum. An example is presented to highlight the computations and to demonstrate some basic characteristics of the solution. Computational experience indicates that the algorithm is capable of solving problems with up to 50 variables in a reasonable amount of time.     

A decomposable transshipment algorithm for a multiperiod transportation problem

A dynamic version of the transportation (Hitchcock) problem occurs when there are demands at each of n sinks for T periods which can be fulfilled by shipments from m sources. A requirement in period t₂ can be satisfied by a shipment in the same period (a linear shipping cost is incurred) or by a shipment in period t₁ < t₂ (in addition to the linear shipping cost a linear inventory cost is incurred for every period in which the commodity is stored). A well known method for solving this problem is to transform it into an equivalent single period transportation problem with mT sources and nT sinks. Our approach treats the model as a transshipment problem consisting of T, m source — n sink transportation problems linked together by inventory variables. Storage requirements are proportional to T² for the single period equivalent transportation algorithm, proportional to T, for our algorithm without decomposition, and independent of T for our algorithm with decomposition. This storage saving feature enables much larger problems to be solved than were previously possible. Futhermore, we can easily incorporate upper bounds on inventories. This is not possible in the single period transportation equivalent.     

Minimax resource allocation problems with ordering constraints

Resource allocation problems consider the allocation of limited resources among numerous competing activities. We address an allocation problem with multiple knapsack resource constraints. The activities are grouped into disjoint sets. Ordering constraints are imposed on the activities within each set, so that the level of one activity cannot exceed the level of another activity in the same set. The objective function is of the minimax type and each performance function is a nonlinear, strictly decreasing and continuous function of a single variable. Applications for such resource allocation problems are found, for example, in high-tech industries confronted with large-scale and complex production planning problems. We present two algorithms to solve the allocation problem with ordering constraints. The first one uses characterization of the optimal decision variables to apply a search method. The second algorithm solves a sequence of problems, each in the format of the original problem without ordering constraints. Whereas the computational effort of the first algorithm depends on the desired degree of accuracy even for linear performance functions, the effort of the latter algorithm is polynomial for certain classes of performance functions. © 1994 John Wiley & Sons, Inc.     

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     

The interactive fixed charge linear programming problem

In many decision-making situations, each activity that can be undertaken may have associated with it both a fixed and a variable cost. Recently, we have encountered serveral practical problems in which the fixed cost of undertaking an activity depends upon which other activities are also undertaken. To our knowledge, no existing optimization model can accomodate such a fixed cost structure. To do so, we have therefore developed a new model called the interactive fixed charge linear programming problem (IFCLP). In this paper we present and motivate problem (IFCLP), study some of its characteristics, and present a finite branch and bound algorithm for solving it. We also discuss the main properties of this algorithm.     

Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem

In this paper we present a new formulation of the quadratic assignment problem. This is done by transforming the quadratic objective function into a linear objective function by introducing a number of new variables and constraints. The resulting problem is a 0-1 linear integer program with a highly specialized structure. This permits the use of the partitioning scheme of Benders where only the original variables need be considered. The algorithm described thus iterates between two problems. The master problem is a pure 0-1 integer program, and the subproblem is a transportation problem whose optimal solution is shown to be readily available from the master problem in closed form. Computational experience on problems available in the literature is provided.