Lagrangian solution of maximum dispersion problems

We address the so‐called maximum dispersion problems where the objective is to maximize the sum or the minimum of interelement distances amongst a subset chosen from a given set. The problems arise in a variety of contexts including the location of obnoxious facilities, the selection of diverse groups, and the identification of dense subgraphs. They are known to be computationally difficult. In this paper, we propose a Lagrangian approach toward their solution and report the results of an extensive computational experimentation. Our results show that our Lagrangian approach is reasonably fast, that it yields heuristic solutions which provide good lower bounds on the optimum solution values for both the sum and the minimum problems, and further that it produces decent upper bounds in the case of the sum problem. For the sum problem, the results also show that the Lagrangian heuristic compares favorably against several existing heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 97–114, 2000     

Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems

Until recently, fast algorithms for the maximum flow problem have typically proceeded by constructing layered networks and establishing blocking flows in these networks. However, in recent years, new distance-directed algorithms have been suggested that do not construct layered networks but instead maintain a distance label with each node. The distance label of a node is a lower bound on the length of the shortest augmenting path from the node to the sink. In this article we develop two distance-directed augmenting path algorithms for the maximum flow problem. Both the algorithms run in O(n²m) time on networks with n nodes and m arcs. We also point out the relationship between the distance labels and layered networks. Using a scaling technique, we improve the complexity of our distance-directed algorithms to O(nm log U), where U denotes the largest arc capacity. We also consider applications of these algorithms to unit capacity maximum flow problems and a class of parametric maximum flow problems.     

Optimality of the greedy shooting strategy in the presence of incomplete damage information

Consider a situation where a single shooter engages, sequentially, a cluster of targets that may vary in terms of vulnerability and value or worth. Following the shooting of a round of fire at a certain target, the latter may either be killed or remain alive. We assume neither partial nor cumulative damage. If the target is killed, there is a possibility that the shooter is not aware of that fact and may keep on engaging that target. If the shooter recognizes a killed target as such, then this target is considered to be evidently killed. If the objective is to maximize the weighted expected number of killed targets, where the weight reflects the value of a target, then it is shown that a certain type of a shooting strategy, called a Greedy Strategy, is optimal under the general assumption that the more a target is engaged, but still not evidently killed, the less is the probability that the next round will be effective. If all weights are equal, then the greedy shooting strategy calls to engage, at each round, the least previously engaged target that is not evidently killed. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 613–622, 1997     

Note: On the greedy algorithm for optimal assembly

The greedy and balanced algorithms for the optimal assembly of arbitrary structure functions (not necessarily binary) are discussed. Conditions under which these algorithms yield optimal configurations are deduced. © 1992 John Wiley & Sons, Inc.     

Vector processing approach to constrained network problems

Modification of algorithms designed for scalar computing, to take advantage of vector processing, raises several challenges. This article presents the vectorization of the primal simplex based network algorithm and results in a 50% improvement in computational time. One of the major contributors to this improvement is the matching of the size of the pricing candidate list to the vector register size. The side constraints are relaxed into a single surrogate constraint. The single constraint network algorithm is vectorized and used as the basis for solving large-scale constrained network problems. Computational experiments are presented which illustrate the vectorization of the network code as well as the ability of the surrogate constraint approach to deal with large constrained network problems.     

An efficient primal approach to bottleneck transportation problems

This article addresses bottleneck linear programming problems and in particular capacitated and constrained bottleneck transportation problems. A pseudopricing procedure based on the poly-ω procedure is used to facilitate the primal simplex procedure. This process allows the recent computational developments such as the Extended Threaded Index Method to be applied to bottleneck transportation problems. The impact on problem solution times is illustrated by computational testing and comparison with other current methods.     

A combined approach to solve binary multicriteria problems

An implicit enumeration algorithm is developed to determine the set of efficient points in zero-one multiple criteria problems. The algorithm is specialized for the solution of a particular class of facility location problems. The procedure is complemented with the use of the utility function of the decision maker to identify a subset of efficient point candidates for the final selection. Computational results are provided and discussed.     

Nonexistence of the maximum likelihood estimates in the weibull process

With incomplete data the maximum likelihood estimates of the parameters of the Weibull process can only be obtained by solving the likelihood equations iteratively. In this article we show that the solution of the likelihood equations may lie outside of the parameter space if none of the processes can be observed from time zero.     

多波段隐身兼容中的几个矛盾问题的分析

多波段隐身兼容是隐身技术发展的方向,但是每增加一个隐身内容或波段,都对隐身兼容的实现增加很大的难度。分析了多波段隐身兼容技术中存在的几个矛盾问题,包括1 06μm激光隐身与近红外隐身兼容的矛盾、主被动毫米波隐身兼容的矛盾、10 6μm激光与8～14μm热红外隐身兼容的矛盾,同时探讨了解决这些矛盾问题的方法。     

An approach for solving discrete alternative multiple criteria problems involving ordinal criteria

The existence of ordinal criteria is a factor that complicates multiple criteria problems. In this article we develop an approach for the problem of choosing among discrete alternatives assuming that criteria are ordinal. The approach requires pairwise comparisons of alternatives by the decision maker. Based on these comparisons, presumably inferior alternatives are eliminated. Experience on randomly generated problems indicates that the approach usually chooses one of the most preferred alternatives and requires a small number of pairwise comparisons.     

A network flow approach for capacity expansion problems with two facility types

A deterministic capacity expansion model for two facility types with a finite number of discrete time periods is described. The model generalizes previous work by allowing for capacity disposals, in addition to capacity expansions and conversions from one facility type to the other. Furthermore, shortages of capacity are allowed and upper bounds on both shortages and idle capacities can be imposed. The demand increments for additional capacity of any type in any time period can be negative. All cost functions are assumed to be piecewise, concave and nondecreasing away from zero. The model is formulated as a shortest path problem for an acyclic network, and an efficient search procedure is developed to determine the costs associated with the links of this network.     

Analysis of the dispute over Taiwan using a game theory approach

Throughout the world, there is a large number of young, and even not-so-young, scholars who are reading for higher degrees in strategic, security and defense studies, or engaged in analytical research in research institutes, think-tanks or consultancies; they bring to the subject innovative and fresh perspectives often ignored or missed by more established scholars. Most of these people have yet to make their mark in the defense and security field. The Editors of Defense & Security Analysis are resolved to tap this valuable source of information, observation, analysis and critical study by offering a new section of the journal for their views to be given an opportunity to be aired. Submissions of up to 3,000 words are encouraged from University Master's and Doctoral candidates and post-doctoral researchers.     

最大面积避障矩形问题的解法

建立了在一个含有若干障碍点的矩形母域内求一个最大面积避障矩形问题的数学模型.通过分析避障矩形的几何特性,找到了求解这一含有0-1变量的非线性规划数学模型的一种特殊解法.     

An asymptotically optimal greedy heuristic for the multiperiod single‐sourcing problem: The cyclic case

The dynamics of the environment in which supply chains evolve requires that companies frequently redesign their logistics distribution networks. In this paper we address a multiperiod single‐sourcing problem that can be used as a strategic tool for evaluating the costs of logistics network designs in a dynamic environment. The distribution networks that we consider consist of a set of production and storage facilities, and a set of customers who do not hold inventories. The facilities face production capacities, and each customer's demand needs to be delivered by a single facility in each period. We deal with the assignment of customers to facilities, as well as the location, timing, and size of inventories. In addition, to mitigate start and end‐of‐study effects, we view the planning period as a typical future one, which will repeat itself. This leads to a cyclic model, in which starting and ending inventories are equal. Based on an assignment formulation of the problem, we propose a greedy heuristic, and prove that this greedy heuristic is asymptotically feasible and optimal in a probabilistic sense. We illustrate the behavior of the greedy heuristic, as well as some improvements where the greedy heuristic is used as the starting point of a local interchange procedure, on a set of randomly generated test problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 412–437, 2003     

Solving a selected class of location problems by exploiting problem structure: A decomposition approach

For many combinatorial optimization problems that are NP-hard, a number of special cases exist that can be solved in polynomial time. This paper addresses the issue of solving one such problem, the well-known m-median problem with mutual communication (MMMC), by exploiting polynomially solvable special cases of the problem. For MMMC, a dependency graph is defined that characterizes the structure of the interactions between decision variables. A Lagrangian decomposition scheme is proposed that partitions the problem into two or more subproblems, each having the same structure as the original problem, but with simpler dependency graphs. The dual problems are solved using subgradient or multiplier adjustment methods. An efficient method of adjusting the multiplier values is given. Computational results are reported that show the method to be quite effective. In addition, applications of the approach to other difficult location problems is discussed. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 791–815, 1998     

Assembly of systems having maximum reliability

The first problem considered in this paper is concerned with the assembly of independent components into parallel systems so as to maximize the expected number of systems that perform satisfactorily. Associated with each component is a probability of it performing successfully. It is shown that an optimal assembly is obtained if the reliability of each assembled system can be made equal. If such equality is not attainable, then bounds are given so that the maximum expected number of systems that perform satisfactorily will lie within these stated bounds; the bounds being a function of an arbitrarily chosen assembly. An improvement algorithm is also presented. A second problem treated is concerned with the optimal design of a system. Instead of assembling given units, there is an opportunity to “control” their quality, i.e., the manufacturer is able to fix the probability, p, of a unit performing successfully. However, his resources, are limited so that a constraint is imposed on these probabilities. For (1) series systems, (2) parallel systems, and (3) k out of n systems, results are obtained for finding the optimal p's which maximize the reliability of a single system, and which maximize the expected number of systems that perform satisfactorily out of a total assembly of J systems.     

基于最大后验风险的多层Bayes方法

为了对指数型产品进行可靠性鉴定,首先给出了失效率的多层先验分布,然后从最大后验风险的角度,运用Bayes方法,制定出可靠性鉴定试验方案.按照此鉴定试验方案,缩短了试验时间,从而降低了鉴定试验所需的费用.     

Inference for the maximum cell probability under multinomial sampling

This article investigates inference for p_max, the largest cell probability in multinomial trials for the case of a small to moderate number of trials. Emphasis focuses on point and interval estimation. Both frequentist and Bayesian approaches are developed. The results of extensive simulation investigation are included as well as the analysis of a set of crime data for the city of New Orleans taken from the National Crime Survey.     

Iterative coloring extension of a maximum clique

In this paper we present an improved branch and bound algorithm for the vertex coloring problem. The idea is to try to extend the coloring of a maximum clique to its adjacent vertices. If this succeeds, its successive neighbors are considered; in case of failure (i.e., in the case the initial colors are not sufficient), working on the subgraph induced by the maximum clique and its neighborhood, the lower bound is improved by seeking for an optimal coloring of this subgraph by branch and bound. The process is repeated iteratively until the whole graph is examined. The iterative scheme exploits a further lower bound obtained by integrating a simple algorithm into the maximum clique search, and a new method to compute upper bounds on subgraphs. Furthermore, a new branching rule and a method for the selection of the initial maximum clique are presented. Extensive computational results and comparisons with existing exact coloring algorithms on random graphs and benchmarks are given. © 2001 John Wiley & Sons, Inc. Naval Research Logistic 48: 518–550, 2001     

Approximation techniques in the solution of queueing problems

In the study of complex queueing systems, analysis techniques aimed al providing exact solutions become ineffective. Approximation techniques provide an attractive alternative in such cases. This paper gives an overview of different types of approximation techniques available in the literature and points out their relative merits. Also, the need for proper validation procedures of approximation techniques is emphasized.