Software for Optimisation
We have a github page where we archive various pieces of software.
An OscaR/CBLS Backend for MiniZinc
Gustav Björdal has written a MiniZinc backend based on OscaR/CBLS, called fzn-oscar-cbls [Bjö14]. It has been expanded [BMFP15] with Jean-Noël Monette and other new features are described in [BFPS19, BFP19, BFPST18]:
- The source code is part of the OscaR repository (oscar-fzn-dev branch).
- To install fzn-oscar-cbls, download a zipped file. Assuming you have Java installed, you can then run the backend via the command line on Unix/Linux/macOS as follows:
java -Xmx8G -jar lib/oscar-fzn-cbls.jar <command-line arguments>
The backend won a silver medal at the MiniZinc Challenge 2021, MiniZinc Challenge 2020, bronze medals at the MiniZinc Challenge 2019, MiniZinc Challenge 2018, and MiniZinc Challenge 2017, was the Best Local-Search Solver at the MiniZinc Challenge 2016, and won an Honourable Mention at the MiniZinc Challenge 2015.
- [BFPS19] G. Björdal, P. Flener, J. Pearson, and P. J. Stuckey. Exploring declarative local-search neighbourhoods with constraint programming. In: T. Schiex and S. de Givry (editors), CP 2019. Lecture Notes in Computer Science, volume 11802, pages 37-52. Springer, 2019. (PDF) (Preprint)
- [BFP19] G. Björdal, P. Flener, and J. Pearson. Generating compound moves in local search by hybridisation with complete search. In: L.-M. Rousseau and K. Stergiou (editors), CP-AI-OR 2019. Lecture Notes in Computer Science, volume 11494, pages 95-111. Springer, 2019. (PDF) (Preprint)
- [BFPST18] G. Björdal, P. Flener, J. Pearson, P.J. Stuckey, and G. Tack. Declarative local-search neighbourhoods in MiniZinc. In: M. Alamaniotis, J.-M. Lagniez, and A. Lallouet (editors), ICTAI 2018, pages 98-105. IEEE Computer Society, 2018. (PDF) (Preprint)
- [BMFP15] G. Björdal, J.-N. Monette, P. Flener, and J. Pearson. A constraint-based local search backend for MiniZinc. Constraints, journal fast track of CP-AI-OR 2015, 20(3):325-345, July 2015. (PDF) (Preprint)
- [Bjö14] G. Björdal: The First Constraint-Based Local Search Backend for MiniZinc. Bachelor Thesis in Computer Science, Report IT 14 066, Faculty of Science and Technology. Uppsala University, Sweden, 2014. (PDF)
Tabling for MiniZinc
Jip Dekker has added support for presolving through tabling of designated constraint predicates to the toolchain of the MiniZinc constraint-based modelling language for discrete optimisation, as described in [DBCFM17, Dek16].
- [DBCFM17] J. J. Dekker, G. Björdal, M. Carlsson, P. Flener, and J.-N. Monette. Auto-tabling for subproblem presolving in MiniZinc. Constraints, journal fast track of CP-AI-OR 2017, 22(4):512-529, October 2017. (PDF, open access)
- [Dek16] J. Dekker. Sub-Problem Pre-Solving in MiniZinc. Master Thesis, Report IT 16082, Faculty of Science and Technology, Uppsala University, Sweden, October 2016. (PDF)
Bounded-Length String Variables and Constraints for Gecode and MiniZinc
Joseph Scott has extended the Gecode CP solver with bounded-length string variables and constraints, as described in [SFPS17, Sco16], and written a FlatZinc parser interfacing the extended Gecode with the string extension described in [AFPSST17] of the MiniZinc constraint-based modelling language for discrete optimisation.
- [SFPS17] J. Scott, P. Flener, J. Pearson, and Ch. Schulte. Design and implementation of bounded-length sequence variables. In: D. Salvagnin and M. Lombardi (editors), CP-AI-OR 2017. Lecture Notes in Computer Science, volume 10335, pages 51-67. Springer, 2017. (PDF) (Preprint)
- [AFPSST17] R. Amadini, P. Flener, J. Pearson, J. Scott, P. Stuckey, and G. Tack. MiniZinc with Strings. In: M. Hermenegildo and P. Lopez-Garcia (editors), LOPSTR 2016 Post-Proceedings. Lecture Notes in Computer Science, volume 10184, pages 52-67. Springer, 2017. (PDF) (Preprint) (superseded Pre-Proceedings version)
- [Sco16] J. Scott. Other Things Besides Number: Abstraction, Constraint Propagation, and String Variable Types. PhD thesis, Department of Information Technology, Uppsala University, Sweden, March 2016. (PDF)
The Indexical Compiler
The Indexical Compiler is a program described in [MFP12] that translates indexical code into propagators for several constraint programming solvers. It is written and maintained by Jean-Noël Monette:
- The compiler (a jar file, including the manual): indexicals.jar (800 KB).
- The source code is maintained on Bitbucket.
- The manual: manual.pdf (not up-to-date).
- [MFP12] J.-N. Monette, P. Flener, and J. Pearson. Towards solver-independent propagators. In: M. Milano (editor), CP 2012, pages 544-560. Lecture Notes in Computer Science, volume 7514. © Springer, 2012. (PDF) (Preprint)
Automated Auxiliary Variable Elimination through On-the-Fly Propagator Generation
The implementation of this novel approach presented in [MFP15] is available on Bitbucket, including the source code and everything needed to reproduce the experiments. For any question or feedback feel free to contact Jean-Noël Monette.
- [MFP15] J.-N. Monette, P. Flener, and J. Pearson. Automated auxiliary variable elimination through on-the-fly propagator generation. In: G. Pesant (editor), CP 2015. Lecture Notes in Computer Science. © Springer, 2015. (PDF) (Preprint)
A Parametric Propagator for Discretely Convex Pairs of Sum Constraints
The implementation of the parametric propagator presented in [MBFP13] for discretely convex pairs of sum constraints is solver-independent, but we provide a "bridge" with OscaR. It should be easy to create the same bridge for other Java-based solvers. The implementation includes several instantiations of the pattern, including SPREAD, DEVIATION, and LINEAR+COUNT. There is little or no documentation in the code. Feel free to contact Jean-Noël Monette for help. The following code is shared under the BSD 3-Clause license:
The files above contain also the code used to perform the experiments presented in [MBFP16,MBFP13]. We used BACP instances and the raw results of our experiments are here. However, if you are interested in replicating the experiments, we advise you to use the replication package (the exact URL is apparently subject to change, please let us know if the link is dead and we will update it).
- [MBFP16] J.-N. Monette, N. Beldiceanu, P. Flener, and J. Pearson. A parametric propagator for pairs of sum constraints with a discrete convexity property. Artificial Intelligence, 241:170-190, December 2016. (PDF) (Preprint)
- [MBFP13] J.-N. Monette, N. Beldiceanu, P. Flener, and J. Pearson. A parametric propagator for discretely convex pairs of sum constraints. In: Ch. Schulte (editor): Proceedings of CP 2013, pages 529-544. Lecture Notes in Computer Science, volume 8124. © Springer-Verlag, 2013. (PDF) (Preprint) (Slides)
A Propagator for the Context-Free-Grammar Constraint
Jun He has written a Gecode implementation of our state-of-the-art propagator proposed in [HFPZ13] for the context-free-grammar constraint:
The implementation is provided as is, and does not fully comply yet with Gecode style (this is ongoing work), but we hope it will already be useful to some. It is intended to release the code under a BSD license, but the relevant license files have not yet been included.
- [HFPZ13] J. He, P. Flener, J. Pearson, and W. M. Zhang. Solving string constraints: The case for constraint programming. In: Ch. Schulte (editor), CP 2013, pages 381-397. Lecture Notes in Computer Science, volume 8124. © Springer, 2013. (PDF) (Preprint) (Slides)
Bit-Vector Variables and Constraints
Kellen Dye [D14] has written a Gecode implementation of bit-vector variables and propagators for bit-vector constraints, including some of those of [MVH12], following the ideas of [MVH12]:
The implementation is provided as is, and does not fully comply yet with Gecode style (this is ongoing work), but we hope it will already be useful to some.
- [D14] K. Dye. Implementation of Bit-Vector Variables in a CP Solver, with an Application to the Generation of Cryptographic S-Boxes. Master Thesis in Computer Science, Report IT 14 063, Faculty of Science and Technology, Uppsala University, Sweden, October 2014. (PDF)
- [MVH12] L. D. Michel and P. Van Hentenryck. Constraint satisfaction over bit-vectors. In: M. Milano (editor), CP 2012, pages 527-543. Lecture Notes in Computer Science, volume 7514. © Springer, 2012. (PDF)