Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Reformulations of Constraint Satisfaction Problems: A Survey
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.ORCID iD: 0000-0003-2106-7186
2020 (English)Report (Other academic)
Abstract [en]

Model reformulation plays an important role in improving models, reducing search space so that solutions can be found faster. Hence we categorise model reformulation into three types: a model is reformulated to another model with the same modelling language, a model with non constraint programming standard types is compiled to another model with constraint programming (CP) standard types, and a model is converted to Boolean satisfiability problem (SAT), Mixed-integer programming (MIP), Satisfiability modulo theories (SMT), and Mixed integer linear programming (MILP). Based on these categories, reformulation and compilation could be used in different ways to improve a model such as automatic reformulations, semi-automatic reformulations, MIP to constraint programming, implied constraints, set Constraint Satisfaction Problems (CSPs) to CSPs, string variables to CSP without string variables, symmetry breaking, pre-computation, non-binary to binary translations, and reformulations into SAT, MILP, and SMT. CP is a pervasive and highly successful technology for solving a wide variety of constraint satisfaction problems such as air traffic management, resource allocation, transportation, scheduling, and so on. Model reformulation can have a significant impact on solving time. Techniques from formal methods will be used to provide machine assistance for MiniZinc, which is the high-level modelling language to model CSPs. In this survey, we present an overview of reformulation focusing on the contributions made in the area of reformulation of CSPs where significant performance improvements have been achieved. Our contributions are as follows: propose criteria and types that categorise model reformulations; we systematically unify and organise the vast literature; contrast and compare different categories of the reformulation for solving CSPs; propose a compiler for counter automata reformulation; ultimately, we propose a plan for future work, we identify the challenges, implement frameworks, and evaluate our experimental results of model reformulations.

Place, publisher, year, edition, pages
2020. , p. 34
Keywords [en]
Constraint programming, optimisation, model reformulation
National Category
Computer and Information Sciences Computer Sciences
Research subject
Computing Science
Identifiers
URN: urn:nbn:se:uu:diva-401115OAI: oai:DiVA.org:uu-401115DiVA, id: diva2:1382884
Available from: 2020-01-06 Created: 2020-01-06 Last updated: 2021-04-06Bibliographically approved

Open Access in DiVA

phuc-reformulation(327 kB)1008 downloads
File information
File name FULLTEXT01.pdfFile size 327 kBChecksum SHA-512
6c521017e5b97f9ee5bfb2fc8981a88a8d7ff6e3c5e22d1bc9fa31ee6f28cf6adb78b33dd0937adbd5999ae01813681dfd3f188e3901214cdd330f9d9ed73ca1
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Vo, Huu-Phuc
By organisation
Computing Science
Computer and Information SciencesComputer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 1008 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 1446 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf