Search

This article initiates the semantic study of distribution-free normal modal logic systems, laying the semantic foundations and anticipating further research in the area. The article explores roughly the same area, though taking a different approach, with a recent article by Bezhanishvili, de Groot, Dmitrieva and Morachini, who studied a distribution-free version of Dunn's Positive Modal Logic (PML). Unlike PML, we consider logics that may drop distribution and which are equipped with both an implication connective and modal operators. We adopt a uniform relational semantics approach, relying on recent results on representation and duality for normal lattice expansions. We prove canonicity and completeness in the relational semantics of the minimal distribution-free normal modal logic, assuming just the K-axiom, as well as of its axiomatic extensions obtained by adding any of the D, T, B, S4 or S5 axioms. Adding distribution can be easily accommodated and, as a side result, we also obtain a new semantic treatment of Intuitionistic Modal Logic.

Centrality metrics have become a popular concept in network science and optimization. Over the years, centrality has been used to assign importance and identify influential elements in various settings, including transportation, infrastructure, biological, and social networks, among others. That said, most of the literature has focused on nodal versions of centrality. Recently, group counterparts of centrality have started attracting scientific and practitioner interest. The identification of sets of nodes that are influential within a network is becoming increasingly more important. This is even more pronounced when these sets of nodes are required to induce a certain motif or structure. In this study, we review group centrality metrics from an operations research and optimization perspective for the first time. This is particularly interesting due to the rapid evolution and development of this area in the operations research community over the last decade. We first present a historical overview of how we have reached this point in the study of group centrality. We then discuss the different structures and motifs that appear prominently in the literature, alongside the techniques and methodologies that are popular. We finally present possible avenues and directions for future work, mainly in three areas: (i) probabilistic metrics to account for randomness along with stochastic optimization techniques; (ii) structures and relaxations that have not been yet studied; and (iii) new emerging applications that can take advantage of group centrality. Our survey offers a concise review of group centrality and its intersection with network analysis and optimization.

We develop a common semantic framework for the interpretation both of $\mathbf{IPC}$, the intuitionistic propositional calculus, and of logics weaker than $\mathbf{IPC}$ (substructural and subintuitionistic logics). This is done by proving a choice-free representation and duality theorem for implicative lattices, which may or may not be distributive. The duality specializes to a choice-free duality for the category of Heyting algebras and a category of topological sorted frames with a ternary sorted relation.

Constructive dualities have been recently proposed for some lattice based algebras and a related project has been outlined by Holliday and Bezhanishvili, aiming at obtaining "choice-free spatial dualities for other classes of algebras [$\ldots$], giving rise to choice-free completeness proofs for non-classical logics''. We present in this article a way to complete the Holliday-Bezhanishvili project (uniformly, for any normal lattice expansion) by recasting recent relational representation and duality results in a choice-free manner. These results have some affinity with the Moshier and Jipsen duality for bounded lattices with quasi-operators, except for aiming at representing operators by relations, extending the J\'{o}nsson-Tarski approach for BAOs, and Dunn's follow up approach for distributive gaggles, to contexts where distribution may not be assumed. To illustrate, we apply the framework to lattices (and their logics) with some form or other of a (quasi)complementation operator, obtaining canonical extensions in relational frames and choice-free dualities for lattices with a minimal, or a Galois quasi-complement, or involutive lattices, including De Morgan algebras, as well as Ortholattices and Boolean algebras, as special cases., Comment: arXiv admin note: text overlap with arXiv:2110.06924

Providing first aid and other supplies (e.g., epi-pens, medical supplies, dry food, water) during and after a disaster is always challenging. The complexity of these operations increases when the transportation, power, and communications networks fail, leaving people stranded and unable to communicate their locations and needs. The advent of emerging technologies like uncrewed autonomous vehicles can help humanitarian logistics providers reach otherwise stranded populations after transportation network failures. However, due to the failures in telecommunication infrastructure, demand for emergency aid can become uncertain. To address the challenges of delivering emergency aid to trapped populations with failing infrastructure networks, we propose a novel robust computational framework for a two-echelon vehicle routing problem that uses uncrewed autonomous vehicles, or drones, for the deliveries. We formulate the problem as a two-stage robust optimization model to handle demand uncertainty. Then, we propose a column-and-constraint generation approach for worst-case demand scenario generation for a given set of truck and drone routes. Moreover, we develop a decomposition scheme inspired by the column generation approach to heuristically generate drone routes for a set of demand scenarios. Finally, we combine the heuristic decomposition scheme within the column-andconstraint generation approach to determine robust routes for both trucks and drones, the time that affected communities are served, and the quantities of aid materials delivered. To validate our proposed computational framework, we use a simulated dataset that aims to recreate emergency aid requests in different areas of Puerto Rico after Hurricane Maria in 2017.

Uncrewed autonomous vehicles (UAVs) have made significant contributions to reconnaissance and surveillance missions in past US military campaigns. As the prevalence of UAVs increases, there has also been improvements in counter-UAV technology that makes it difficult for them to successfully obtain valuable intelligence within an area of interest. Hence, it has become important that modern UAVs can accomplish their missions while maximizing their chances of survival. In this work, we specifically study the problem of identifying a short path from a designated start to a goal, while collecting all rewards and avoiding adversaries that move randomly on the grid. We also provide a possible application of the framework in a military setting, that of autonomous casualty evacuation. We present a comparison of three methods to solve this problem: namely we implement a Deep Q-Learning model, an $\varepsilon$-greedy tabular Q-Learning model, and an online optimization framework. Our computational experiments, designed using simple grid-world environments with random adversaries showcase how these approaches work and compare them in terms of performance, accuracy, and computational time.

During 2020 and 2021, severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) transmission has been increasing amongst the world's population at an alarming rate. Reducing the spread of SARS-CoV-2 and other diseases that are spread in similar manners is paramount for public health officials as they seek to effectively manage resources and potential population control measures such as social distancing and quarantines. By analyzing the United States' county network structure, one can model and interdict potential higher infection areas. County officials can provide targeted information, preparedness training, as well as increase testing in these areas. While these approaches may provide adequate countermeasures for localized areas, they are inadequate for the holistic United States. We solve this problem by collecting coronavirus disease 2019 (COVID-19) infections and deaths from the Center for Disease Control and Prevention{\color{black},} and {\color{black} adjacency between all counties obtained} from the United States Census Bureau. Generalized network autoregressive (GNAR) time series models have been proposed as an efficient learning algorithm for networked datasets. This work fuses network science and operations research techniques to univariately model COVID-19 cases, deaths, and current survivors across the United States' county network structure.

We revisit the problem of Stone duality for lattices with various quasioperators, first studied in [14], presenting a fresh duality result. The new result is an improvement over that of [14] in two important respects. First, the axiomatization of frames in [14] was rather cumbersome and it is now simplified, partly by incorporating Gehrke's proposal [8] of section stability for relations. Second, morphisms are redefined so as to preserve Galois stable (and co-stable) sets and we rely for this, partly again, on Goldblatt's [11] recently proposed definition of bounded morphisms for polarities, though we need to strengthen the definition in order to get a Stone duality result. In studying the dual algebraic structures associated to polarities with relations we demonstrate that stable/co-stable set operators result as the Galois closure of the restriction of classical (though sorted) image operators generated by the frame relations to Galois stable/co-stable sets. This provides a proof, at the representation level, that non-distributive logics can be viewed as fragments of sorted, residuated (poly)modal logics, a research direction initiated in [16,17]., Comment: arXiv admin note: substantial text overlap with arXiv:2109.11597

This article contributes in that it clarifies and indeed completes an approach (initiated by Dunn and this author several years ago and again pursued by the present author over the last three years or so) to the relational semantics of logics that may lack distribution (Dunn's non-distributive gaggles). The approach uses sorted frames with an incidence relation on sorts (polarities), equipped with additional sorted relations, but, in the spirit of Occam's razor principle, it drops the extra assumptions made in the generalized Kripke frames approach, initiated by Gehrke, that the frames be separated and reduced (RS-frames). We show in this article that, despite rejecting the additional frame restrictions, all the main ideas and results of the RS-frames approach relating to the semantics of non-distributive logics are captured in this simpler framework. This contributes in unifying the research field, and, in an important sense, it complements and completes Dunn's gaggle theory project for the particular case of logics that may drop distribution.

As the number of adopted alternative fuel vehicles increases, it is crucial for communities (especially those that are susceptible to hazards) to make evacuation plans that account for such vehicles refueling needs. During emergencies that require preemptive evacuation planning, travelers using alternative fuel vehicles are vulnerable when evacuation routes do not provide access to refueling stations on their way to shelters. In this paper, we formulate and solve a novel seamless evacuation route plan problem, by designing $k$-minimum spanning trees with hop constraints that capture the refueling needs of each $k \in K$ vehicle fuel type on their way to reach a shelter. We develop a branch-and-price algorithm based on a matheuristic column generation approach to solve the evacuation problem. We apply the proposed framework to the Sioux Falls transportation network with existing infrastructure deployment and present numerical experiments. Specifically, we discuss the evacuation travel and refueling times under scenarios of various alternative fuel vehicles driving ranges. Our findings show that the characteristics of each vehicle fuel type, like driving range and the refueling infrastructure topology, play a pivotal role in determining evacuation route plans. This means that an evacuation route could prove unique to a single vehicle fuel type, while being infeasible to the others. Finally, we observe that the driving range constraints could force evacuee vehicles to detour to meet their refueling needs before reaching safety and increase the total evacuation time by 7.32 % in one of the evaluated scenarios.

Humanitarian logistics service providers have two major responsibilities immediately after a disaster: locating trapped people and routing aid to them. These difficult operations are further hindered by failures in the transportation and telecommunications networks, which are often rendered unusable by the disaster at hand. In this work, we propose a two-echelon vehicle routing framework for performing these operations using aerial uncrewed autonomous vehicles (UAVs or drones) to address the issues associated with these failures. In our proposed framework, we assume that ground vehicles cannot reach the trapped population directly, but they can only transport drones from a depot to some intermediate locations. The drones launched from these locations serve to both identify demands for medical and other aids (e.g., epi-pens, medical supplies, dry food, water) and make deliveries to satisfy them. Specifically, we present a decision framework, in which the resulting optimization problem is formulated as a two-echelon vehicle routing problem with trucks as the first echelon vehicles and for the second echelon vehicles, we consider two types of drones. Hotspot drones have the capability of providing a cell phone and internet reception and hence are used to capture demands. Delivery drones are subsequently employed to satisfy the observed demand. To handle demand uncertainty, we decompose the decision problem into two stages: providing telecommunications capabilities in the first stage thereby capturing demand precisely, and satisfying the resulting demands in the second stage. To solve the resulting models, we propose efficient computational approaches by designing a decomposition algorithm with column generation (CG)-based heuristics to identify optimal drone routes.

Recent published work has addressed the Shalqvist correspondence problem for non-distributive logics. The natural question that arises is to identify the fragment of first-order logic that corresponds to logics without distribution, lifting van Benthem's characterization result for modal logic to this new setting. Carrying out this project is the contribution of the present article. The article is intended as a demonstration and application of a project of reduction of non-distributive logics to (sorted) residuated modal logics. The reduction is an application of recent representation results by this author for normal lattice expansions and a generalization of a canonical and fully abstract translation of the language of substructural logics into the language of their companion sorted, residuated modal logics. The reduction of non-distributive logics to sorted modal logics makes the proof of a van Benthem characterization of non-distributive logics nearly effortless, by adapting and reusing existing results, demonstrating the usefulness and suitability of this approach in studying logics that may lack distribution.

The FoundationDB Record Layer is an open source library that provides a record-oriented data store with semantics similar to a relational database implemented on top of FoundationDB, an ordered, transactional key-value store. The Record Layer provides a lightweight, highly extensible way to store structured data. It offers schema management and a rich set of query and indexing facilities, some of which are not usually found in traditional relational databases, such as nested record types, indexes on commit versions, and indexes that span multiple record types. The Record Layer is stateless and built for massive multi-tenancy, encapsulating and isolating all of a tenant's state, including indexes, into a separate logical database. We demonstrate how the Record Layer is used by CloudKit, Apple's cloud backend service, to provide powerful abstractions to applications serving hundreds of millions of users. CloudKit uses the Record Layer to host billions of independent databases, many with a common schema. Features provided by the Record Layer enable CloudKit to provide richer APIs and stronger semantics with reduced maintenance overhead and improved scalability., Comment: 16 pages; updated to reflect reviewer suggestions and fix typos

During natural or anthropogenic disasters, humanitarian organizations face a series of time-sensitive tasks. One of the tasks involves picking up critical resources (e.g., first aid kits, blankets, water) from warehouses and delivering them to the affected people. To successfully deliver these items to the people in need, the organization needs to make decisions that range from the quick acquisition of vehicles from the local market, to the preparation of pickup and delivery schedules and vehicle routes. During crises, the supply of vehicles is often limited, their acquisition cost is steep, and special rental periods are imposed. At the same time, the affected area needs the aid materials as fast as possible, and deliveries must be made within due time. Therefore, it is imperative that the decisions of acquiring, scheduling, and routing of vehicles are made optimally and quickly. In this paper, we consider a variant of a truckload open vehicle routing problem with time windows, which is suitable for modeling vehicle routing operations during a humanitarian crisis. We present two integer linear programming models to formulate the problem, with the first one being an arc-based mixed integer linear programming model. The second model is a path-based integer linear programming model, for which we design two fast path generation algorithms. The first model is solved exactly using the commercial solver, while we propose to solve the second model within a column generation framework. Finally, we perform numerical experiments and compare the results obtained from the two models. We show that the path-based model, when solved with our column generation algorithm, outperforms the arc-based model in terms of solution time without sacrificing the solution quality.

In this paper, we define a new, special second order cone as a type-$k$ second order cone. We focus on the case of $k=2$, which can be viewed as SOCO with an additional {\em complicating variable}. For this new problem, we develop the necessary prerequisites, based on previous work for traditional SOCO. We then develop a primal-dual interior point algorithm for solving a type-2 second order conic optimization (SOCO) problem, based on a family of kernel functions suitable for this type-2 SOCO. We finally derive the following iteration bound for our framework: \[\frac{L^\gamma}{\theta \kappa \gamma} \left[2N \psi\left( \frac{\varrho \left(\tau /4N\right)}{\sqrt{1-\theta}}\right)\right]^\gamma\log \frac{3N}{\epsilon}.\]

In this work, we propose a novel centrality metric, referred to as star centrality, which incorporates information from the closed neighborhood of a node, rather than solely from the node itself, when calculating its topological importance. More specifically, we focus on degree centrality and show that in the complex protein-protein interaction networks it is a naive metric that can lead to misclassifying protein importance. For our extension of degree centrality when considering stars, we derive its computational complexity, provide a mathematical formulation, and propose two approximation algorithms that are shown to be efficient in practice. We portray the success of this new metric in protein-protein interaction networks when predicting protein essentiality in several organisms, including the well-studied Saccharomyces cerevisiae, Helicobacter pylori, and Caenorhabditis elegans, where star centrality is shown to significantly outperform other nodal centrality metrics at detecting essential proteins. We also analyze the average and worst case performance of the two approximation algorithms in practice, and show that they are viable options for computing star centrality in very large-scale protein-protein interaction networks, such as the human proteome, where exact methodologies are bound to be time and memory intensive.

Summary: Both theory and empirical evidence indicate that phylogenies (trees) of different genes (loci) do not display precisely matched topologies. This phylogenetic incongruence is attributed to the reticulated evolutionary history of most species due to meiotic sexual recombination in eukaryotes, or horizontal transfers of genetic materials in prokaryotes. Nonetheless, most genes do display topologically related phylogenies; this implies they form cohesive subsets (clusters). In this work, we compare popular clustering methods, and show how the performance of the normalized cut framework is efficient and statistically accurate when obtaining clusters on the set of gene trees based on the geodesic distance between them over the Billera-Holmes-Vogtmann (BHV) tree space. We proceed to present a computational study on the performance of different clustering methods with and without preprocessing under different distance metrics and using a series of dimension reduction techniques. Results: First, we show using simulated data that indeed the Ncut framework accurately clusters the set of gene trees given a species tree under the coalescent process. We then depict the success of our framework by comparing its performance to other clustering techniques, including k-means and hierarchical clustering. The main computational results can be summarized to the stellar performance of the Ncut framework even without dimension reduction, the similar performance portrayed by k-means and Ncut under most dimension reduction schemes, the utter failure of hierarchical clustering to accurately capture clusters, as well as the significantly better performance of the NJp method, as compared to MLE., Comment: 22 pages, 6 figures and 3 tables