SILO



The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group

3M

with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Split Cuts for Two-Stage Stochastic Integer Programs and Tracking Influence in Dynamic Social Networks

Merve Bodur and Prof. Rebecca Willett,

Date and Time: Nov 20, 2013 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building

Abstract:

Merve Bodur
Stochastic programming is a way of dealing with uncertainty in the optimization problems. We consider two-stage stochastic programs with integer first stage and continuous second stage. It means that the decision maker must take some integer decisions before the uncertainty is revealed, then can observe the realizations and take recourse actions.
These problems yield to large-scale mixed integer programs, which are called as extensive form. The most common solution approach is Benders decomposition (also known as L-shaped method) which is a cutting plane algorithm. Benders cuts project out second stage variables from the LP relaxation of extensive form and reformulate the problem in the space of first stage variables. Consequently, they do not use the fact that the first stage variables are integer. We try to get advantage of this integer information by incorporating the integrality into the projection in order to generate stronger cutting planes to improve LP relaxations. Specifically, we apply simple disjunctions in the cut generator linear programs to obtain split cuts, which are at least as good as Benders cuts.

Rebecca Willett
Cascading chains of interactions are a salient feature of many
real-world social networks. One particularly well-studied example is
social reciprocity between two people, but more distributed series of
interactions are also possible: kindnesses are "paid forward'', gang
violence begets retaliations, nation-state conflicts are accompanied
by proxy wars, and chain emails are regularly forwarded. This talk
addresses the challenge of tracking how the actions within a social
network stimulate or influence future actions. We adopt an online
learning framework well-suited to streaming data, using a multivariate
Hawkes model to encapsulate autoregressive features of observed events
within the social network. Recent work on online learning in dynamic
environments is leveraged not only to exploit the dynamics within the
social network, but also to track that network structure as it
evolves. Regret bounds and experimental results demonstrate that the
proposed method (with no prior knowledge of the network) performs
nearly as well as would be possible with full knowledge of the
network. Joint work with Eric Hall.