Machine-Assisted Reformulation for MiniZinc
2019 (English)Conference paper, Published paper (Refereed)
Abstract [en]
Model reformulation plays an important role in improving models and reducing search space so that solutions can be found faster. In solving Constraint Satisfaction Problems (CSPs), a model of a CSP may be solved rapidly, while a different model may take excessively long to solve. The efficient solution of CSP is significant in real-world applications, such as air traffic management, resource allocation, production scheduling, and bioinformatics. Many technologies such as constraint programming (CP), hybrid technologies, mixed integer programming (MIP), constraint-based local search (CBLS), boolean satisfiability (SAT) could have different solvers and backends to solve the real-time problems. 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. The verification tool, Isabelle, will be used to verify the correctness of reformulations. We plan to apply recent results in formal methods such as program analysis and synthesis to provide semi-automated frameworks for model analysis. In this paper, we identify the challenges, implement frameworks, and evaluate our experimental results in reformulations for future research.
Place, publisher, year, edition, pages
2019.
Keywords [en]
formal methods, implied constraint, reformula- tions, constraint programming, optimisation, modelling languages
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:uu:diva-392599OAI: oai:DiVA.org:uu-392599DiVA, id: diva2:1349070
Conference
IEEE International Workshops on Foundations and Applications of Self* Systems (FAS*2019), Umeå, Sweden, 16-20 June 2019
2019-09-062019-09-062019-09-16Bibliographically approved