Nested Constraint Programs
Geoffrey Chu, Peter J. Stuckey · 2014
Abstract. Many real world discrete optimization problems are express-ible as nested problems where we solve one optimization or satisfac-tion problem as a subproblem of a larger meta problem. Nested prob-lems include many important problem classes such as: stochastic con-straint satisfaction/optimization, quantified constraint satisfaction/op-timization and minimax problems. In this paper we define a new class of problems called nested constraint programs (NCP) which include the previously mentioned problem classes as special cases, and describe a search-based CP solver for solving NCP’s. We briefly discuss how no-good learning can be used to significantly speedup such an NCP solver. We show that the new solver can be significantly faster than existing solvers for the special cases of stochastic/quantified CSP/COP’s, and that it can solve new types of problems which cannot be solved with existing solvers. 1