Minimal Hitting Sets

Project for the "Algoritmi & Strutture Dati" course, held at Università degli Studi di Brescia (Italy).

The aim of the project was to develop a software application capable of calculating Minimal Hitting Sets (MHS), while also analyzing its performance.

Environment Setup

To use the program, you first need to have Python 3.12 or more recent installed, and all the necessary libraries.

It is highly recommended to follow the same steps described in the CONTRIBUTING.md file, where you create a virtual environment specific to this project, so that all dependencies will only impact the project itself.

If you don't mind, assuming you already have Python on your system, to download all dependencies you just need to execute the following:

pip install -r requirements.txt

How To Use

Problem Matrix

The program takes as input a problem matrix file, which consists of optional comments marked with ;;; at the top of the file, and a matrix full of zeros and ones.

Each columns represents an element, for a total of $M$ elements, while each row represents a set, for a total of $N$ sets. Each set is delimited by a final - character.

The value $a_{ij}$ of the matrix is $1$ if the element at index $j$ belongs to the set at index $i$, otherwise $0$.

;;;
;;; This is a comment
;;;
1 1 0 0 1 0 0 1 0 1 0 0 0 -
1 1 0 1 0 0 1 1 0 1 0 1 0 -
1 1 1 0 0 0 1 0 0 1 0 0 0 -
1 1 1 0 0 1 1 0 0 1 0 1 0 -
1 1 1 0 0 0 1 0 0 1 0 0 0 -

Standard Search

In the file index.py, you need to set two variables:

• file_path: the path to the problem matrix you want to solve. For example, if you create in the project root folder a new folder called "benchmarks", in which you have a problem file called "problem.matrix", you can set the variable like this:

file_path: str = "./benchmarks/problem.matrix"

• out_folder: the path to the folder you want to save the solution of the problem into. For example, if you have in the project root folder a folder called "mhs", you can set the variable like this:

out_folder: str = "./mhs"

Once this is done, you can run the program by executing the following command. The execution can be stopped at any time with the key combination Ctrl+C.

python index.py

Based on the previously set parameters, you can find the solution of the problem, with all found minimal hitting sets and additional diagnostic and performance information, in the file located at "./mhs/problem.mhs".

Search with Permutation

In the file index.py, you can additionally set up the permutation logic by uncommenting the following two lines:

permutator = ProblemPermutator(file_path=file_path)
permutation = permutator.permute(strategy=<strategy>)

As for how the permutation setup works:

• permutator: instance of ProblemPermutator, which takes in the same file path from before, and is used to compute the permutation to be applied on the problem matrix.

• permutation: the permutation properties computed by the permutator, by using the selected <strategy>. All already available permutation strategies can be imported from the stragegy file.

If you decide to use a permutation, you need to modify the line that calls the class responsible for the minimal hitting set search, by passing the computed permutation properties, like so:

solution = search.find_mhs(permutation=permutation)

Library Usage

This project has been mainly developed as a library, whose components can be used and/or extended outside of the main index.py executable file. Below are described the core components that make up the library.

Hypothesis

The Hypothesis is the core class of this library, which of course represents a hypothesis of the minimal hitting set problem. It consists of two attributes:

• bin: the binary representation of the hypothesis within the Hasse diagram, such as [1, 0, 0, 1, 0]. Each $1$ in the binary representation identifies the elements of the problem matrix that belong to the hypothesis.
• vector: the vector representation of the hypothesis over the sets of the problem matrix, such as [1, 1, 0]. Each $1$ in the vector representation identifies the sets of the problem matrix that are covered by its elements.

>>> hypothesis = Hypothesis(bin=[1, 0, 0, 1, 0], vector=[1, 1, 0])

MHSFinder

The MHSFinder, or minimal hitting set finder, is responsible for searching all minimal hitting sets of the given problem matrix.

During the search progress, MHSFinder displays a progress bar, which lets the user see the search execution progress. More specifically, it allows to see the:

• Current level of the search.
• Maximum depth of the search.
• Total number of minimal hitting sets found so far.
• Number of hypotheses that have been analyzed, over the total number of hypotheses present at the current level.
• Number of generated hypotheses, which will need to be analyzed at the next level of the search.

At the end of the search, or after the user has interrupted in advance the process using Ctrl+C, MHSFinder returns a SolutionProps object, which contains:

• All minimal hitting sets found up to the point of execution.
• Diagnostic information of the search, such as time and memory usage of the search at each level of execution, reached search depth, and whether the search was interrupted early.

It may additionally take as parameter a PermutationProps object, which is used to apply a permutation on the original matrix during the search.

# Create a MHSFinder instance
>>> search = MHSFinder(file_path=file_path)
# Run the search algorithm
>>> solution: SolutionProps = search.find_mhs(permutation=permutation)

ProblemPermutator

The ProblemPermutator is responsible computing the permutation to be applied on the original matrix during the execution of the search. A permutation is defined as a reordering of either/both the elements and sets of the original problem matrix, so that the search algorithm is forced to analyze the problem following a different order.

# Create a ProblemPermutator instance
>>> permutator = ProblemPermutator(file_path=file_path)
# Compute the permutation to apply to the search
>>> permutation: PermutationProps = permutator.permute(strategy=<strategy>)

The ProblemPermutator, by using a specific strategy, returns a PermutationProps object, which contains the following two attributes:

• element_indexes: a list of length $M$, representing a new arrangement of the elements relative to their original order. In practice, each index in the original list is mapped to its new position in the permutation.

For example, if the permutation indexes are [1, 2, 0, 4, 3], then the element at index (column) 0 in the original matrix is now the element at index 1 in the permutated matrix, the element at index 1 is now the element at index 2, and so on, the element at index 2 is now the element at index 0, and so on.

• set_indexes: a list of length $N$, representing a new arrangement of the sets from their original order. Each index in the original list is mapped to its new position in the permutation.

For example, if the permutation indexes are [1, 2, 0, 4, 3], then the set at index (row) 0 in the original matrix is now the set at index 1 in the permutated matrix, the set at index 1 is now the set at index 2, and so on, the set at index 2 is now the set at index 0, and so on.

All already available permutation strategies can be imported from the stragegy file. If you instead want to implement your own strategy to pass as parameter to the ProblemPermutator, it needs to follow the specifications illustrated before. The following is a baseline for any new permutation strategy callable function:

def custom_strategy(
    problem_reader: ProblemReader,
    problem_props: ProblemProps
) -> PermutationProps:
    # TODO: your code here