Optimal production growth for the machine loading problem

This paper investigates a production growth logistics system for the machine loading problem (generalized transportation model), with a linear cost structure and minimum levels on total machine hours (resources) and product types (demands). An algorithm is provided for tracing the production growth path of this system, viz. in determining the optimal machine loading schedule of machines for product types, when the volumes of (i) total machine hours, and (ii) the total amount of product types are increased either individually for each total or simultaneously for both. Extensions of this methodology, when (i) the costs of production are convex and piecewise linear, and (ii) when the costs are nonconvex due to quantity discounts, and (iii) when there are upper bounds for productions are also discussed. Finally, a “goal-programming” production growth model where the specified demands are treated as just goals and not as absolute quantities to be satisfied is also considered.     

Sensor placement in active multistatic sonar networks

The idea of deploying noncollocated sources and receivers in multistatic sonar networks (MSNs) has emerged as a promising area of opportunity in sonar systems. This article is one of the first to address point coverage problems in MSNs, where a number of points of interest have to be monitored in order to protect them from hostile underwater assets. We consider discrete “definite range” sensors as well as various diffuse sensor models. We make several new contributions. By showing that the convex hull spanned by the targets is guaranteed to contain optimal sensor positions, we are able to limit the solution space. Under a definite range sensor model, we are able to exclude even more suboptimal solutions. We then formulate a nonlinear program and an integer nonlinear program to express the sensor placement problem. To address the nonconvex single‐source placement problem, we develop the Divide Best Sector (DiBS) algorithm, which quickly provides an optimal source position assuming fixed receivers. Starting with a basic implementation of DiBS, we show how incorporating advanced sector splitting methods and termination conditions further improve the algorithm. We also discuss two ways to use DiBS to find multiple source positions by placing sensors iteratively or simultaneously. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 287–304, 2017     

Transportation type problems with quantity discounts

It is known to be real that the per unit transportation cost from a specific supply source to a given demand sink is dependent on the quantity shipped, so that there exist finite intervals for quantities where price breaks are offered to customers. Thus, such a quantity discount results in a nonconvex, piecewise linear functional. In this paper, an algorithm is provided to solve this problem. This algorithm, with minor modifications, is shown to encompass the “incremental” quantity discount and the “fixed charge” transportation problems as well. It is based upon a branch-and-bound solution procedure. The branches lead to ordinary transportation problems, the results of which are obtained by utilizing the “cost operator” for one branch and “rim operator” for another branch. Suitable illustrations and extensions are also provided.     

Computing equilibria via nonconvex programming

The problem of determining a vector that places a system in a state of equilibrium is studied with the aid of mathematical programming. The approach derives from the logical equivalence between the general equilibrium problem and the complementarity problem, the latter being explicitly concerned with finding a point in the set S = {x: < x, g(x)> = 0, g(x) ≦ 0, x ≧ 0}. An associated nonconvex program, min{? < x, g(x) > : g(x) ≦ 0, x ≧ 0}, is proposed whose solution set coincides with S. When the excess demand function g(x) meets certain separability conditions, equilibrium solutions are obtained by using an established branch and bound algorithm. Because the best upper bound is known at the outset, an independent check for convergence can be made at each iteration of the algorithm, thereby greatly increasing its efficiency. A number of examples drawn from economic and network theory are presented in order to demonstrate the computational aspects of the approach. The results appear promising for a wide range of problem sizes and types, with solutions occurring in a relatively small number of iterations.     

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     

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.     

一种基于多目标优化的QoS路由交互式算法

为了满足通信网络中一些特定业务对于多个网络指标性能的同时要求 ,研究了一类基于多目标决策的QoS路由算法。通过选取带宽作为约束条件 ,把时延和丢失率作为优化目标 ,建立了QoS路由选择的多目标非线性整数规划模型 ,并给出了一种求解模型的交互式算法。该算法通过逐步调整目标函数的上界 ,压缩目标函数的搜索空间来满足决策者的要求和网络条件。实例计算结果表明了算法的可行性     

Dominating sets for rectilinear center location problems with polyhedral barriers

In planar location problems with barriers one considers regions which are forbidden for the siting of new facilities as well as for trespassing. These problems are important since they model various actual applications. The resulting mathematical models have a nonconvex objective function and are therefore difficult to tackle using standard methods of location theory even in the case of simple barrier shapes and distance functions. For the case of center objectives with barrier distances obtained from the rectilinear or Manhattan metric, it is shown that the problem can be solved in polynomial time by identifying a dominating set. The resulting genuinely polynomial algorithm can be combined with bound computations which are derived from solving closely connected restricted location and network location problems. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 647–665, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10038     

组合导航系统的神经元信息融合模型

提出了一种基于神经元状态融合的组合导航系统信息融合模型 ,给出了神经元融合权重在线自适应学习算法。将该模型应用于车载SINS/GPS组合导航系统 ,通过仿真计算和实验室静态组合导航实验 ,验证了该信息融合模型及融合权重在线自适应学习算法在实际应用中的有效性和可行性。     

装备保障路径选择算法研究

战争时效性对装备保障提出了更高的要求。针对装备保障路径的特点,对传统的解决最短路问题的Dijksta算法进行改进,引入并行处理的概念,提出了改进的最短路算法,建立了新的路径选择评价模型。经实验,此算法可快速、科学和稳定地解决一定范围内装备保障路径选优问题。     

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.     

Optimal service and arrival rates in Jackson queueing networks

In this paper we present an algorithm for solving a class of queueing network design problems. Specifically, we focus on determining both service and arrival rates in an open Jackson network of queueing stations. This class of problems has been widely studied and used in a variety of applications, but not well solved due to the difficulty of the resulting optimization problems. As an example, consider the classic application in computer network design which involves determining the minimum cost line capacities and flow assignments while satisfying a queueing performance measure such as an upper limit on transmission delay. Other application areas requiring the selection of both service and arrival rates in a network of queues include the design of communication, manufacturing, and health care systems. These applications yield optimization problems that are difficult to solve because typically they are nonconvex, which means they may have many locally optimal solutions that are not necessarily globally optimal. Therefore, to obtain a globally optimal solution, we develop an efficient branch and bound algorithm that takes advantage of the problem structure. Computational testing on randomly generated problems and actual problems from a health care organization indicate that the algorithm is able to solve realistic sized problems in reasonable computing time on a laptop computer. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 1–17, 2000     

系统标定的一种新方法

以2008年高教社杯全国大学生数学建模竞赛的A题为研究背景，设计了利用数码相机进行系统标定的一种新方法，建立了相应的数学模型，并设计遗传算法实现了模型的快速求解，算例表明了模型及算法的有效性。     

基于贝叶斯网络的空中目标威胁估计算法

联合作战条件下,指挥决策人员在海量描述战场态势的数据和信息面前往往会束手无策,无法快速作出正确的决策。贝叶斯网络模型是一种基于概率推理的网络化数学模型,能够通过一些变量的信息来获取其他的概率信息,从而解决不定性和不完整性问题。提出了一种基于贝叶斯网络的空中目标威胁估计算法,用空中威胁网络模型找到空中威胁目标各属性之间的潜在关系,并建立空中目标威胁估计算法,最后以一个实例来验证该空中目标威胁估计的计算过程和有效性。     

A quadratic assignment problem without column constraints

We convert a quadratic assignment problem [1] with a nonconvex objective function into an integer linear program. We then solve the equivalent integer program by a simple enumeration that produces global minima.     

一种单平台的无源被动定位算法

提出了一种对匀速扫描雷达的单站被动定位方法 ,主要论述了该定位方法的数学模型 ,仿真分析结果表明该算法有较好的定位精度     

Approximating nondominated sets in continuous multiobjective optimization problems

Many important problems in Operations Research and Statistics require the computation of nondominated (or Pareto or efficient) sets. This task may be currently undertaken efficiently for discrete sets of alternatives or for continuous sets under special and fairly tight structural conditions. Under more general continuous settings, parametric characterisations of the nondominated set, for example through convex combinations of the objective functions or ε‐constrained problems, or discretizations‐based approaches, pose several problems. In this paper, the lack of a general approach to approximate the nondominated set in continuous multiobjective problems is addressed. Our simulation‐based procedure only requires to sample from the set of alternatives and check whether an alternative dominates another. Stopping rules, efficient sampling schemes, and procedures to check for dominance are proposed. A continuous approximation to the nondominated set is obtained by fitting a surface through the points of a discrete approximation, using a local (robust) regression method. Other actions like clustering and projecting points onto the frontier are required in nonconvex feasible regions and nonconnected Pareto sets. In a sense, our method may be seen as an evolutionary algorithm with a variable population size. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

改进预测协方差门限法的采样周期自适应选择算法

传感器采样周期是影响目标跟踪的一个重要参数。现有自适应采样周期策略中,一些算法运算量比较大,计算效率低,不具有一般性。为此提出了一种改进的预测协方差门限法。该算法改进传统采样周期的全遍历寻优策略。最后与几种自适应采样周期算法与固定采样周期算法通过交互式多模型(IMM)滤波算法进行仿真比较。仿真结果表明该算法在目标跟踪过程中能满足跟踪需求,具有较少的计算量,较高的运行效率,比固定采样周期算法更能节约资源。     

基于BP神经网络的防空导弹火力单元阵地评价模型

建立了防空导弹阵地评价的指标体系。对应用人工神经网络解决防空导弹阵地评价的方法问题进行了探讨 ,并且给出了神经网络的评价模型及算法。实例证明该方法是可行的。     

基于Jerk模型的一种改进多传感器数据融合算法

简要介绍了目前存在的一些机动模型和基于状态估计的滤波算法。将Jerk模型与强跟踪滤波算法有机地结合起来,并提出了一种通过时空综合分析的测量方差自适应估计方法以优化强跟踪滤波算法中次优渐消因子和滤波增益的在线选择,同时结合多传感器数据融合具有改善滤波精度的性质,最终给出了一种基于Jerk模型的改进多传感器数据融合算法。最后,通过蒙特卡罗仿真验证了该算法的有效性。