Nested constraint programs

Geoffrey Chu, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

5 Citations (Scopus)

Abstract

Many real world discrete optimization problems are expressible as nested problems where we solve one optimization or satisfaction problem as a subproblem of a larger meta problem. Nested problems include many important problem classes such as: stochastic constraint satisfaction/ optimization, quantified constraint satisfaction/optimization 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 nogood 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.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication20th International Conference, CP 2014 Lyon, France, September 8-12, 2014 Proceedings
EditorsBarry O’Sullivan
Place of PublicationCham Switzerland
PublisherSpringer
Pages240-255
Number of pages16
ISBN (Electronic)9783319104287
ISBN (Print)9783319104270
DOIs
Publication statusPublished - 2014
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2014 - Lyon, France
Duration: 8 Sep 201412 Sep 2014
Conference number: 20th
http://cp2014.a4cp.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8656
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2014
Abbreviated titleCP 2014
CountryFrance
CityLyon
Period8/09/1412/09/14
Internet address

Cite this