Building an automatic search for a backend can ease the modelling experience in MiniZinc when solving optimisation problems. As such, the purpose of this thesis was to examine the potential of automatic search through a portfolio implemented into the classical constraint programming solver Gecode for MiniZinc. The implemented portfolio includes eleven assets. Six assets utilise LNS strategies to navigate the search space. These include random, propagation-guided, reverse propagation-guided, objective relaxation, cost impact-guided, and static variable-relationship-guided LNS. Moreover, one asset compares all LNS assets and selects the one apparently most fit for the problem at hand. Additionally, two assets are modifications of standard Gecode search, and one is identical to it. The portfolio also includes a shaving asset that helps find infeasible values for variables during the search. Finally, the available assets incorporate branching strategies explicitly selected for each asset when search annotations are absent from the MiniZinc model to assist with automatic search. The portfolio’s performance was tested on a subset of problems from the MiniZinc Challenge 2023. The results demonstrate the efficiency of the implemented portfolio, beating other Gecode methods on most tested problems by finding superior solutions and in some cases achieving faster proofs of optimality.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:uu-533041 |
| Date | January 2024 |
| Creators | Leander, Dexter |
| Publisher | Uppsala universitet, Institutionen för informationsteknologi |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0016 seconds