125 research outputs found
Progress in Material Handling Research 2012
No full textAndres Carrano (with Reyhan Erin and Moises Sudit) is a contributing author, An MIP Approach to the U-line Balancing Problem With Proportional Worker Throughput, pp. 112-130
Paroids: a canonical format for combinatorial optimization
No full textAbstractAlmost all successful exact approaches to hard combinatorial optimization problems are firmly rooted in the theory of a single canonical model format—linear integer programming. Some heuristic or approximate strategies for hard combinatorial problems are also structured around linear programming, but many of the most effective, including greedy and local search schemes have no close ties to the linear format.This paper introduces a new structure we call a paroid we believe has the potential to remedy these difficulties by providing a purely combinatorial canonical format in which discrete problems can be “naturally” modeled, and in which notions of combinatorial search can be studied and compared. A paroid is formed by a matroid and a partition of the underlying ground set into “all or nothing” parity sets. We offer as exemplars fairly natural paroid optimization formulations for seven classical combinatorial problems. Then a structural hierarchy of paroids is introduced and many of the seven models are seen to fall in the easiest class. We show that standard matroid theory can be extended with natural notions of paroid duals and minors, and investigate invariances over our classes. Finally, we briefly review the results in thecompanion Rardin and Sudit (1988) showing the power of a generic paroid search algorithm to unify a number of quite diverse combinatorial algorithms
Paroids: A generic environment for local search
No full textPerhaps the most important development of the past decade in discrete optimization has been the emergence of a coherent complexity theory providing formal definitions of the classes of problems tractable to different kinds of algorithms. The theory has isolated a vast problem family, NP-Complete, for which is widely accepted that no formally efficient algorithm can be produced for any of its members. This conjecture has renewed mathematical interest in the heuristic/approximate approaches long used in an ad hoc way to tackle hard combinatorial problems. To date, most research on approximate combinatorial algorithms has been either very problem specific or if generic, rooted in linear programming. This research is directed to an alternative approach. The goal is to open the door to truly generic research in combinatorial heuristics by isolating and proving the viability of a canonical combinatorial environment in which heuristics can be structured, compared and applied to numerous specific models. We will define a new matroid based combinatorial structure called paroid. A number of classes of paroids are introduced, and their relation to classical models is shown. Structural properties of paroids and their relation to matroids are presented. Two optimization problems that arise from paroids are introduced, and natural reductions of well-known discrete models into the paroid optimization environment are also shown. The models studied are: k-Matroid Intersection, Matching, Traveling Salesman Problem, Vertex Packing, Graph Partitioning, and Knapsack. We also present a local search procedure, called paroid search which generalizes a number of problem specific algorithms. Some of these generalized procedures include Lin Kerninghan for the Traveling Salesman Problem, the greedy for independence systems, and an optimal algorithm for 2-Matroid Intersection. A number of algorithmic properties are shown, including PLS-Completeness and reachability
INformation fusion engine for real-time decision-making (INFERD): A perceptual system for cyber attack tracking
No full text
Evaluating Threat Assessment for Multi-Stage Cyber Attacks
No full textCurrent practices to defend against cyber attacks are typically reactive yet passive. Recent research work has been proposed to proactively predict hacker\u27s target entities in the early stage of the attack. With prediction, there comes false alarms and missed attacks. Very little has been reported on how to evaluate a threat assessment algorithm, especially for cyber security. Because of the variety and the constantly changing nature of hacker behavior and network vulnerabilities, a cyber threat assessment algorithm is, perhaps more susceptible that for other application domains. This work sets forth the issues on evaluating cyber threat assessment algorithms, and discusses the validity of various statistical measures. Simulation examples are provided to illustrate the pros and cons of using different metrics under various cyber attack scenarios. Our results show that commonly used false positives and false negatives are necessary but not sufficient to evaluate cyber threat assessment
- …
