While agricultural robotics has made great strides in recent years, manipulation of plants for tasks such as staking and harvesting remains highly challenging due to the high variability in dynamics and deformable nature of plants. To address the challenges created by dynamics uncertainty, we develop a system applying an occupancy-belief planning concept to plant manipulation for staking. We first train a dynamics model that predicts a per-pixel probability that the plant occupies the corresponding slice in space after a drag action using a large set of simulators. This model is then used to plan a manipulation action that maximizes the probability areas swept by the stake tying tool’s operating region are occupied by the plant, and minimize the probability areas swept by the non-operating side regions of the tool are occupied. We demonstrate our method both in simulation and with zero-shot sim-to-real transfer to a physical implementation. We show that adding consideration of belief through use of occupancy-belief allows our method to outperform both the visual foresight type approaches it is based on and other baselines and ablations, especially in the real-world case.

We address the problem of generating robust solutions for the makespan minimization problem on identical agents (parallel machines), under the assumption that only interval bounds of processing times are known. While there are various concepts of robustness in the literature, we prove using pathological examples that any of these criteria may result in allocations with undesirable characteristics. We identify key properties that must be satisfied for a solution to be considered truly robust. Given a set of jobs with associated loads and uncertainties, it is shown that an allocation that balances loads and uncertainties simultaneously is extremely robust and satisfies multiple other existing criteria of robustness within an acceptable approximation factor. Thus, robustness is achieved by distributing the uncertainty/risk among the agents along with the load. The problem of finding a robust allocation is reduced to a bi-criteria two-dimensional load balancing problem, with the two dimensions being the load and the uncertainty. We prove that for the case with 2 agents, an allocation that satisfies a 1.5-approximation on both dimensions simultaneously always exists and can be found efficiently, and is also the best possible guarantee. For the general case with any number of agents, we prove that an allocation that satisfies a 2-approximation on one dimension and a 2.5-approximation on the other always exists and can be found in pseudo-polynomial time. The approximation algorithms presented in this paper are complemented by interesting existential and structural results and contribute to the vector scheduling literature for two dimensions as well. Finally, an extensive numerical analysis is presented, where we demonstrate our algorithms’ near-optimal performance and ability to generate allocations that satisfy multiple criteria of robustness simultaneously in a short amount of time. Note to Practitioners—This paper introduces a simple and provably effective methodology for generating robust allocations in the context of the makespan minimization problem, a critical challenge in operational management that significantly impacts the efficiency and productivity of various industries. We demonstrate using counter-examples that traditional concepts of robustness such as worst-case makespan and min-max regret can lead to overly conservative and practically inefficient allocations, even when solved optimally. Following this, it is shown that an allocation that balances loads and uncertainties simultaneously is extremely robust and satisfies multiple other existing criteria of robustness within an acceptable approximation factor. This leads to a more attractive and practical concept of robustness. Efficient, fast, and provably good algorithms are presented that solve a 2D Load Balancing problem and generate allocations that are balanced with respect to both the loads as well as uncertainties for a large percentage of the possible scenarios. Numerical results provide practitioners confidence in our approach. The algorithm further classifies the jobs as critical and non-critical based on their completion times and uncertainties in a way that leads to provably good allocations. This classification can be further used to obtain intuition about the problem, thus providing managerial insights.

As cloud-native workflow orchestration tools become increasingly important for complex data science workloads, there is a growing need for more efficient scheduling. Existing cloud schedulers rely on basic heuristics and user choice for task partitioning for parallel computing, leading to under-utilization of cluster resources and prolonged job completion times. To address this, we propose a novel workflow scheduling algorithm that leverages workflow characteristics to enhance resource utilization and reduce weighted job completion time. The algorithm combines three sub-algorithms, each reflecting a distinct aspect of the scheduling strategy: 1) Hybrid Maximum Children (MC) -Weighted Shortest Critical Path Time (WSCPT) rule alternates between two heuristics, MC and WSCPT, which prioritize jobs based on workflow structure and critical path, respectively. The choice between these heuristics is dynamically adjusted according to the cluster queue size. 2) Dynamic Resource Allocation (DRA), which dynamically adjusts the number of executors assigned to each workflow, and 3) Dynamic Task Partition (DTP), which autonomously determines the task parallelism level. We tested our algorithm with extensive experiments on various workflow types using Spark-imitated simulation. Our algorithm outperformed other schedulers, including learning-based models, by reducing 21-47% of the combined performance of average job completion time and makespan for unweighted workflows and reducing at least 50% of weighted job completion time for weighted workflows.

The Linear Assignment Problem (LAP) is a fundamental combinatorial optimization problem with a wide range of applications. Over the years, significant progress has been made in developing efficient algorithms to solve the LAP, particularly in the realm of high-performance computing, which has led to remarkable reductions in computation time. In recent years, hardware improvements in General Purpose Graphics Processing Units (GPGPUs) have shown promise in meeting the ever-increasing compute bandwidth requirements. This has attracted researchers to develop GPU-accelerated algorithms to solve the LAP. Recent work in the GPU domain has uncovered parallelism available in the problem structure to achieve significant performance improvements. However, each solution presented so far targets either sparse or dense instances of the problem and has some scope for improvement. The Hungarian algorithm is one of the most famous approaches to solving the LAP in polynomial time. Hungarian algorithm has classical O(N4) (Munkres') and tree based O(N3) (Lawler's) implementations. It is well established that the Munkres' implementation is faster for sparse LAP instances while the Lawler's implementation is faster for dense instances. In this work, we blend the GPU implementations of Munkres' and Lawler's to develop a Hybrid GPU accelerated solver for LAP that switches between the two implementations based on available sparsity. Also, we improve the existing GPU implementations to reduce memory contention, minimize CPU-GPU synchronizations, and coalesced memory access. The resulting solver (HyLAC) works faster than existing CPU/GPU LAP solvers for sparse as well as dense problem instances. HyLAC achieves a speedup of up to 6.14× over existing state-of-the-art GPU implementation when run on the same hardware. We also develop an implementation to solve a list of small LAPs (tiled LAP), which is particularly useful in the optimization domain. This tiled LAP solver performs 22.59× faster than the existing implementation.

We present a GPU solution for exact maximal clique enumeration (MCE) that performs a search tree traversal following the Bron-Kerbosch algorithm. Prior works on parallelizing MCE on GPUs perform a breadth-first traversal of the tree, which has limited scalability because of the explosion in the number of tree nodes at deep levels. We propose to parallelize MCE on GPUs by performing depth-first traversal of independent subtrees in parallel. Since MCE suffers from high load imbalance and memory capacity requirements, we propose a worker list for dynamic load balancing, as well as partial induced subgraphs and a compact representation of excluded vertex sets to regulate memory consumption. Our evaluation shows that our GPU implementation on a single GPU outperforms the state-of-the-art parallel CPU implementation by a geometric mean of 4.9× (up to 16.7×), and scales efficiently to multiple GPUs. Our code has been open-sourced to enable further research on accelerating MCE.

Multi-Target Tracking (MTT) is a challenging problem in the field of data association and sensor data fusion. Many solutions to MTT assume a Markovian nature to the motion of the target to solve the problem and avoid the potential computational complexity. Recently, we have shown that considering a sequence of three time steps and their resulting triplet costs in data association provides a superior solution that better incorporates the kinematic behavior of maneuvering targets. Nevertheless, the triplet costs pose significant computational overhead and scaling challenges. In this paper, we present significant computational advances in a triplet cost-based data association engine for MTT using Graphics Processing Units (GPUs). We achieve this by improving the computational performance of the dual ascent algorithm for dense Multi-Dimensional Assignment Problem (MAP), presented in Vadrevu and Nagi, 2022. Our contributions include: (1) A very fast GPU-accelerated Linear Assignment Problem (LAP) solver that solves an array of tiled LAPs without synchronizing with the CPU, (2) Reduction in computational overheads of triplet costs by using gating and compressed matrix representations, and (3) Computational performance studies that demonstrate the effectiveness of our computational enhancements. Our resulting solution is 5.8 times faster than the current solution without compromising the accuracy.

BEEP is a state-of-the-art subgraph enumerator that delivers high performance through a combination of balanced, parallel GPU processing and novel algorithmic improvements. With a rapidly increasing demand for fast tools on large graphs, GPU-based subgraph enumerators are of growing interest. Most existing GPU enumerators are based on Breadth First Search (BFS), which often impose limitations on hardware resources due to excessive memory requirements. PARSEC [12] was the first GPU enumerator to adopt Depth First Search (DFS) that demonstrated impressive speedups and its adaptability to hardware with limited memory resources. However, PARSEC’s DFS implementation suffers from computational inefficiencies and load imbalances. BEEP introduces novel search space reduction techniques and load balancing strategies to tackle these challenges in DFS-based parallelization and achieves exceptional performance and scalability. Experimental results indicate that BEEP outperforms PARSEC with geometric mean speedups of up to 10.52 × across disparate data graphs and up to 7.28 × across various queries with maximum speedups of 33.46 ×. This makes BEEP the fastest subgraph enumerator to date. Furthermore, a multi-GPU implementation is developed that exhibits almost linear scalability with the number of devices.

We study the problem of allocating a set of indivisible operations to a set of agents in a fair and efficient manner while also minimizing the makespan. We first present the Operation Trading Algorithm that generates allocations satisfying the DEQx (Duplicated Equitability up to any operation) fairness criterion while also guaranteeing an upper bound of 2 on the makespan for identical agents. The pairwise approach used in this algorithm has the added advantages of being decentralizable and robust. We then define a relaxed version of the DEQ1 (Duplicated Equitability upto some operation) fairness criterion called partial-DEQ1. A market based algorithm is presented to achieve partial-DEQ1 along with Pareto Optimality. Following this, it is shown that the algorithm also guarantees an upper bound of 1.618 on the makespan for 2 non-identical agents. Parametric Pruning further improves the upper bound to 1.5 which is theoretically the best possible upper bound. To the best of our knowledge, these are the first algorithms designed to achieve the mentioned fairness criteria. The algorithms additionally guarantee upper bounds on the makespan. Finally, we show the efficacy of the algorithms in generating allocations with near optimal makespans by numerically evaluating the algorithms on random instances. Note to Practitioners—This paper provides fast algorithms that can be used for task allocation among any number of agents. The algorithms generate allocations that satisfy fairness criteria along with minimizing the makespan, thus achieving two practically important criteria simultaneously. Additionally, some of the algorithms introduced can be implemented in a reactive manner thus making it easy to deal with sudden changes. The algorithms can also be implemented in a decentralized manner in environments where maintaining a centralized situational awareness is difficult due to communication and machine failures.

We develop a Graphics Processing Unit (GPU) accelerated algorithm for the NP-Hard Multi-dimensional Assignment Problem (MAP), suitable for target tracking applications. First, the original MAP formulation with a quadratic objective function is reformulated using a creative linearization technique. This formulation lends itself well to Lagrangian Relaxation, which decomposes into pairwise Linear Assignment Problems (LAPs). These LAPs are solved in parallel and are each solved using a recent GPU-accelerated approach. Next, we propose a dual-ascent scheme for the Lagrange multiplier updates. The advantage of this scheme is that it results in monotonically increasing lower bounds and converges in a fraction of the iterations typically needed for a subgradient method. The dual-ascent technique is also parallelized for the GPU. Finally, we develop a creative gap closure scheme with$M$-best LAP solutions for each dimension and find the shortest path in the resulting staged graph. The algorithm is applied to the Multi-Target Tracking problem and tested on datasets for maneuverable targets. Scaling studies are also performed, and note that the processing time goes down approximately linearly in the number of GPU devices. The algorithm can efficiently solve up to a problem size of 400 targets in 400 time-frames, which corresponds to 25 billion variables, with high accuracy.Note to Practitioners—The Multi-Target Tracking problem (MTT) has been a longstanding problem with various variants and solution algorithms. Still, the problem remains challenging, especially when dealing with a large number of targets for many time frames, when solution speed and optimality are concerns. Many problems including, entity resolution, weapon target assignment, resource allocation, and data association can be formulated as MAP. Our overall algorithm, implemented with GPU acceleration enables addressing large-dimensioned MAPs, e.g., number of observed targets for a long horizon, for around 25 billion variables. As per our knowledge, no algorithm could tackle this large-scale data either for MAP or MTT.

Demand for efficient cloud-native workflow scheduling is growing as many data science workloads are composed of several tasks with dependencies. As container technology becomes more prevalent in cloud communities, containerized workflow orchestration tools are introduced and become standard for scheduling workflows. However, current schedulers use simple heuristics and rely on the user's choice on priority and parallelism level of tasks without accounting for workflow-specific information.

Counting k-cliques in a graph is an important problem in graph analysis with many applications such as community detection and graph partitioning. Counting k-cliques is typically done by traversing search trees starting at each vertex in the graph. Parallelizing k-clique counting has been well-studied on CPUs and many solutions exist. However, there are no performant solutions for k-clique counting on GPUs.

Subgraph enumeration is an important problem in the field of Graph Analytics with numerous applications. The problem is provably NP-complete and requires sophisticated heuristics and highly efficient implementations to be feasible on problem sizes of realistic scales. Parallel solutions have shown a lot of promise on CPUs and distributed environments. Recently, GPU-based parallel solutions have also been proposed to take advantage of the massive execution resources in modern GPUs. Subgraph enumeration involves traversing a search tree for each vertex of the data graph to find matches of a query in a graph. Most GPU-based solutions traverse the tree in breadth-first manner that exploits parallelism at the cost of high memory requirement and presents a formidable challenge for processing large graphs with high-degree vertices since the memory capacity of GPUs is significantly lower than that of CPUs. In this work, we propose a novel GPU solution based on a hybrid BFS and DFS approach where the top level(s) of the search trees are traversed in a fully parallel, breadth-first manner while each subtree is traversed in a more space-efficient, depth-first manner. The depth-first traversal of subtrees requires less memory but presents more challenges for parallel execution. To overcome the less parallel nature of depth-first traversal, we exploit fine-grained parallelism in each step of the depth-first traversal of sub-trees. We further identify and implement various optimizations to efficiently utilize memory and compute resources of the GPUs. We evaluate our performance in comparison with the state-of-the-art GPU and CPU implementations. We outperform the GPU and CPU implementations with a geometric mean speedup of 9.47× (up to 92.01×) and 2.37× (up to 12.70×), respectively. We also show that the proposed approach can efficiently process the graphs that previously cannot be processed by the state-of-the-art GPU solutions due to their excessive memory requirement.

We propose and address a new variation of the team orienteering problem (TOP) in which all members of the team are independent self-interested agents. The prize-collecting nature emanates from the fact that the prize available at a node of the traversal graph can be collected only by a single visiting agent. The problem is motivated by situations in which team members (agents) must accomplish tasks toward a common goal but are unable to communicate, such as a fleet of surveillance drones operating in a communication denied area or with remote pilots operating independently. We explore three policies for minimizing the amount of inefficiency these self-interested agents can bring into the situation. We analyze these policies in a game-theoretic framework and show upper bounds on the Price of Anarchy (PoA) ranging from$\approx 1.582$to unbounded depending on the policy, network type, and the number of players$k$. This is done by extending well-known PoA bounds for valid utility systems to a leader–follower setting. The PoA also depends on the behavior of the agents, which could not have goodwill toward other agents. In many cases, we are able to provide examples that establish the tightness of the bounds. Finally, solution methods are provided for each of these policies. Numerical results computed by these solution methods are then presented and compared with the optimal centrally coordinated solutions.Note to Practitioners—Unmanned aerial vehicles (UAVs) are becoming increasingly popular for information collection tasks in defense and civilian applications alike. When the collection area is large, it is not unusual that a fleet of UAVs is deployed. Routing of a fleet can be performed in a centralized or decentralized manner. Decentralized routing might be the only possibility when centralized situational awareness is not possible due to bandwidth limitations and when centralized optimal routes for each UAV are too complex to compute. For managers of UAV systems, our work provides a theoretical bound on how bad decentralized routing could be in the context of a prize-collecting game. Under a game-theoretic framework, we prove that the fleet will collect at least 50% of the prizes collected by the optimal centralized solution. Empirically, we show that the performance of the fleet is much better, usually providing at least 90% of the optimal centralized solution. Our routing strategies provide valuable guidance to the practicing engineer or manager of a UAV fleet.

The fast-growing market of autonomous vehicles, unmanned aerial vehicles, and fleets in general necessitates the design of smart and automatic navigation systems considering the stochastic latency along different paths in the traffic network. The longstanding shortest path problem in a deterministic network, whose counterpart in a congestion game setting is Wardrop equilibrium, has been studied extensively, but it is well known that finding the notion of an optimal path is challenging in a traffic network with stochastic arc delays. In this work, we propose three classes of risk-averse equilibria for an atomic stochastic congestion game in its general form where the arc delay distributions are load dependent and not necessarily independent of each other. The three classes are risk-averse equilibrium (RAE), mean-variance equilibrium (MVE), and conditional value at risk level$\alpha $equilibrium ($\text{CVaR}_{\alpha}\text{E}$) whose notions of risk-averse best responses are based on maximizing the probability of taking the shortest path, minimizing a linear combination of mean and variance of path delay, and minimizing the expected delay at a specified risky quantile of the delay distributions, respectively. We prove that for any finite stochastic atomic congestion game, the risk-averse, mean-variance, and$\text{CVaR}_{\alpha}$equilibria exist. We show that for risk-averse travelers, the Braess paradox may not occur to the extent presented originally since players do not necessarily travel along the shortest path in expectation, but they take the uncertainty of travel time into consideration as well. We show through some examples that the price of anarchy can be improved when players are risk-averse and travel according to one of the three classes of risk-averse equilibria rather than the Wardrop equilibrium.

This article attempts to provide viral marketeers guidance in terms of an investment level that could help capture some desired γ percentage of the market share by some target time t with the desired level of confidence. To do this, we first introduce a generalized diffusion model for social networks. A distance-dependent random graph is then considered as a model for the underlying social network, which we use to analyze the proposed diffusion model. Using the fact that vertices degrees have an almost Poisson distribution in distance-dependent random networks, we then provide a lower bound on the probability of the event that the time it takes for an idea (or a product, campaign, disease, and so on) to dominate a prespecified γ percentage of a social network (denoted by Rγ) is smaller than some preselected target time t > 0, i.e., we find a lower bound on the probability of the event {Rγ≤ t}. Simulation results performed over a wide variety of networks, including random and real world, are then provided to verify that our bound indeed holds in practice. The Kullback-Leibler divergence measure is used to evaluate the performance of our lower bound over these groups of networks, and as expected, we note that for networks that deviate more from the Poisson degree distribution, our lower bound weakens. In the case where absolute/full domination of the market-share is desired, under the linear threshold diffusion model, a particular case of our generalized diffusion model, an upper bound on the size of the seed set is derived, and a selection algorithm is developed to show its tightness. This is also extended to the partial market-share situation.

As graphs become larger and more complex, it is becoming nearly impossible to process them without graph partitioning. Graph partitioning creates many subgraphs which can be processed in parallel thus delivering high-speed computation results. However, graph partitioning is a difficult task. In this work, we introduce Thanos, a fast graph partitioning tool which uses the cross-decomposition algorithm that iteratively partitions a graph. It also produces balanced loads of partitions. The algorithm is well suited for parallel GPU programming which leads to fast and high-quality graph partitioning solutions. Experimental results show that we have achieved 30× speedup and 35% better edge cut reduction compared to the CPU version of the popular graph partitioner, METIS, on average.

Recently we proposed a new Mixed-Integer Linear Programming formulation for the Multi-Target Tracking (MTT) problem and used a standard optimization solver to demonstrate its viability [1]. Subsequently, we provided Graphics Processing Unit (GPU) accelerated algorithms for the underlying Multidimensional Assignment Problem (MAP) with decomposable costs or triplet costs using a Lagrangian Relaxation (LR) framework. Here, we present a Dual-Ascent algorithm that provides monotonically increasing lower bounds and converges in a fraction of iterations required for a subgradient scheme. This approach can handle a large number of targets for many time steps with massive parallelism and computational efficiency. The dual-ascent framework decomposes the MAP into a set of Linear Assignment Problems (LAPs) for adjacent time-steps, which can be solved in parallel using the GPU-accelerated method of [2], [3]. The overall dual-ascent algorithm is able to efficiently solve problems with 100 targets and 100 time-frames with high accuracy. We demonstrate the applicability of our new algorithm to MTT by including realistic issues of missed detections and false alarms. Computational results demonstrate the robustness of the algorithm with good MMEP and ITCP scores and solution times for the larger problems in less than 6 seconds.

We study the multiagent unmanned aerial vehicle (UAV) routing problem where a set of UAVs needs to collect information via surveillance of an area of operation. Each UAV is autonomous and does not rely on a reliable communication medium to coordinate with other UAVs. We formulate the problem as a game where UAVs are players and their strategies are the different routes they can take. Our model also incorporates the useful concept of information fusion. This results in a new variant of weighted congestion-type games. We show that the price of anarchy (PoA) of the game is at most 2, irrespective of the number of UAVs and their sensor capabilities. This also validates the empirical results of earlier works. Furthermore, we identify classes of games for the existence of a pure Nash equilibrium. To the best of our knowledge, these are the first such theoretical results in the related literature. Finally, we conduct experimental studies using randomly generated instances with several multiagent UAV routing policies. Our insights are that PoA increases with the congestion level when the same number of UAVs search a smaller area or more UAVs search the same area, and on an average, our proposed policies are less than 10% worse than the centralized optimal for the problem scenarios attempted. Note to Practitioners-UAVs are becoming increasingly popular for information collection tasks in defense and civilian applications alike. When the collection area is large, it is not unusual that a fleet of UAVs is deployed. Routing of a fleet can be performed in a centralized or decentralized manner. Decentralized routing might be the only possibility when centralized situational awareness is not possible due to bandwidth limitations and centralized optimal routes for each UAV in the fleet are too complex to compute. Autonomous solutions have several other advantages, let alone simplicity. For managers of UAV systems, our work provides the first theoretical characterization of how bad could decentralized routing be. Under various scenarios of information fusion, specifically weak and strong, and the attribution of information collected to each UAV of a team, we prove that the fleet will collect at least 50% of the best-centralized solution. Empirically, we show that, in fact, the performance of the fleet is much better and generally not worse than 10% of the best-centralized solution. Hopefully, our routing strategies provide valuable guidance to the practicing engineer or manager of a UAV fleet.

Dynamic affinity load balancing of multi-type tasks on multi-skilled servers, when the service rate of each task type on each of the servers is known and can possibly be different from each other, is an open problem for over three decades. The goal is to do task assignment on servers in a real time manner so that the system becomes stable, which means that the queue lengths do not diverge to infinity in steady state (throughput optimality), and the mean task completion time is minimized (delay optimality). The fluid model planning, Max-Weight, and c-μ -rule algorithms have theoretical guarantees on optimality in some aspects for the affinity problem, but they consider a complicated queueing structure and either require the task arrival rates, the service rates of tasks on servers, or both. In many cases that are discussed in the introduction section, both task arrival rates and service rates of different task types on different servers are unknown. In this work, the Blind GB-PANDAS algorithm is proposed which is completely blind to task arrival rates and service rates. Blind GB-PANDAS uses an exploration-exploitation approach for load balancing. We prove that Blind GB-PANDAS is throughput optimal under arbitrary and unknown distributions for service times of different task types on different servers and unknown task arrival rates. Blind GB-PANDAS desires to route an incoming task to the server with the minimum weighted-workload, but since the service rates are unknown, such routing of incoming tasks is not guaranteed which makes the throughput optimality analysis more complicated than the case where service rates are known. Our extensive experimental results reveal that Blind GB-PANDAS significantly outperforms existing methods in terms of mean task completion time at high loads.

This paper attempts to provide viral marketeers guidance in terms of an investment level that could help capture some desired γ percentage of the market-share by some target time t with a desired level of confidence. To do this, we first introduce a diffusion model for social networks. A distance-dependent random graph is then considered as a model for the underlying social network, which we use to analyze the proposed diffusion model. Using the fact that vertices degrees have an almost Poisson distribution in distance-dependent random networks, we then provide a lower bound on the probability of the event that the time it takes for an idea (or a product, disease, etc.) to dominate a pre-specified γ percentage of a social network (denoted by Rγ) is smaller than some pre-selected target time t > 0, i.e., we find a lower bound on the probability of the event {Rγ ≤ t}. Simulation results performed over a wide variety of networks, including random as well as real-world, are then provided to verify that our bound indeed holds in practice. The Kullback-Leibler divergence measure is used to evaluate performance of our lower bound over these groups of networks, and as expected, we note that for networks that deviate more from the Poisson degree distribution, our lower bound does worse.

This paper discusses efficient parallel algorithms for obtaining strong lower bounds and exact solutions for large instances of the quadratic assignment problem (QAP). Our parallel architecture is comprised of both multicore processors and compute unified device architecture–enabled NVIDIA graphics processing units (GPUs) on the Blue Waters Supercomputing Facility at the University of Illinois at Urbana–Champaign. We propose novel parallelization of the Lagrangian dual ascent algorithm on the GPUs, which is used for solving a QAP formulation based on the level-2 reformulation linearization technique. The linear assignment subproblems in this procedure are solved using our accelerated Hungarian algorithm [Date K, Rakesh N (2016) GPU-accelerated Hungarian algorithms for the linear assignment problem. Parallel Computing 57:52–72.]. We embed this accelerated dual-ascent algorithm in a parallel branch-and-bound scheme and conduct extensive computational experiments on single and multiple GPUs, using problem instances with up to 42 facilities from the quadratic assignment problem library (QAPLIB). The experiments suggest that our GPU-based approach is scalable, and it can be used to obtain tight lower bounds on large QAP instances. Our accelerated branch-and-bound scheme is able to comfortably solve Nugent and Taillard instances (up to 30 facilities) from the QAPLIB, using a modest number of GPUs.

In this paper, we propose an integer programming based model for tracking multiple maneuverable targets in a planar region. The objective function of this model uses both pairs and triplets of observations, which offer more accurate representation for constant velocity targets. Triplet scores in this model are calculated using a novel approach based on cubic spline interpolation, while the data association problem is solved using a specialized multi-dimensional assignment formulation. We show that the spline interpolation based scoring model provides more accurate reconstruction of trajectories, when compared to a naïve model based on linear interpolation, on various randomly generated trajectories, at the expense of modest increase in computation time. The proposed multi-dimensional assignment formulation has nice structural properties and tight linear programming relaxation bound, which results in small computation times.

This paper reports on the utility of social network analysis methods in the data fusion domain. Given fused data that combine multiple intelligence reports from the same environment, social network extraction and high value individual (HVI) identification are of interest. The research on the feasibility of such activities may help not only in methodological developments in network science but also in testing and evaluation of fusion quality. This paper offers a parallel computing-based methodology to extract a social network of individuals from fused data, captured as a cumulative associated data graph (CDG). To obtain the desired social network, two approaches including a hop count weighted and a path salience approach are developed and compared. A supervised learning framework is implemented for parameterizing the extraction algorithms. Parameters utilized in the extraction algorithm consider paths between individuals within the social network, weighing relationships between these individuals based on the count weighted and the path salience calculation methodologies. An overall link strength value is then calculated by aggregating path hop count weights and saliences between unique individual pairs for the hop count weighted and path salience approaches, respectively. Ordered centrality-based HVI lists are obtained from the CDGs constructed from the Sunni criminal thread and Bath'est resurgence threads of the SYNCOIN data set, under various fusion system settings. The reported results shed light on the sensitivity of betweenness, closeness, and degree centrality metrics to fused graph inputs and the role of HVI identification as a test and evaluation tool for fusion process optimization. The computational results demonstrate superiority of path salience approach in identifying HVIs. The insights generated by these approaches and directions for future research are discussed.

Composite services are widely popular for solving complex problems where the required QoS levels are often demanding. The composite service that provides the best utility while meeting the QoS requirements has to be found. This paper proposes a network model where many complementary candidates could be selected for each service class to improve the benefits, while the conventional model limits the selection to a single service candidate or service level per service class. The selection of services step is NP-hard because it can be reduced to a multi-constraint knapsack problem. Yet, the decision has to be reached rapidly so that it does not increase the overall workflow time. Large-size networks and problems with high restriction levels (strong QoS requirements) are the most problematic. Traditional multiple-constrained-shortest-path (MCSP) heuristics are improved in this paper using the novel concept “potential feasibility”. When our modified MCSP heuristic algorithms are compared to the CPLEX solver, one of them demonstrates a significantly smaller average runtime. Further, it provides solutions within a 2.6 percent optimality gap on average for small networks, and a 10 percent optimality gap on average for large networks, regardless of the restriction level. Our algorithm uses a general utility function, not derived from the QoS parameters.

In this paper, we consider an assembly scheduling problem (ASP) with tree-structured precedence constraints. In our problem, there are a number of work centers. Each work center contains a number of machines of the same functionality. The job to be processed via this system is a job with tree-structure precedence constraints. Each operation in the job has a designated work center. We propose a mixed integer linear programming formulation and solve the problem with a Lagrangian relaxation (LR) approach. We solve the subproblems of the LR problem via a heuristic method and generate feasible solutions via a randomized list scheduling algorithm. Near-optimal results are obtained and the computational time is within a few seconds for problems with size up to 20 machines and 300 operations.

Today's social networks are getting larger, and the need to analyze datasets with millions of nodes and billions of edges is not uncommon any more. As a network of social relationships evolves by the addition of new nodes and edges, fast algorithms are desirable for the recomputation of key network measures such as actor centrality. The distributed computing paradigm offers a scalable approach to addressing the recomputation challenge. This paper develops a Map-Reduce implementation of an incremental All-Pairs Shortest Path (APSP) algorithm. The incremental nature of the approach allows for performing minimal work in updating centrality measures, while the Map-Reduce implementation makes it scalable to large data. The key idea of the incremental APSP algorithm [1] is based on the efficient use of past information about the shortest paths between any node and the neighbors of the newly added node. A presented parallelized version of the algorithm relies on a three-step iterative execution of the "map" and "reduce" jobs. Experiences with its implementation are reported in application to a real-world dataset containing 7115 nodes. The experimental runs were performed using the Amazon's EMR service.

In this work, we consider a relatively new representation used in cognitive theory to describe how people understand concepts. This representation is called Conceptual Spaces, and is a geometrical way to represent human thought. Our work relates Conceptual Spaces to Data Fusion, first at Level 1, and later to be extended to Level 2 (as defined by JDL [1]). In this paper, we focus on modeling these Conceptual Spaces as a mathematical program. We then discuss uses and methodologies for Conceptual Spaces in the light of Data Fusion.

Asymmetric/urban warfare, improvised explosive devices (IEDs), and dirty bombs are dominating over conventional warfare, and there is an urgent need to deal with them systematically. Effective strategies of thwarting terrorism continue to be the top priority for international communities. This paper presents a research approach for situation awareness and threat/impact assessment strategies for a genre of UW problems. The approach is based on a formal domain ontology and a scenario authoring and simulation environment. A class of hybrid deductive (model-based) and inductive reasoning approaches are applied to the scenario simulation and performance evaluation studies are conducted. Such an approach can be used for training purposes as well as fusion technology development. An example will be presented

The intent of this paper is to show enhancements in level 2 and 3 fusion capabilities through a new class of graph models and solution strategies. The problem today is not often lack of information, but instead, information overload. Graphs have demonstrated to be a useful framework to represent and analyze large amounts of information. Classical strategies such as Bayesian networks, semantic networks and graph matching are some examples of the power of graphs. We will introduce two different but related graph-based structures that will allow us to span the temporal performance of decision-making processes. Given that most of the high level information fusion problems of interest are NP-Hard, there is a need to separate methodologies between "near real-time" tools and forensic heuristics. With this in mind we will introduce a real-time decision-making tool (INFERD) and a forensic graph matching algorithm (TruST)

Many enterprise areas, such as marketing, variant design, group technology, and cellular manufacturing, require their wide variety of products to be organized into families, which are clusters of similar products. In this paper, we propose a similarity metric for finding the distance between existing products based on bills of materials (BOMs), a class of unordered trees. We show that existing editing operations for unordered trees are not consistent for BOMs, and present a similarity metric based on the symmetric difference. We also provide an polynomial time algorithm for finding the minimum weighted symmetric difference between a pair of unordered trees. The results of the pairwise comparisons are used as a distance metric for a clustering algorithm that groups the BOM trees into product families.