基于粗集和最大熵的模式识别方法

用基于属性约简的粗集理论找出条件属性的最小属性集。对属性间为不确定因果关系的模式,计算在最大熵情况下发生的概率,通过比较概率来进行模式识别,实例分析和结论部分说明这种方法是有效的。     

On locally optimal independent sets and vertex covers

In this paper, we introduce a new notion of local optimality and demonstrate its application to the problem of finding optimal independent sets and vertex covers in k-claw free graphs. The maximum independent set problem in k-claw free graphs has interesting applications in the design of electronic testing fixtures for printed circuit boards [13]. For this problem, our concept of local optimality enabled us to devise an efficient heuristic algorithm which outperforms the currently best approximation algorithm by nearly a factor of two in terms of worst case bound. We believe that the idea of local optimality suggested in this paper can also be applied to other combinatorial problems such as the clique problem, the dominating set problem and the graph coloring problem. © 1996 John Wiley & Sons, Inc.     

Maximum matching in a convex bipartite graph

A special matching problem arising in industry is shown to be solvable by an algorithm of the form: match objects a_i and b_j if they satisfy a local optirnality criterion based on a ranking of currently unmatched objects. When no a_i and b_i remain that can be matched, the largest number of acceptable matches has been found.     

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     

The graph association problem: Mathematical models and a lagrangian heuristic

Graph association is the problem of merging many graphs that collectively describe a set of possibly repetitive entities and relationships into a single graph that contains unique entities and relationships. As a form of data association, graph association can be used to identify when two sensors are observing the same object so information from both sensors can be combined and analyzed in a meaningful and consistent way. Graph association between two graphs is related to the problem of graph matching, and between multiple graphs it is related to the common labeling of a graph set (also known as multiple graph matching) problem. This article contribution is to formulate graph association as a binary linear program and introduce a heuristic for solving multiple graph association using a Lagrangian relaxation approach to address issues with between‐graph transitivity requirements. The algorithms are tested on a representative dataset. The developed model formulation was found to accurately solve the graph association problem. Furthermore, the Lagrangian heuristic was found to solve the developed model within 3% of optimal on many problem instances, and found better solutions to large problems than is possible by directly using CPLEX. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

A maximum utility solution to a vehicle constrained tanker scheduling problem

A modification to the Dantzig and Fulkerson Tanker Scheduling Problem is described. An insufficient number of vehicles and a utility associated with each vehicle delivery are assumed. The new problem is shown to be equivalent to a Transshipment Problem, the solution of which is the same as the maximal utility solution of the modified Tanker Scheduling Problem. An example is given.     

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     

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.     

子自仿射集的Hausdorff维数

设S1,S2 ,… ,SN 是Rn 上的N个仿射压缩映射 ,若Rn 的紧子集E满足E UNi =1 Si(E) ,则称E为子自仿射集 .作者在一定条件下得到了子自仿射集E的Hausdorff维数 .     

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

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

Analysis of the greedy approach in problems of maximum k-coverage

In this paper, we consider a general covering problem in which k subsets are to be selected such that their union covers as large a weight of objects from a universal set of elements as possible. Each subset selected must satisfy some structural constraints. We analyze the quality of a k-stage covering algorithm that relies, at each stage, on greedily selecting a subset that gives maximum improvement in terms of overall coverage. We show that such greedily constructed solutions are guaranteed to be within a factor of 1 − 1/e of the optimal solution. In some cases, selecting a best solution at each stage may itself be difficult; we show that if a β-approximate best solution is chosen at each stage, then the overall solution constructed is guaranteed to be within a factor of 1 − 1/e^β of the optimal. Our results also yield a simple proof that the number of subsets used by the greedy approach to achieve entire coverage of the universal set is within a logarithmic factor of the optimal number of subsets. Examples of problems that fall into the family of general covering problems considered, and for which the algorithmic results apply, are discussed. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 615–627, 1998     

Cyclical job sequencing on multiple sets of identical machines

The problem posed in this paper is to sequence or route n jobs, each originating at a particular location or machine, undergoing r?1 operations or repairs, and terminating at the location or machine from which it originated. The problem is formulated as a 0-1 integer program, with block diagonal structure, comprised of r assignment subproblems; and a joint set of constraints to insure cyclical squences. To obtain integer results the solutions to each subproblem are ranked as required and combinations thereof are implicitly enumerated. The procedure may be terminated at any step to obtain an approximate solution. Some limited computational results are presented.     

Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine

We examine a class of single-machine scheduling problems with sequence-dependent setup times that arise in the context of semiconductor test operations. We present heuristics for the problems of minimizing maximum lateness with dynamic arrivals and minimizing number of tardy jobs. We exploit special problem structure to derive worst-case error bounds. The special problem structure also enables us to derive dynamic programming procedures for the problems where all jobs are available simultaneously.     

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

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

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.     

网络图论在局域网安全威胁态势分析中的应用

提出了基于网络图论模型的威胁态势分析方法;定义了图中邻接点的攻击代价;给出了计算其效用值的公式,以及计算最大威胁路径、节点的方法。针对某局域网,分析了目标节点的威胁程度及威胁路径。结果表明:不同路径对目标节点的攻击代价各不相同;存在最大和最小威胁路径。