Project of "Combinatorial Decision Making and Optimization".
The goal of MCP is to decide for each courier the items
to be distributed and plan a tour.
In this repository you can find four solution for this problem which use four different approaches:
To install all the requirements run:
pip install -r requirements.txt
The suggested version of python is 3.10
All the solvers can be used by running the file main.py with the command python main.py and the following arguments:
-a approach, --approach approach with approach = {cp, sat, smt, lp, smtlib}. Selects the approach to use.
-m model, --model model with model = {0,1}. Select the model to use for the choosen approach, default = 1
-n N, --num_instance N Select an instance between 1 and 21; the code will execute the solver choosen from instance 1 to the given instance,
default = 0 means solve all.
-i path, --input_dir path Specify the path from where take the input files, default = "./input"
-o path, --output_dir path Specify the path in which the results will be generated, default = " ./output"
-t T, --timeout T Set the timeout in T seconds, default = 300s.
For the executing an SMT model using different solvers is needed a Linux Enviroment and the installation of the solvers that you want to use.
If you want to install z3-solver:
sudo apt-get install -y z3
If you want to install cvc4-solver:
sudo apt-get install -y cvc4
First of all is needed to install docker: https://www.docker.com/products/docker-desktop/
Important:
On docker there are the execution of model with the best performance for each approach.
To run with docker, is needed to build the docker image:
docker build. -t name_image
name_image is the name of image that you create
After that it is possible to run the container
docker run -v name_folder:/project/output name_image
name_folder is the name of the folder where the results will be saved
If the image is available, you need to load it on docker:
docker load -i name_image.tar
After that you can run the container using the previous command.
Notes:
To make the execution of docker linear, each approach use the instance which do not cause problem of memory exceeding, because if during the execution on docker there are problem of memory, docker kills the process and stops the execution.
Obviusly for the instance which are not taken in account during the execution of the model, the solution is UNKNOWN.
If you run the project in local(using for i.e Windows System), the problem of memory exceeding is handle without killed the process, the solution will be written but it still UNKNOWN.
In the following there are the best models for each approach:
-a cp -m 1
-a sat -m 1
-a smt -m 0
-a lp -m 1