Theory and Algorithms Commons^™

The Multi-Vehicle Cycle Inventory Routing Problem: Formulation And A Metaheuristic Approach, Vincent F. Yu, Audrey Tedja Widjaja, Aldy Gunawan, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

This paper presents a new variant of the Multi-Vehicle Cyclic Inventory Routing Problem (MV-CIRP) which aims to determine a subset of customers to be visited, the appropriate number of vehicles used, and the corresponding cycle time and route sequence, such that the total cost (e.g. transportation, inventory, and rewards) is minimized. The MV-CIRP is formulated as a mixed-integer nonlinear programming model. We propose a Simulated Annealing (SA) based algorithm to solve the problem. SA is first tested on the available benchmark Single-Vehicle CIRP (SV-CIRP) instances and compared to the state-of-the-art algorithms. SA is then tested on the benchmark MV-CIRP instances …

Rotating Scatter Mask For Directional Radiation Detection And Imaging, Darren Holland, Robert Olesen, Larry Burggraf, Buckley O'Day, James E. Bevins

AFIT Patents

A radiation imaging system images a distributed source of radiation from an unknown direction by rotating a scatter mask around a central axis. The scatter mask has a pixelated outer surface of tangentially oriented, flat geometric surfaces that are spherically varying in radial dimension that corresponds to a discrete amount of attenuation. Rotation position of the scatter mask is tracked as a function of time. Radiation counts from gamma and/or neutron radiation are received from at least one radiation detector that is positioned at or near the central axis. A rotation-angle dependent detector response curve (DRC) is generated based on …

Counting And Sampling Small Structures In Graph And Hypergraph Data Streams, Themistoklis Haris

Dartmouth College Undergraduate Theses

In this thesis, we explore the problem of approximating the number of elementary substructures called simplices in large k-uniform hypergraphs. The hypergraphs are assumed to be too large to be stored in memory, so we adopt a data stream model, where the hypergraph is defined by a sequence of hyperedges.

First we propose an algorithm that (ε, δ)-estimates the number of simplices using O(m^1+1/k / T) bits of space. In addition, we prove that no constant-pass streaming algorithm can (ε, δ)- approximate the number of simplices using less than O( m ^1+1/k / T ) bits of space. Thus …

Object Manipulation With Modular Planar Tensegrity Robots, Maxine Perroni-Scharf

Dartmouth College Undergraduate Theses

This thesis explores the creation of a novel two-dimensional tensegrity-based mod- ular system. When individual planar modules are linked together, they form a larger tensegrity robot that can be used to achieve non-prehensile manipulation. The first half of this dissertation focuses on the study of preexisting types of tensegrity mod- ules and proposes different possible structures and arrangements of modules. The second half describes the construction and actuation of a modular 2D robot com- posed of planar three-bar tensegrity structures. We conclude that tensegrity modules are suitably adapted to object manipulation and propose a future extension of the modular 2D …

The “Knapsack Problem” Workbook: An Exploration Of Topics In Computer Science, Steven Cosares

Open Educational Resources

This workbook provides discussions, programming assignments, projects, and class exercises revolving around the “Knapsack Problem” (KP), which is widely a recognized model that is taught within a typical Computer Science curriculum. Throughout these discussions, we use KP to introduce or review topics found in courses covering topics in Discrete Mathematics, Mathematical Programming, Data Structures, Algorithms, Computational Complexity, etc. Because of the broad range of subjects discussed, this workbook and the accompanying spreadsheet files might be used as part of some CS capstone experience. Otherwise, we recommend that individual sections be used, as needed, for exercises relevant to a course in …

Modeling And Solving The Outsourcing Risk Management Problem In Multi-Echelon Supply Chains, Arian A. Nahangi

Master's Theses

Worldwide globalization has made supply chains more vulnerable to risk factors, increasing the associated costs of outsourcing goods. Outsourcing is highly beneficial for any company that values building upon its core competencies, but the emergence of the COVID-19 pandemic and other crises have exposed significant vulnerabilities within supply chains. These disruptions forced a shift in the production of goods from outsourcing to domestic methods.

This paper considers a multi-echelon supply chain model with global and domestic raw material suppliers, manufacturing plants, warehouses, and markets. All levels within the supply chain network are evaluated from a holistic perspective, calculating a total …

Solving Chromatic Number With Quantum Search And Quantum Counting, David Lutze

Master's Theses

This thesis presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2^n/2n²(log2n)²). This is an improvement over the best known algorithm, with a run time of 2ⁿn^O(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can …

First Train Timetabling And Bus Service Bridging In Intermodal Bus-And-Train Transit Networks, Liujiang Kang, Hao Li, Huijun Sun, Jianjun Wu, Zhiguang Cao, Nsabimana Buhigiro

Research Collection School Of Computing and Information Systems

Subway system is the main mode of transportation for city dwellers and is a quite signif-icant backbone to a city's operations. One of the challenges of subway network operation is the scheduling of the first trains each morning and its impact on transfers. To deal with this challenge, some cities (e.g. Beijing) use bus 'bridging' services, temporarily substitut -ing segments of the subway network. The present paper optimally identifies when to start each train and bus bridging service in an intermodal transit network. Starting from a mixed integer nonlinear programming model for the first train timetabling problem, we linearize and …

Self-Adaptive Graph Traversal On Gpus, Mo Sha, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

GPU’s massive computing power offers unprecedented opportunities to enable large graph analysis. Existing studies proposed various preprocessing approaches that convert the input graphs into dedicated structures for GPU-based optimizations. However, these dedicated approaches incur significant preprocessing costs as well as weak programmability to build general graph applications. In this paper, we introduce SAGE, a self-adaptive graph traversal on GPUs, which is free from preprocessing and operates on ubiquitous graph representations directly. We propose Tiled Partitioning and Resident Tile Stealing to fully exploit the computing power of GPUs in a runtime and self-adaptive manner. We also propose Sampling-based Reordering to further …

A Hybrid Stochastic-Deterministic Minibatch Proximal Gradient Method For Efficient Optimization And Generalization, Pan Zhou, Xiao-Tong Yuan, Lin Zhouchen, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Despite the success of stochastic variance-reduced gradient (SVRG) algorithms in solving large-scale problems, their stochastic gradient complexity often scales linearly with data size and is expensive for huge data. Accordingly, we propose a hybrid stochastic-deterministic minibatch proximal gradient (HSDMPG) algorithm for strongly convex problems with linear prediction structure, e.g. least squares and logistic/softmax regression. HSDMPG enjoys improved computational complexity that is data-size-independent for large-scale problems. It iteratively samples an evolving minibatch of individual losses to estimate the original problem, and can efficiently minimize the sampled subproblems. For strongly convex loss of n components, HSDMPG attains an -optimization-error within O κ …

Set Team Orienteering Problem With Time Windows, Aldy Gunawan, Vincent F. Yu, Andros Nicas Sutanto, Panca Jodiawan

Research Collection School Of Computing and Information Systems

This research introduces an extension of the Orienteering Problem (OP), known as Set Team Orienteering Problem with Time Windows (STOPTW), in which customers are first grouped into clusters. Each cluster is associated with a profit that will be collected if at least one customer within the cluster is visited. The objective is to find the best route that maximizes the total collected profit without violating time windows and time budget constraints. We propose an adaptive large neighborhood search algorithm to solve newly introduced benchmark instances. The preliminary results show the capability of the proposed algorithm to obtain good solutions within …

Fake News Analysis And Graph Classification On A Covid-19 Twitter Dataset, Kriti Gupta

Master's Projects

Earlier researches have showed that the spread of fake news through social media can have a huge impact to society and also to individuals in an extremely negative way. In this work we aim to study the spread of fake news compared to real news in a social network. We do that by performing classical social network analysis to discover various characteristics, and formulate the problem as a binary classification, where we have graphs modeling the spread of fake and real news. For our experiments we rely on how news are propagated through a popular social media services such as …

Improving Additional Adversarial Robustness For Classification, Michael Guo

McKelvey School of Engineering Graduate Student Theses & Dissertations

Although neural networks have achieved remarkable success on classification, adversarial robustness is still a significant concern. There are now a series of approaches for designing adversarial examples and methods to defending against them. This paper consists of two projects. In our first work, we propose an approach by leveraging cognitive salience to enhance additional robustness on top of these methods. Specifically, for image classification, we split an image into the foreground (salient region) and background (the rest) and allow significantly larger adversarial perturbations in the background to produce stronger attacks. Furthermore, we show that adversarial training with dual-perturbation attacks yield …

Reinforcement Learning For Realistic Robotic Training: A Survey, Andres Jaramillo

Honors Scholar Theses

Reinforcement learning is a widely popular topic that has resulted in a plethora of

research papers and interest from academia and industry. When applied with robotics,

the field has showed some promising signs that robots can achieve levels of complex

cognitive abilities rivaling humans, but the goal of creating sapient robots is far from

a reality due to many challenges involved with training robots in a real world setting.

This paper will provide a survey regarding the keys towards realistic robotic training by

detailing the challenges and overviewing the reinforcement learning solutions involved

in getting a robot to think like …

Semi-Supervised Spatial-Temporal Feature Learning On Anomaly-Based Network Intrusion Detection, Huy Mai

Computer Science and Computer Engineering Undergraduate Honors Theses

Due to a rapid increase in network traffic, it is growing more imperative to have systems that detect attacks that are both known and unknown to networks. Anomaly-based detection methods utilize deep learning techniques, including semi-supervised learning, in order to effectively detect these attacks. Semi-supervision is advantageous as it doesn't fully depend on the labelling of network traffic data points, which may be a daunting task especially considering the amount of traffic data collected. Even though deep learning models such as the convolutional neural network have been integrated into a number of proposed network intrusion detection systems in recent years, …

Data-Driven Approaches To Complex Materials: Applications To Amorphous Solids, Dil Kumar Limbu

Dissertations

While conventional approaches to materials modeling made significant contributions and advanced our understanding of materials properties in the past decades, these approaches often cannot be applied to disordered materials (e.g., glasses) for which accurate total-energy functionals or forces are either not available or it is infeasible to employ due to computational complexities associated with modeling disordered solids in the absence of translational symmetry. In this dissertation, a number of information-driven probabilistic methods were developed for the structural determination of a range of materials including disordered solids to transition metal clusters. The ground-state structures of transition-metal clusters of iron, nickel, and …

A Comparison Of Word Embedding Techniques For Similarity Analysis, Tyler Gerth

Computer Science and Computer Engineering Undergraduate Honors Theses

There have been a multitude of word embedding techniques developed that allow a computer to process natural language and compare the relationships between different words programmatically. In this paper, similarity analysis, or the testing of words for synonymic relations, is used to compare several of these techniques to see which performs the best. The techniques being compared all utilize the method of creating word vectors, reducing words down into a single vector of numerical values that denote how the word relates to other words that appear around it. In order to get a holistic comparison, multiple analyses were made, with …

Improving Bayesian Graph Convolutional Networks Using Markov Chain Monte Carlo Graph Sampling, Aneesh Komanduri

Computer Science and Computer Engineering Undergraduate Honors Theses

In the modern age of social media and networks, graph representations of real-world phenomena have become incredibly crucial. Often, we are interested in understanding how entities in a graph are interconnected. Graph Neural Networks (GNNs) have proven to be a very useful tool in a variety of graph learning tasks including node classification, link prediction, and edge classification. However, in most of these tasks, the graph data we are working with may be noisy and may contain spurious edges. That is, there is a lot of uncertainty associated with the underlying graph structure. Recent approaches to modeling uncertainty have been …

Trunctrimmer: A First Step Towards Automating Standard Bioinformatic Analysis, Z. Gunner Lawless, Dana Dittoe, Dale R. Thompson, Steven C. Ricke

Computer Science and Computer Engineering Undergraduate Honors Theses

Bioinformatic analysis is a time-consuming process for labs performing research on various microbiomes. Researchers use tools like Qiime2 to help standardize the bioinformatic analysis methods, but even large, extensible platforms like Qiime2 have drawbacks due to the attention required by researchers. In this project, we propose to automate additional standard lab bioinformatic procedures by eliminating the existing manual process of determining the trim and truncate locations for paired end 2 sequences. We introduce a new Qiime2 plugin called TruncTrimmer to automate the process that usually requires the researcher to make a decision on where to trim and truncate manually after …

The Generalized Riemann Hypothesis And Applications To Primality Testing, Peter Hall

University Scholar Projects

The Riemann Hypothesis, posed in 1859 by Bernhard Riemann, is about zeros
of the Riemann zeta-function in the complex plane. The zeta-function can be repre-
sented as a sum over positive integers n of terms 1/ns when s is a complex number
with real part greater than 1. It may also be represented in this region as a prod-
uct over the primes called an Euler product. These definitions of the zeta-function
allow us to find other representations that are valid in more of the complex plane,
including a product representation over its zeros. The Riemann Hypothesis says that
all …