# CSPHeuristicLearning

This repository contains the source code for the algorithm designed to learn on-the-fly (variable ordering) heuristics for constraint optimization problems (COPs). To apply heuristics to COPs the Geocde solver is used and 
adapted.

The corresponding paper is:

Online Learning of Variable Ordering Heuristics for Constraint Optimisation Problems
Floris Doolaard and Neil Yorke‐Smith
Annals of Mathematics and Artificial Intelligence
https://doi.org/10.1007/s10472-022-09816-z
published online 2022


New/modified code copyright (c)2019-2022 Floris Doolaard

Released under the following BSD 3-clause licence.  Note that Gecode has its own licence.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of the copyright holder nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE 
GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 
OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


# Compilation

For machine learning Python is used and thus python must be installed on your machine, this must be done by downloading the source code and installing it. Even more so, `python-dev` and `python3.7-dev` must be installed as we embed Python into C++.

To be able to run the solver, follow the steps as in the [Gecode manual](https://www.gecode.org/doc-latest/MPG.pdf), but with additional arguments as follows:
`./configure`, optionally with the flag `--enable-debug` for debugging and `--disable-examples` if examples are not what you are looking for (saves compilation time).
To correctly compile all files we need to change to order of the CXX flags in the `Makefile` at lines 1803 and 1803 to: 
`$(DLLPATH) $(LINKALL) \`  
`$(CXXFLAGS) $(GLDFLAGS) $(LINKSTATICQT)`  
Then compile and install. There is also a shortcut for this using the script `./compile-solver`.
`make CXXUSR="-I/usr/local/include/python3.7m -L/usr/local/lib/libpython3.7m.a -lpython3.7m`  
`make install`


# How to run it

## MiniZinc IDE
The solver can be used with the *MiniZinc IDE* or *MiniZinc terminal*. First the source code must be compiled which can be done by following the steps in section 2.6 from the [Gecode manual](https://www.gecode.org/doc-latest/MPG.pdf). *MiniZinc* first compiles its models to *FlatZinc* which can be interpreted by Gecode in the file `fzn-gecode.exe`. This file is located (after compiling) in the `/tools` directory and must be copied to the root folder where the other `.dll` files are located which were produced by compilation.

Then, to add the custom Gecode solver to MiniZinc, follow the steps in the [MiniZinc documentation](https://www.minizinc.org/doc-2.2.0/en/minizinc_ide.html), section 3.2.5.2. Be sure to select the `fzn-gecode.exe` binary.

## Terminal
The `./hr-learner` program can be used to control the system. In here you can select problems to solve or delete save files.
Alternatively you can use the `./run-solver` script in the root folder to run the program. To adjust the minizinc file simply edit this script.

To manually run it (as in the script), direct to the folder `gecode-release-6.1.1/gecode/brancher` and use the following command to solve the compiled MiniZinc model (a Flatzinc file).

`PYTHONPATH=. ../../tools/flatzinc/fzn-gecode ../../../MiniZinc\ models/<minizinc model>.fzn`
