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

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.