Balancing and optimizing a portfolio of R&D projects

A mathematical formulation of an optimization model designed to select projects for inclusion in an R&D portfolio, subject to a wide variety of constraints (e.g., capital, headcount, strategic intent, etc.), is presented. The model is similar to others that have previously appeared in the literature and is in the form of a mixed integer programming (MIP) problem known as the multidimensional knapsack problem. Exact solution of such problems is generally difficult, but can be accomplished in reasonable time using specialized algorithms. The main contribution of this paper is an examination of two important issues related to formulation of project selection models such as the one presented here. If partial funding and implementation of projects is allowed, the resulting formulation is a linear programming (LP) problem which can be solved quite easily. Several plausible assumptions about how partial funding impacts project value are presented. In general, our examples suggest that the problem might best be formulated as a nonlinear programming (NLP) problem, but that there is a need for further research to determine an appropriate expression for the value of a partially funded project. In light of that gap in the current body of knowledge and for practical reasons, the LP relaxation of this model is preferred. The LP relaxation can be implemented in a spreadsheet (even for relatively large problems) and gives reasonable results when applied to a test problem based on GM's R&D project selection process. There has been much discussion in the literature on the topic of assigning a quantitative measure of value to each project. Although many alternatives are suggested, no one way is universally accepted as the preferred way. There does seem to be general agreement that all of the proposed methods are subject to considerable uncertainty. A systematic way to examine the sensitivity of project selection decisions to variations in the measure of value is developed. It is shown that the solution for the illustrative problem is reasonably robust to rather large variations in the measure of value. We cannot, however, conclude that this would be the case in general. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 18–40, 2001     

Response surface analysis of two‐stage stochastic linear programming with recourse

We apply the techniques of response surface methodology (RSM) to approximate the objective function of a two‐stage stochastic linear program with recourse. In particular, the objective function is estimated, in the region of optimality, by a quadratic function of the first‐stage decision variables. The resulting response surface can provide valuable modeling insight, such as directions of minimum and maximum sensitivity to changes in the first‐stage variables. Latin hypercube (LH) sampling is applied to reduce the variance of the recourse function point estimates that are used to construct the response surface. Empirical results show the value of the LH method by comparing it with strategies based on independent random numbers, common random numbers, and the Schruben‐Margolin assignment rule. In addition, variance reduction with LH sampling can be guaranteed for an important class of two‐stage problems which includes the classical capacity expansion model. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 753–776, 1999     

A guarantee rate optimization model for wastewater treatment system design under uncertainty

We consider a design problem for wastewater treatment systems that considers uncertainty in pollutant concentration levels at water sources. The goal is to optimize the selection of treatment technologies and pipeline connections, so that treated wastewater can achieve specified effluents discharge limits as well as possible. We propose a new two-stage model to optimize a set of guarantee levels, that is, the maximum concentration level of source pollutants for which treated wastewater can be compliant with discharge limits. In the first stage, treatment technologies and pipeline connections are selected. In the second stage, when pollutant concentration levels are revealed, wastewater distribution and mixing are determined. A key attractiveness of the proposed guarantee rate optimization model is that it can be simplified into a single-stage mixed-integer linear program. In our numerical experiments based on real-world pollutants data, the guarantee rate model demonstrates its advantages in terms of computational efficiency, scalability and solution quality, compared with the standard probability maximization model. Finally, the methodology proposed in this paper can also be applied to other two-stage problems under uncertainty with similar uncertainty characteristics.     

舰艇CGF搜潜过程马氏决策规划模型

舰艇搜索潜艇的过程可以近似地看作一种马尔可夫过程.研究了潜艇训练仿真系统中舰艇CGF(计算机生成兵力)搜索潜艇过程中的状态转移过程和随机搜索发现目标的概率模型,将舰艇CGF搜索潜艇的过程分为若干独立的阶段,建立了搜潜过程马氏决策规划模型,提出了在各种不同初始搜索状态下的舰艇搜索策略.仿真结果给出了舰艇CGF的最优搜索策略集合和发现概率,验证了马氏决策规划模型的有效性.     

支持向量顺序回归机的线性规划算法

支持向量顺序回归机是标准支持向量分类机的一个推广,它是一个凸的二次规划问题。本文根据l1范数与l2范数等价关系和优化问题的对偶原理,把凸的二次规划转化成线性规划。由此提了支持向量顺序回归机的线性规划算法,进一步用数值实验验证了此算法的可行性和有效性。并与支持向量顺序回归机相比,它的运行时间缩短了,而且误差i不超过支持向量顺序回归机;     

基于自适应遗传算法的配送型多级库存优化研究

研究了由1个战役仓库、多个战术仓库组成的配送型系统的优化问题,建立了战术仓库使用经济订货批量策略和战役仓库采用4种不同订货策略时的模型,并采用自适应遗传算法实现了模型的求解,实例验证了模型及算法的有效性。     

基于A*算法的坦克CGF全局路径规划

提出了一种应用A*启发式搜索算法对虚拟战场中坦克CGF(Computer Generated Forces)实体进行全局路径规划的方法,同时对A*算法进行了改进,利用二叉堆的结构组织OPEN表,大大加速了A*算法的搜索效率。所提方法可以处理较大规模的战场地形,具有较高的效率。     

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

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

A novel modeling approach for express package carrier planning

Express package carrier networks have large numbers of heavily‐interconnected and tightly‐constrained resources, making the planning process difficult. A decision made in one area of the network can impact virtually any other area as well. Mathematical programming therefore seems like a logical approach to solving such problems, taking into account all of these interactions. The tight time windows and nonlinear cost functions of these systems, however, often make traditional approaches such as multicommodity flow formulations intractable. This is due to both the large number of constraints and the weakness of the linear programming (LP) relaxations arising in these formulations. To overcome these obstacles, we propose a model in which variables represent combinations of loads and their corresponding routings, rather than assigning individual loads to individual arcs in the network. In doing so, we incorporate much of the problem complexity implicitly within the variable definition, rather than explicitly within the constraints. This approach enables us to linearize the cost structure, strengthen the LP relaxation of the formulation, and drastically reduce the number of constraints. In addition, it greatly facilitates the inclusion of other stages of the (typically decomposed) planning process. We show how the use of templates, in place of traditional delayed column generation, allows us to identify promising candidate variables, ensuring high‐quality solutions in reasonable run times while also enabling the inclusion of additional operational considerations that would be difficult if not impossible to capture in a traditional approach. Computational results are presented using data from a major international package carrier. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Optimal empty vehicle redistribution for hub‐and‐spoke transportation systems

This article considers the empty vehicle redistribution problem in a hub‐and‐spoke transportation system, with random demands and stochastic transportation times. An event‐driven model is formulated, which yields the implicit optimal control policy. Based on the analytical results for two‐depot systems, a dynamic decomposition procedure is presented which produces a near‐optimal policy with linear computational complexity in terms of the number of spokes. The resulting policy has the same asymptotic behavior as that of the optimal policy. It is found that the threshold‐type control policy is not usually optimal in such systems. The results are illustrated through small‐scale numerical examples. Through simulation the robustness of the dynamic decomposition policy is tested using a variety of scenarios: more spokes, more vehicles, different combinations of distribution types for the empty vehicle travel times and loaded vehicle arrivals. This shows that the dynamic decomposition policy is significantly better than a heuristics policy in all scenarios and appears to be robust to the assumptions of the distribution types. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008