CRII: RI: Stochastic Optimization via Embedding Counting as Optimization with Randomized Constraints

Purdue University, West Lafayette IN

Investigators

Abstract

Stochastic optimization is a problem-solving method that makes use of randomness in the world. Randomness arises naturally in many applications ranging from economics, operational research, and artificial intelligence. Take the network design problem for wild-life animal protection as an example. The movements of wild-life animals can be described using a stochastic function. The goal is to decide optimal protection measures that maximize animals' dispersal in expectation. Solving the network design problem, a special case of stochastic optimization, would help ecologists and government officials to prioritize environmental protection plans wisely, which is meaningful in securing our sustainable future. Nevertheless, stochastic optimization is highly intractable because it combines two intractable problems, one of which is the inner counting problem to compute the expectation across exponentially many probabilistic outcomes, the other of which is the outer optimization problem to search for the optimal policy that maximizes the expectation. This proposal focuses on expanding a novel approach, Embedding Counting as Optimization with Randomized Constraints (ECOR), to solve stochastic optimization problems. ECOR approximates intractable counting sub-problems with optimization queries subject to randomized parity constraints, which are in turn embedded into the global optimization task. As a result, the stochastic optimization inference can be reduced to a single joint optimization of a polynomial size of the original problem with provable guarantees. This research focuses on expanding ECOR into a family of approaches that is practical for machine learning and network design applications. The limitation of the current ECOR algorithm is mainly due to its implementation as a single, large constraint program, in addition to the long parity constraints, which provide strong probabilistic guarantees but are challenging computationally. The key principle to scale up ECOR is to take an integrated view of the inner counting and the outer maximization problem. The algorithmic contribution will be driven by the intuitions gained from working on several real-world problems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.