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.     

A penalty for concave minimization derived from the tuy cutting plane

A wide variety of optimization problems have been approached with branch-and-bound methodology, most notably integer programming and continuous nonconvex programming. Penalty calculations provide a means to reduce the number of subproblems solved during the branch-and-bound search. We develop a new penalty based on the Tuy cutting plane for the nonconvex problem of globally minimizing a concave function over linear constraints and continuous variables. Computational testing with a branch-and-bound algorithm for concave minimization indicates that, for the problems solved, the penalty reduces solution time by a factor ranging from 1.2 to 7.2. © 1994 John Wiley & Sons, Inc.     

Facility location on a grid with a diagonal line

This article extends the traditional median problem on a grid to include a diagonal line (e.g., a street). In contrast to the traditional median problem, this generalized problem is nonconvex and nonseparable, invalidating some of the properties on which well-known median-seeking algorithms are based. This work presents an algorithm for finding the median on this generalized grid and discusses the relationship between it and the traditional median.     

The frequency assignment problem: A solution via nonlinear programming

This paper gives a mathematical programming model for the problem of assigning frequencies to nodes in a communications network. The objective is to select a frequency assignment which minimizes both cochannel and adjacent-channel interference. In addition, a design engineer has the option to designate key links in which the avoidance of jamming due to self interference is given a higher priority. The model has a nonconvex quadratic objective function, generalized upper-bounding constraints, and binary decision variables. We developed a special heuristic algorithm and software for this model and tested it on five test problems which were modifications of a real-world problem. Even though most of the test problems had over 600 binary variables, we were able to obtain a near optimum in less than 12 seconds of CPU time on a CDC Cyber-875.     

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.     

Optimization methods for large-scale multiechelon stockage problems

I examine the problem of determining inventory stockage levels and locations of different parts in a multiechelon system. This stockage problem is complicated by parts commonality—each part may be used by several different end items. Stockage levels and locations of each part affect the availability of end items that use the part, since an end item will be out of service if it requires a part that is not available. Of course, if the part is available at another nearby location, then the end item will be out of service for a shorter period of time. An essential feature of any model for this problem is constraints on operational availability of the end items. Because these constraints would involve nonconvex functions if the stockage levels were allowed to vary continuously, I formulate a 0–1 linear optimization model of the stockage problem. In this model, each part can be stocked at any of a number of prespecified levels at each echelon. The model is to minimize stockage cost of the selected items subject to the end-item availability constraints and limits on the total weight, volume, and number of different parts stocked at each echelon. Advantages and disadvantages of different Lagrangian relaxations and the simplex method with generalized upper-bounding capability are discussed for solving this stockage model.     

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.     

系统标定的一种新方法

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

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     

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

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

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.     

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

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