Repository: PyVRP/PyVRP (python)

Issue:
ProblemData.distance_matrix requires importing IntMatrix / test_read.py fails
#### Describe the bug

`test_read.py` fails when running independently (it succeeds when running all tests), since it uses `ProblemData.distance_matrix` which requires `IntMatrix` to be imported.

Pull request:
Import DoubleMatrix and IntMatrix
This PR adds importing `DoubleMatrix` and `IntMatrix` in `pyvrp.__init__`. This ensures that these classes are known to the interpreter so that `ProblemData.distance_matrix` can be accessed without raising a type error.

- [x] Closes #204.
- [x] Adds and passes relevant tests.
- [x] Has well-formatted code and documentation.


Patch:
diff --git a/README.md b/README.md
index 5674674..0fdd542 100644
--- a/README.md
+++ b/README.md
@@ -1,7 +1,7 @@
 [![PyPI version](https://badge.fury.io/py/pyvrp.svg)](https://badge.fury.io/py/pyvrp)
-[![CI](https://github.com/N-Wouda/pyvrp/actions/workflows/CI.yml/badge.svg?branch=main)](https://github.com/N-Wouda/pyvrp/actions/workflows/CI.yml)
+[![CI](https://github.com/PyVRP/PyVRP/actions/workflows/CI.yml/badge.svg?branch=main)](https://github.com/PyVRP/PyVRP/actions/workflows/CI.yml)
 [![Documentation Status](https://readthedocs.org/projects/pyvrp/badge/?version=latest)](https://pyvrp.readthedocs.io/en/latest/?badge=latest)
-[![codecov](https://codecov.io/gh/N-Wouda/pyvrp/branch/main/graph/badge.svg?token=G9JKIVZOHB)](https://codecov.io/gh/N-Wouda/pyvrp)
+[![codecov](https://codecov.io/gh/PyVRP/PyVRP/branch/main/graph/badge.svg?token=G9JKIVZOHB)](https://codecov.io/gh/PyVRP/PyVRP)
 
 # PyVRP
 
diff --git a/docs/source/dev/contributing.rst b/docs/source/dev/contributing.rst
index 4e8dea4..edca3a6 100644
--- a/docs/source/dev/contributing.rst
+++ b/docs/source/dev/contributing.rst
@@ -1,7 +1,7 @@
 Contributing
 ============
 
-Conversations about development and issues take place in the `GitHub repository <https://github.com/N-Wouda/PyVRP/>`_.
+Conversations about development and issues take place in the `GitHub repository <https://github.com/PyVRP/PyVRP/>`_.
 Feel free to open a new issue if you have something to discuss.
 
 
@@ -10,7 +10,7 @@ Setting up a local installation
 
 Make sure you have a reasonably modern C++ compiler.
 Any recent version that supports (most of) the C++20 standard should do.
-Once you have a compiler installed, you can proceed by forking the ``pyvrp`` repository from the `GitHub website <https://github.com/N-Wouda/PyVRP/fork>`_.
+Once you have a compiler installed, you can proceed by forking the ``pyvrp`` repository from the `GitHub website <https://github.com/PyVRP/PyVRP/fork>`_.
 Then, clone your new fork to some local environment:
 
 .. code-block:: shell
diff --git a/docs/source/setup/benchmarks.rst b/docs/source/setup/benchmarks.rst
index 4d97379..868fc30 100644
--- a/docs/source/setup/benchmarks.rst
+++ b/docs/source/setup/benchmarks.rst
@@ -7,10 +7,10 @@ See the :doc:`benchmarking instructions <../dev/benchmarking>` for how these ben
 v0.1.0 (1 March 2023)
 ---------------------
 
-This benchmark concerns commit `e1b1ac7 <https://github.com/N-Wouda/PyVRP/tree/e1b1ac72bc1246cc51d252bf72df71fc43dc422b>`_, the version used to obtain the results of the initial submission.
+This benchmark concerns commit `e1b1ac7 <https://github.com/PyVRP/PyVRP/tree/e1b1ac72bc1246cc51d252bf72df71fc43dc422b>`_, the version used to obtain the results of the initial submission.
 The gaps below are computed against best-known solutions obtained from CVRPLIB on 28 February 2023.
 The parameter values were changed somewhat from the defaults in that commit.
-The relevant configuration files can be found in `3c26fab <https://github.com/N-Wouda/PyVRP/tree/3c26fab44ba612bae4a225daa099aefc1e618d9e>`_, under ``configs/``.
+The relevant configuration files can be found in `3c26fab <https://github.com/PyVRP/PyVRP/tree/3c26fab44ba612bae4a225daa099aefc1e618d9e>`_, under ``configs/``.
 
 CVRP
 ^^^^
diff --git a/docs/source/setup/getting_help.rst b/docs/source/setup/getting_help.rst
index 7f3cc5c..86c5ab3 100644
--- a/docs/source/setup/getting_help.rst
+++ b/docs/source/setup/getting_help.rst
@@ -1,7 +1,7 @@
 Getting help
 ============
 
-Conversations about development and issues take place in the `GitHub repository <https://github.com/N-Wouda/PyVRP/>`_.
+Conversations about development and issues take place in the `GitHub repository <https://github.com/PyVRP/PyVRP/>`_.
 Feel free to open a new issue if you have something to discuss.
 
 Submitting a bug report
diff --git a/docs/source/setup/installation.rst b/docs/source/setup/installation.rst
index 42da303..b37ec39 100644
--- a/docs/source/setup/installation.rst
+++ b/docs/source/setup/installation.rst
@@ -15,7 +15,7 @@ To install the latest version of ``pyvrp`` directly from the GitHub repository,
 
 .. code-block:: shell
 
-   pip install 'pyvrp @ git+https://github.com/N-Wouda/PyVRP'
+   pip install 'pyvrp @ git+https://github.com/PyVRP/PyVRP'
 
 This can be useful to get updates that have not yet made it to the Python package index.
 
@@ -29,7 +29,7 @@ To run the example notebooks locally, first clone the repository:
 
 .. code-block:: shell
 
-   git clone https://github.com/N-Wouda/PyVRP.git
+   git clone https://github.com/PyVRP/PyVRP.git
 
 Then, make sure your Python version has ``poetry``:
 
diff --git a/pyproject.toml b/pyproject.toml
index bc07ace..04d4ea0 100644
--- a/pyproject.toml
+++ b/pyproject.toml
@@ -9,7 +9,7 @@ authors = [
 ]
 license = "MIT"
 readme = "README.md"
-repository = "https://github.com/N-Wouda/PyVRP"
+repository = "https://github.com/PyVRP/PyVRP"
 include = [
     { path = "LICENSE.md" },
     { path = "meson.build", format = "sdist" },
diff --git a/pyvrp/Population.py b/pyvrp/Population.py
index 33ee816..18e4444 100644
--- a/pyvrp/Population.py
+++ b/pyvrp/Population.py
@@ -114,14 +114,23 @@ class Population:
         else:
             self._infeas.add(individual, cost_evaluator)
 
+    def clear(self):
+        """
+        Clears the population by removing all individuals currently in the
+        population.
+        """
+        self._feas = SubPopulation(self._op, self._params)
+        self._infeas = SubPopulation(self._op, self._params)
+
     def select(
         self,
         rng: XorShift128,
         cost_evaluator: CostEvaluator,
+        k: int = 2,
     ) -> Tuple[Individual, Individual]:
         """
-        Selects two (if possible non-identical) parents by binary tournament,
-        subject to a diversity restriction.
+        Selects two (if possible non-identical) parents by tournament, subject
+        to a diversity restriction.
 
         Parameters
         ----------
@@ -129,6 +138,9 @@ class Population:
             Random number generator.
         cost_evaluator
             Cost evaluator to use when computing the fitness.
+        k
+            The number of individuals to draw for the tournament. Defaults to
+            two, which results in a binary tournament.
 
         Returns
         -------
@@ -136,8 +148,9 @@ class Population:
             A pair of individuals (parents).
         """
         self._update_fitness(cost_evaluator)
-        first = self._get_binary_tournament(rng)
-        second = self._get_binary_tournament(rng)
+
+        first = self._get_tournament(rng, k)
+        second = self._get_tournament(rng, k)
 
         diversity = self._op(first, second)
         lb = self._params.lb_diversity
@@ -146,26 +159,17 @@ class Population:
         tries = 1
         while not (lb <= diversity <= ub) and tries <= 10:
             tries += 1
-            second = self._get_binary_tournament(rng)
+            second = self._get_tournament(rng, k)
             diversity = self._op(first, second)
 
         return first, second
 
-    def clear(self):
-        """
-        Clears the population by removing all individuals currently in the
-        population.
-        """
-        self._feas = SubPopulation(self._op, self._params)
-        self._infeas = SubPopulation(self._op, self._params)
-
-    def get_binary_tournament(
-        self,
-        rng: XorShift128,
-        cost_evaluator: CostEvaluator,
+    def get_tournament(
+        self, rng: XorShift128, cost_evaluator: CostEvaluator, k: int = 2
     ) -> Individual:
         """
-        Selects an individual from this population by binary tournament.
+        Selects an individual from this population by k-ary tournament, based
+        on the (internal) fitness values of the selected individuals.
 
         Parameters
         ----------
@@ -173,6 +177,9 @@ class Population:
             Random number generator.
         cost_evaluator
             Cost evaluator to use when computing the fitness.
+        k
+            The number of individuals to draw for the tournament. Defaults to
+            two, which results in a binary tournament.
 
         Returns
         -------
@@ -180,26 +187,11 @@ class Population:
             The selected individual.
         """
         self._update_fitness(cost_evaluator)
-        return self._get_binary_tournament(rng)
+        return self._get_tournament(rng, k)
 
-    def _get_binary_tournament(self, rng: XorShift128) -> Individual:
-        """
-        Selects an individual from this population by binary tournament.
-
-        Parameters
-        ----------
-        rng
-            Random number generator.
-
-        Returns
-        -------
-        Individual
-            The selected individual.
-
-        .. warning::
-            This function assumes self._update_fitness() has been called before
-            using this function unless nothing has changed.
-        """
+    def _get_tournament(self, rng: XorShift128, k: int) -> Individual:
+        if k <= 0:
+            raise ValueError(f"Expected k > 0; got k = {k}.")
 
         def select():
             num_feas = len(self._feas)
@@ -210,10 +202,6 @@ class Population:
 
             return self._infeas[idx - num_feas]
 
-        item1 = select()
-        item2 = select()
-
-        if item1.fitness < item2.fitness:
-            return item1.individual
-
-        return item2.individual
+        items = [select() for _ in range(k)]
+        fittest = min(items, key=lambda item: item.fitness)
+        return fittest.individual
diff --git a/pyvrp/__init__.py b/pyvrp/__init__.py
index bea6625..ec8c3ee 100644
--- a/pyvrp/__init__.py
+++ b/pyvrp/__init__.py
@@ -5,6 +5,7 @@ from .Result import Result
 from .Statistics import Statistics
 from ._CostEvaluator import CostEvaluator
 from ._Individual import Individual
+from ._Matrix import DoubleMatrix, IntMatrix
 from ._ProblemData import ProblemData
 from ._XorShift128 import XorShift128
 from .read import read, read_solution


Test patch:
diff --git a/pyvrp/tests/test_Population.py b/pyvrp/tests/test_Population.py
index 8be3432..2bdf04a 100644
--- a/pyvrp/tests/test_Population.py
+++ b/pyvrp/tests/test_Population.py
@@ -241,7 +241,8 @@ def test_elite_individuals_are_not_purged(nb_elite: int):
         assert_(id(elite_individual) in new_individuals)
 
 
-def test_binary_tournament_ranks_by_fitness():
+@mark.parametrize("k", [2, 3])
+def test_tournament_ranks_by_fitness(k: int):
     data = read("data/RC208.txt", "solomon", "dimacs")
     cost_evaluator = CostEvaluator(20, 6)
     rng = XorShift128(seed=42)
@@ -255,26 +256,48 @@ def test_binary_tournament_ranks_by_fitness():
 
     # Since this test requires the fitness values of the individuals, we have
     # to access the underlying infeasible subpopulation directly.
-    # We must also explicitly trigger to update the fitness first.
-    pop._infeas.update_fitness(cost_evaluator)
-    infeas = [item for item in pop._infeas]
-    infeas = sorted(infeas, key=lambda item: item.fitness)
-    infeas = {item.individual: idx for idx, item in enumerate(infeas)}
-    infeas_count = np.zeros(len(infeas))
+    infeas_pop = pop._infeas
+    infeas_pop.update_fitness(cost_evaluator)
+
+    items = [item for item in pop._infeas]
+    by_fitness = sorted(items, key=lambda item: item.fitness)
+    indiv2idx = {item.individual: idx for idx, item in enumerate(by_fitness)}
+    infeas_count = np.zeros(len(infeas_pop))
 
     for _ in range(10_000):
-        indiv = pop.get_binary_tournament(rng, cost_evaluator)
-        infeas_count[infeas[indiv]] += 1
+        indiv = pop.get_tournament(rng, cost_evaluator, k=k)
+        infeas_count[indiv2idx[indiv]] += 1
+
+    # Now we compare the observed ranking from the tournament selection with
+    # what we expect from the actual fitness ranking. We compute the percentage
+    # of times we're incorrect, and test that that number is not too high.
+    actual_rank = 1 + np.argsort(-infeas_count)  # higher is better
+    expected_rank = 1 + np.arange(len(infeas_pop))
+    pct_off = np.abs((actual_rank - expected_rank) / len(infeas_pop)).mean()
+    assert_(pct_off < 0.05)
 
-    # Now we compare the observed ranking from the binary tournament selection
-    # against what we would expect from the actual fitness ranking. We compute
-    # the percentage of times we're incorrect, and test that that number is not
-    # too high.
-    actual_rank = np.argsort(-infeas_count)  # higher is better
-    expected_rank = np.arange(len(infeas))
-    pct_off = np.abs((actual_rank - expected_rank) / len(infeas)).mean()
+    # Previous test compared just rank. Now we compare expected frequency. An
+    # item at rank i wins only when the other k - 1 items have a rank lower
+    # than i. That happens with probability roughly proportional to
+    #   (1 - i / #pop) ** (k - 1)
+    actual_freq = infeas_count / infeas_count.sum()
+    expected_freq = (1 - expected_rank / len(infeas_pop)) ** (k - 1)
+    expected_freq /= expected_freq.sum()
+    assert_allclose(actual_freq, expected_freq, atol=0.01)  # 1% tolerance
 
-    assert_(pct_off < 0.05)
+
+@mark.parametrize("k", [-100, -1, 0])  # k must be strictly positive
+def test_tournament_raises_for_invalid_k(k: int):
+    data = read("data/RC208.txt", "solomon", "dimacs")
+    cost_evaluator = CostEvaluator(20, 6)
+    rng = XorShift128(seed=42)
+    pop = Population(bpd)
+
+    for individual in make_random_solutions(5, data, rng):
+        pop.add(individual, cost_evaluator)
+
+    with assert_raises(ValueError):
+        pop.get_tournament(rng, cost_evaluator, k=k)
 
 
 def test_purge_removes_duplicates():