Bistra Dilkina

Bistra Dilkina

Auto-generated profile, based on publicly available information

Bistra Dilkina

University of Southern California

Research Focus & Metrics

Academic Career Length

23Years (2004-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 December 2017 in Applied Energy
Verified
Journal Article
Closed access
CRCaleb Robinson
Caleb Robinson
BDBistra Dilkina
Bistra Dilkina
JHJeffrey Hubbs
Jeffrey Hubbs
WZWenwen Zhang
Wenwen Zhang
SGSubhrajit Guhathakurta
Subhrajit Guhathakurta
RPRam M. Pendyala
Ram M. Pendyala

17 July 2019 in Proceedings of the AAAI Conference on Artificial Intelligence
Verified
Journal Article
Closed access
PDF file
BWBryan Wilder
Bryan Wilder
BDBistra Dilkina
Bistra Dilkina
MTMilind Tambe
Milind Tambe
Creating impact in real-world settings requires artificial intelligence techniques to span the full pipeline from data, to predictive models, to decisions. These components are typically approached separately: a machine learning model is first trained via a measure of predictive accuracy, and then its predictions are used as input into an optimization algorithm which produces a decision. However, the loss function used to train the model may easily be misaligned with the end goal, which is to make the best decisions possible. Hand-tuning the loss function to align with optimization is a difficult and error-prone process (which is often skipped entirely).We focus on combinatorial optimization problems and introduce a general framework for decision-focused learning, where the machine learning model is directly trained in conjunction with the optimization algorithm to produce highquality decisions. Technically, our contribution is a means of integrating common classes of discrete optimization problems into deep learning or other predictive models, which are typically trained via gradient descent. The main idea is to use a continuous relaxation of the discrete problem to propagate gradients through the optimization procedure. We instantiate this framework for two broad classes of combinatorial problems: linear programs and submodular maximization. Experimental results across a variety of domains show that decisionfocused learning often leads to improved optimization performance compared to traditional methods. We find that standard measures of accuracy are not a reliable proxy for a predictive model’s utility in optimization, and our method’s ability to specify the true goal as the model’s training objective yields substantial dividends across a range of decision problems.

21 August 2019 in Communications of the ACM
Verified
Journal Article
Open access
PDF file
CGCarla Gomes
Carla Gomes
TDThomas Dietterich
Thomas Dietterich
CBChristopher Barrett
Christopher Barrett
JCJon Conrad
Jon Conrad
BDBistra Dilkina
Bistra Dilkina
MZMary Lou Zeeman
Mary Lou Zeeman
Computer and information scientists join forces with other fields to help solve societal and environmental challenges facing humanity, in pursuit of a sustainable future.

24 August 2014
Verified
Conference Paper
Open access
EKElias Boutros Khalil
Elias Boutros Khalil
BDBistra Dilkina
Bistra Dilkina
LSLe Song
Le Song
How can we optimize the topology of a networked system to bring a flu under control, propel a video to popularity, or stifle a network malware in its infancy? Previous work on information diffusion has focused on modeling the diffusion dynamics and selecting nodes to maximize/minimize influence. Only a paucity of recent studies have attempted to address the network modification problems, where the goal is to either facilitate desirable spreads or curtail undesirable ones by adding or deleting a small subset of network nodes or edges. In this paper, we focus on the widely studied linear threshold diffusion model, and prove, for the first time, that the network modification problems under this model have supermodular objective functions. This surprising property allows us to design efficient data structures and scalable algorithms with provable approximation guarantees, despite the hardness of the problems in question. Both the time and space complexities of our algorithms are linear in the size of the network, which allows us to experiment with millions of nodes and edges. We show that our algorithms outperform an array of heuristics in terms of their effectiveness in controlling diffusion processes, often beating the next best by a significant margin.

20 June 2018
Verified
Conference Paper
Open access
PDF file
CRCaleb Robinson
Caleb Robinson
BDBistra Dilkina
Bistra Dilkina
Human migration is a type of human mobility, where a trip involves a person moving with the intention of changing their home location. Predicting human migration as accurately as possible is important in city planning applications, international trade, spread of infectious diseases, conservation planning, and public policy development. Traditional human mobility models, such as gravity models or the more recent radiation model, predict human mobility flows based on population and distance features only. These models have been validated on commuting flows, a different type of human mobility, and are mainly used in modeling scenarios where large amounts of prior ground truth mobility data are not available. One downside of these models is that they have a fixed form and are therefore not able to capture more complicated migration dynamics. We propose machine learning models that are able to incorporate any number of exogenous features, to predict origin/destination human migration flows. Our machine learning models outperform traditional human mobility models on a variety of evaluation metrics, both in the task of predicting migrations between US counties as well as international migrations. In general, predictive machine learning models of human migration will provide a flexible base with which to model human migration under different what-if conditions, such as potential sea level rise or population growth scenarios.

1 August 2017
Verified
Conference Paper
Closed access
EKElias B. Khalil
Elias B. Khalil
BDBistra Dilkina
Bistra Dilkina
GNGeorge L. Nemhauser
George L. Nemhauser
SAShabbir Ahmed
Shabbir Ahmed
YSYufen Shao
Yufen Shao
``Primal heuristics'' are a key contributor to the improved performance of exact branch-and-bound solvers for combinatorial optimization and integer programming. Perhaps the most crucial question concerning primal heuristics is that of at which nodes they should run, to which the typical answer is via hard-coded rules or fixed solver parameters tuned, offline, by trial-and-error. Alternatively, a heuristic should be run when it is most likely to succeed, based on the problem instance's characteristics, the state of the search, etc. In this work, we study the problem of deciding at which node a heuristic should be run, such that the overall (primal) performance of the solver is optimized. To our knowledge, this is the first attempt at formalizing and systematically addressing this problem. Central to our approach is the use of Machine Learning (ML) for predicting whether a heuristic will succeed at a given node. We give a theoretical framework for analyzing this decision-making process in a simplified setting, propose a ML approach for modeling heuristic success likelihood, and design practical rules that leverage the ML models to dynamically decide whether to run a heuristic at each node of the search tree. Experimentally, our approach improves the primal performance of a state-of-the-art Mixed Integer Programming solver by up to 6% on a set of benchmark instances, and by up to 60% on a family of hard Independent Set instances.