hackathon baobab 2020

We want to schedule all jobs by deciding when and in which mode to execute each job. There are precedence relationships between pairs of jobs. There are two types of resources. Renewable resources (R) are consumed each period and have an availability that is recovered each period of time. Non-renewable resources (N) are consumed once per job and have an availability for the whole planning horizon. The objective is to reduce the finishing time (start time + duration) of the last job.

As an example the following image shows the input data (left), and the optimal solution (center: gantt, resource usage: right) for the instance c159_7.mm:

The instances for the problem are found here:

http://www.om-db.wi.tum.de/psplib/getdata_mm.html

On the data directory of this repository we have copied the smallest instances. For the format of the solution, since there is no example that we know of, we'll be using the one in data/solutions/c15mm/c1564_9.output.json

Below are the instructions to use the helper functions and checker (they are optional). To understand the format of the input data file, you can check how we parse it in python in the function Instance.from_mm(path) in the filehackathonbaobab2020/core/instance.py

Installation

python>=3.5 is needed. I'm assuming a Windows installation.

To install from source:

cd hackathonbaobab2020
python -m venv venv
venv/Scripts/activate
pip install -r requirements.txt

Alternatively, it's possible to install it as a pypi package. Here there is more control on which packages are installed.

Install only the core dependencies (core, schemas, default solver)::

pip install hackathonbaobab2020

Install all dependencies ('benchmark' to generate graphs, 'solvers' to install solver dependencies). The second line installs (in Ubuntu) the cbc solver::

pip install hackathonbaobab2020[benchmark,solvers]
sudo apt install coinor-cbc

How to add a new solver

These are the steps to add a solver and make it compatible with the command line and the python functions:

1. Add a file inside the hackathonbaobab2020/solver directory with a subclass of hackathonbaobab2020.core.experiment.Experiment that implements, at least, the solve() method with the same argument names.
2. Your solve method needs to return an integer with the status of the solving process. Current values are {4: "Optimal", 2: "Feasible", 3: "Infeasible", 0: "Unknown"}.
3. Your solve method also needs to store the best solution found in self.solution. It needs to be an instance of the Solution object.
4. Edit the hackathonbaobab2020/solver/__init__.py to import your solver and edit the solvers dictionary by giving your solver a name.
5. If the requirements.txt file is missing some package you need for your solver, add it to the list under solvers. Also edit the setup.py and add the dependency on solvers within the extras_require dictionary.

Additional considerations:

1. One way to see if the solver is correctly integrated is to test solving with it via the command line (see below).
2. Everything that your solver needs should be inside the hackathonbaobab2020/solver directory (you can put more than one file). Do not edit the files outside the solver directories with code from your solver!

How to run tests

These tests are run also in github and test some small example problems with a timelimit of 120 s (check the options dictionary).

python tests/tests.py 

Command line

The command line app has three main ways to use it.

To execute instances

To get all possible commands just run:

python hackathonbaobab2020/main.py solve-scenarios --help

The following assumes you have downloaded the zip j30.mm.zip of input instances, and you have stored it in the data directory. It solves instance j301_1.mm with the solver that is in hackathonbaobab2020/solver/algorithm1 named default in hackathonbaobab2020/solver/__init__.py.

python hackathonbaobab2020/main.py solve-scenarios --directory=data --scenario=j30.mm.zip --solver=default --instance=j3010_1.mm --no-test

You can also solve multiple scenarios or multiple instances by passing the --instances and --scenarios arguments. Just be careful with the string format:

python hackathonbaobab2020/main.py solve-scenarios --directory=data --scenarios='["c15.mm.zip", "c21.mm.zip", "j10.mm.zip", "j30.mm.zip", "m1.mm.zip", "m5.mm.zip", "n0.mm.zip", "n1.mm.zip", "n3.mm.zip", "r1.mm.zip", "r4.mm.zip", "r5.mm.zip"]' --solver=default

With the option argument, a json with the solving configuration is passed:

python hackathonbaobab2020/main.py solve-scenarios --directory=data --scenario=j30.mm.zip --solver=brute_EJ --instance=j3010_1.mm --no-test --options='{"DEBUG": 1, "timeLimit": 120}'

Finally, if you pass the zip option you create a nice little zip at the end.

The output format is always the same:

solver_name/scenario_name/instance_name/(input.json, output.json, options.json)

The options.json file contains some information from the solver such as the time it took to solve, the status (Optimal, Feasible, Infeasible, etc.), the name of the solver, etc.

To get statistics from a solution

You first need to have a zip with the results you want to get statistics from. For this, the easiest is to pass the zip option to the solve-scenarios function above.

Then you do something like:

python hackathonbaobab2020/main.py export-table --path=data/default.zip --path_out=data_default.csv

This generates a table in a csv with several columns: scenario, name (instance), objective (function value), solver, (solving) time, (number of) errors (in the solution).

To easily read the contents you can do:

import pandas as pd
df = pd.read_csv('data_default.csv')
print(df.head().to_markdown())

Which should print something like this:

Benchmarking solvers

In hackathonbaobab2020/execution/benchmark.py there are functions to automate the comparison of solvers. Function solve_all() executes a set of random instances. They require previously downloading the corresponding zips from the dataset site. Function compare produce a summary table based on the results. Finally, graphs use the generated table to produce graphs of the results.

Example of a resulting graph:

Using python objects

We use the following helper objects:

1. Instance to represent input data.
2. Solution to represent a solution.
3. Experiment to represent input data+solution.
4. Algorithm(Experiment) to represent a resolution approach.

An example of the last one (4) is found in hackathonbaobab2020/solver/algorithm1.py. It schedules one job at a time while respecting the sequence. It passes all tests except the non-renewables, sometimes.

There are helper functions to read and write an instance and a solution to/from a file.

A small example of how to use the existing code is available in hackathonbaobab2020/execution/test_script.py. Below an example:

from hackathonbaobab2020.core import Instance
from hackathonbaobab2020.solver import get_solver

# get mm file
path = "data/c15.mm/c154_3.mm"
# initialize an instance object
instance = Instance.from_mm(path)
# get the default solver (in solver/algorithm1.py)
solver = get_solver('default')
# initialize the solver with the instance
exp = solver(instance=instance)
# solve the instance using the solver
exp.solve({})
# The next functions do not depend on the solver and should not be overwritten:
# print the possible errors on the solution obtained from the solver
print(exp.check_solution())
# print the objective function of the solution
print(exp.get_objective())
# produce a gantt chart of the job's schedule, with a color per mode.
exp.graph()