Goto

Collaborating Authors

 lodi


Learn2Aggregate: Supervised Generation of Chv\'atal-Gomory Cuts Using Graph Neural Networks

arXiv.org Artificial Intelligence

We present $\textit{Learn2Aggregate}$, a machine learning (ML) framework for optimizing the generation of Chv\'atal-Gomory (CG) cuts in mixed integer linear programming (MILP). The framework trains a graph neural network to classify useful constraints for aggregation in CG cut generation. The ML-driven CG separator selectively focuses on a small set of impactful constraints, improving runtimes without compromising the strength of the generated cuts. Key to our approach is the formulation of a constraint classification task which favours sparse aggregation of constraints, consistent with empirical findings. This, in conjunction with a careful constraint labeling scheme and a hybrid of deep learning and feature engineering, results in enhanced CG cut generation across five diverse MILP benchmarks. On the largest test sets, our method closes roughly $\textit{twice}$ as much of the integrality gap as the standard CG method while running 40$% faster. This performance improvement is due to our method eliminating 75% of the constraints prior to aggregation.


ELODI: Ensemble Logit Difference Inhibition for Positive-Congruent Training

arXiv.org Artificial Intelligence

Negative flips are errors introduced in a classification system when a legacy model is updated. Existing methods to reduce the negative flip rate (NFR) either do so at the expense of overall accuracy by forcing a new model to imitate the old models, or use ensembles, which multiply inference cost prohibitively. We analyze the role of ensembles in reducing NFR and observe that they remove negative flips that are typically not close to the decision boundary, but often exhibit large deviations in the distance among their logits. Based on the observation, we present a method, called Ensemble Logit Difference Inhibition (ELODI), to train a classification system that achieves paragon performance in both error rate and NFR, at the inference cost of a single model. The method distills a homogeneous ensemble to a single student model which is used to update the classification system. ELODI also introduces a generalized distillation objective, Logit Difference Inhibition (LDI), which only penalizes the logit difference of a subset of classes with the highest logit values. On multiple image classification benchmarks, model updates with ELODI demonstrate superior accuracy retention and NFR reduction.


Facebook data could predict spread of disease outbreaks says new research on 'social-connectedness'

Daily Mail - Science & tech

Researchers say evaluating the'social-connectedness' of regions using Facebook data could give epidemiologists another tool in judging the spread of infectious disease outside of geographic proximity and population density. The study, which appears in the preprint journal ArXiv and is authored by researchers from New York University, found links between two hotspots of the ongoing COVID-19 pandemic - Westchester County, New York and Lodi province in Italy - to areas with correlating connections on the social media platform, Facebook. Using an equation developed by the same researchers in 2017 called the'Social Connectedness Index' the study was able to make correlations between the spread of COVID-19 from Westchester County and Lodi to geographically disparate locations like ski resorts on Florida and vacation spots in Rimini, Italy near the Adriatic sea. Those correlations remained even after controlling for wealth, population density, and geographic proximity according to researchers. Levels of social connectedness didn't always correlate to the disproportionate spread of the virus, however.