Problems

If you're currently a student in an Algobattle lab course, you've probably wondered how exactly the problems work, found weird behaviour that you think might be a bug, or wanted to find out the exact file format it will accept. This page teaches you how to get all that info from just the files you've already got in your Algobattle project folder!

Note

This page goes over the anatomy of an Algobattle problem and how you can get what you're looking for from your project folder. This means it's mainly aimed at students who are trying to get more familiar with the course or a particular problem they're dealing with and course instructors who want to get an overview over how they work. If you instead are a course instructor looking to make a problem from scratch the instructor tutorial has more detailed info on that process.

Overall Structure

A typical problem file looks something like this

problem.py

"""The Scheduling problem class."""
from typing import Annotated

from algobattle.problem import Problem, InstanceModel, SolutionModel, minimize
from algobattle.types import Interval, SizeLen
from algobattle.util import Role


Timespan = Annotated[int, Interval(ge=0, le=(2**64 - 1) / 5)]
Machine = Annotated[int, Interval(ge=1, le=5)]


class Instance(InstanceModel):
    """The Scheduling problem class."""

    job_lengths: list[Timespan]

    @property
    def size(self) -> int:
        return len(self.job_lengths)


class Solution(SolutionModel[Instance]):
    """A solution to a Job Shop Scheduling problem."""

    assignments: Annotated[list[Machine], SizeLen]

    @minimize
    def score(self, instance: Instance, role: Role) -> float:
        finish_time = [0] * 5
        for duration, machine in zip(instance.job_lengths, self.assignments):
            finish_time[machine - 1] += duration * machine
        return max(finish_time)


Scheduling = Problem(
    name="Job Shop Scheduling",
    min_size=5,
    instance_cls=Instance,
    solution_cls=Solution,
)

What exactly the problems we discuss here are about is not important for this guide. If you're still curious you can find them all in our Algobattle problems repo with additional explanations. We will now go through this file and explain what each section does.

The Instance Class

This class defines what each instance of the problem will look like. It both tells you what your generator needs to create and what input your solver will receive. At the top of the class you will find a block of attribute definitions. In our case this is only a single line.

Timespan = Annotated[int, Interval(ge=0, le=(2**64 - 1) / 5)]
Machine = Annotated[int, Interval(ge=1, le=5)]


class Instance(InstanceModel):
    """The Scheduling problem class."""

    job_lengths: list[Timespan]

    @property
    def size(self) -> int:
        return len(self.job_lengths)

This tells us that each instance's json file contains a single key, job_lengths, which maps to a list of Timespans. As we can see from the type alias above the class definition, a Timespan just is an integer between 0 and (2⁶⁴ - 1) / 5. What that means is that if you're programming your generator you must ensure to not output any numbers that do not fall in this range, and when implementing your solver you can safely assume that all inputs you will receive are in it.

Instance Size

The instance size is defined by the size property.

Timespan = Annotated[int, Interval(ge=0, le=(2**64 - 1) / 5)]
Machine = Annotated[int, Interval(ge=1, le=5)]


class Instance(InstanceModel):
    """The Scheduling problem class."""

    job_lengths: list[Timespan]

    @property
    def size(self) -> int:
        return len(self.job_lengths)

Note

You should not include a size key in your instances. It will be computed from other attributes of the instance.

Additional Validation

Some problem instances, like this one for the Hikers problem, also include a validate_instance method.

class HikersInstance(InstanceModel):
    """The Hikers instance class."""

    hikers: list[tuple[u64, u64]]

    @property
    def size(self) -> int:
        """The instance size is the number of hikers."""
        return len(self.hikers)

    def validate_instance(self) -> None:
        super().validate_instance()
        if any(min_size > max_size for min_size, max_size in self.hikers):
            raise ValidationError("One hiker's minimum group size is larger than their maximum group size.")

This method contains further code that validates which inputs are allowable and which aren't. If you generate an instance that causes this method to raise an error, your instance will be considered invalid, and you will lose the fight.

The Solution Class

This class is very similar to the instance class, except it specifies what solutions look like. In our case we again have a single attribute and thus the solutions contain only a single key.

Timespan = Annotated[int, Interval(ge=0, le=(2**64 - 1) / 5)]
Machine = Annotated[int, Interval(ge=1, le=5)]


class Solution(SolutionModel[Instance]):
    """A solution to a Job Shop Scheduling problem."""

    assignments: Annotated[list[Machine], SizeLen]

    @minimize
    def score(self, instance: Instance, role: Role) -> float:
        finish_time = [0] * 5
        for duration, machine in zip(instance.job_lengths, self.assignments):
            finish_time[machine - 1] += duration * machine
        return max(finish_time)

This time we not only use an alias to specify the allowable range of integer values, but also the SizeLen marker which means that the number of assignments must be exactly the same as the instance's size.

Solution Score

Most solutions also have a score method. This tells Algobattle what the goal of this problem is and how to weigh different solutions.

Timespan = Annotated[int, Interval(ge=0, le=(2**64 - 1) / 5)]
Machine = Annotated[int, Interval(ge=1, le=5)]


class Solution(SolutionModel[Instance]):
    """A solution to a Job Shop Scheduling problem."""

    assignments: Annotated[list[Machine], SizeLen]

    @minimize
    def score(self, instance: Instance, role: Role) -> float:
        finish_time = [0] * 5
        for duration, machine in zip(instance.job_lengths, self.assignments):
            finish_time[machine - 1] += duration * machine
        return max(finish_time)

The decorator at the top can either be maximize or minimize and tells us if bigger or smaller score values are considered to be better. The function then computes some non-negative real number based on the instance and solution, this will be this solutions' score. Each fight in a battle will receive a single score, that will be calculated by comparing the solution score of the generator's and solver's solutions.

In our example the score just is the longest time a machine takes to complete all jobs. If in the generator's solution all machines complete their jobs in 10 units, but the solver's solution takes 12, the fight's score will be approximately 0.83.

Additional Validation

Just like instances can undergo extra validation, so can solutions. They use the validate_solution method for this.

class Solution(SolutionModel[HikersInstance]):
    """A solution to a Hikers problem."""

    assignments: dict[Hiker, u64]

    def validate_solution(self, instance: HikersInstance, role: Role) -> None:
        super().validate_solution(instance, role)
        group_sizes = Counter(self.assignments.values())

        for hiker, group in self.assignments.items():
            min_size, max_size = instance.hikers[hiker]
            if not (min_size <= group_sizes[group] <= max_size):
                raise ValidationError("A Hiker is not happy with their assignment!")

    @maximize
    def score(self, instance: HikersInstance, role: Role) -> float:
        return len(self.assignments)

The Problem Constructor

The last part of the problem file actually creates the problem.

"""The Scheduling problem class."""
from typing import Annotated

from algobattle.problem import Problem, InstanceModel, SolutionModel, minimize
from algobattle.types import Interval, SizeLen
from algobattle.util import Role


Timespan = Annotated[int, Interval(ge=0, le=(2**64 - 1) / 5)]
Machine = Annotated[int, Interval(ge=1, le=5)]


class Instance(InstanceModel):
    """The Scheduling problem class."""

    job_lengths: list[Timespan]

    @property
    def size(self) -> int:
        return len(self.job_lengths)


class Solution(SolutionModel[Instance]):
    """A solution to a Job Shop Scheduling problem."""

    assignments: Annotated[list[Machine], SizeLen]

    @minimize
    def score(self, instance: Instance, role: Role) -> float:
        finish_time = [0] * 5
        for duration, machine in zip(instance.job_lengths, self.assignments):
            finish_time[machine - 1] += duration * machine
        return max(finish_time)


Scheduling = Problem(
    name="Job Shop Scheduling",
    min_size=5,
    instance_cls=Instance,
    solution_cls=Solution,
)

It contains the name of the problem and references to the two classes we discussed. It also specifies what the smallest reasonable size of this problem is. In our case an instance should contain at least one job for each machine, so the minimum size of this problem is 5.