Stochastic Packing Integer Programming with a Few Queries

Many discrete optimization problems that appear in machine learning applications are expressed as packing integer programming problems in which the objective vector is stochastic.
Here, we consider a situation that we can reveal the value of an entry of the objective vector by conducting a query. The task is to find a good solution by conducting a small number of queries. This problem has applications in kidney exchange and the online dating system.

In this study, we propose adaptive and non-adaptive algorithms for the stochastic packing integer programming problem, and provide a general technique, based on the LP-duality and counting, to analyze the performance of the algorithms. By using this technique, we obtain non-trivial results for stochastic matching problems, matroid problems, and stable set problem in some graph classes.

This is a joint work with Yutaro Yamaguchi (Osaka University, Japan)