Mixed-Integer Programming for a Class of Robust Submodular Maximization Problems

\(\) We consider robust submodular maximization problems (RSMs), where given a set of \(m\) monotone submodular objective functions, the robustness is with respect to the worst-case (scaled) objective function. The model we consider generalizes two variants of robust submodular maximization problems in the literature, depending on the choice of the scaling vector. On one hand, by … Read more

Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks

Bayesian Networks (BNs) represent conditional probability relations among a set of random variables (nodes) in the form of a directed acyclic graph (DAG), and have found diverse applications in knowledge discovery. We study the problem of learning the sparse DAG structure of a BN from continuous observational data. The central problem can be modeled as … Read more

Integer Programming for Learning Directed Acyclic Graphs from Continuous Data

Learning directed acyclic graphs (DAGs) from data is a challenging task both in theory and in practice, because the number of possible DAGs scales superexponentially with the number of nodes. In this paper, we study the problem of learning an optimal DAG from continuous observational data. We cast this problem in the form of a … Read more

An Exact Method for Constrained Maximization of the Conditional Value-at-Risk of a Class of Stochastic Submodular Functions

We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of … Read more