Repository: CharJon/GeCO

Issue:
OR-Lib Set-Cover
Add method to translate [set-cover problems from or-lib](http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html) to our parameters for set-cover formulations.

Discussion:

Patch:
diff --git a/README.md b/README.md
index cab6f12..37e9c0e 100644
--- a/README.md
+++ b/README.md
@@ -91,7 +91,7 @@ might require, it works the exact same way it just doesn't stop after `n` instan
 [MIPLIB](https://miplib.zib.de/) 2017 instances can be loaded into a PySCIPOpt model using the `Loader` class.
 
 ```python
-from geco.mips.miplib.base import Loader
+from geco.mips.loading.miplib import Loader
 
 instance = Loader().load_instance('INSTANCE_NAME.mps.gz')
 ```
diff --git a/geco/mips/__init__.py b/geco/mips/__init__.py
index 99110ca..1f02736 100644
--- a/geco/mips/__init__.py
+++ b/geco/mips/__init__.py
@@ -8,4 +8,4 @@ import geco.mips.max_cut as max_cut
 import geco.mips.production_planning as production_planning
 import geco.mips.packing as packing
 import geco.mips.graph_coloring as graph_coloring
-import geco.mips.miplib as miplib
+import geco.mips.loading as miplib
diff --git a/geco/mips/loading/__init__.py b/geco/mips/loading/__init__.py
new file mode 100644
index 0000000..f70696c
--- /dev/null
+++ b/geco/mips/loading/__init__.py
@@ -0,0 +1,1 @@
+from geco.mips.loading.miplib import *
diff --git a/geco/mips/miplib/base.py b/geco/mips/loading/miplib.py
similarity index 100%
rename from geco/mips/miplib/base.py
rename to geco/mips/loading/miplib.py
diff --git a/geco/mips/loading/orlib.py b/geco/mips/loading/orlib.py
new file mode 100644
index 0000000..5fae257
--- /dev/null
+++ b/geco/mips/loading/orlib.py
@@ -0,0 +1,27 @@
+from urllib.request import urlopen
+
+FILES_BASE_URL = "http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/"
+
+
+def orlib_load_instance(instance_name, reader):
+    """
+    Generic wrapper for OR-Library [1] reader functions.
+
+    Parameters
+    ----------
+    instance_name: str
+        Name of instance file
+    reader: function
+        Takes a file-like object and returns the read model
+
+    Returns
+    -------
+    model: scip.Model
+        A pyscipopt model of the loaded instance
+
+    References
+    ----------
+    ..[1] http://people.brunel.ac.uk/~mastjjb/jeb/info.html
+    """
+    content_as_file = urlopen(FILES_BASE_URL + instance_name)
+    return reader(content_as_file)
diff --git a/geco/mips/miplib/__init__.py b/geco/mips/miplib/__init__.py
deleted file mode 100644
index 1e067ee..0000000
--- a/geco/mips/miplib/__init__.py
+++ /dev/null
@@ -1,1 +0,0 @@
-from geco.mips.miplib.base import *
diff --git a/geco/mips/set_cover/__init__.py b/geco/mips/set_cover/__init__.py
index 864ff85..42fb407 100644
--- a/geco/mips/set_cover/__init__.py
+++ b/geco/mips/set_cover/__init__.py
@@ -1,3 +1,4 @@
 from geco.mips.set_cover.generic import *
 from geco.mips.set_cover.yang import *
 from geco.mips.set_cover.sun import *
+from geco.mips.set_cover.orlib import *
diff --git a/geco/mips/set_cover/orlib.py b/geco/mips/set_cover/orlib.py
new file mode 100644
index 0000000..d34c178
--- /dev/null
+++ b/geco/mips/set_cover/orlib.py
@@ -0,0 +1,117 @@
+import pyscipopt as scip
+from geco.mips.loading.orlib import orlib_load_instance
+from geco.mips.set_cover.generic import set_cover
+
+
+def _read_number(line):
+    if not line:
+        return None
+    return int(line.strip().split(b" ")[0])
+
+
+def _read_numbers(line):
+    return (int(n) for n in line.strip().split(b" "))
+
+
+def _read_multiline_numbers(file, number_to_read):
+    costs = []
+    while file:
+        if len(costs) >= number_to_read:
+            break
+        else:
+            line = file.readline()
+            numbers = list(_read_numbers(line))
+            costs += numbers
+    return costs
+
+
+def _scp_reader(file):
+    """
+    Reads scp set-cover instances mentioned in [1].
+
+    Parameters
+    ----------
+    file: file-like object
+
+    Returns
+    -------
+    model: scip.Model
+        A pyscipopt model of the loaded instance
+
+    References
+    ----------
+    ..[1] http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html
+    """
+    number_of_cons, number_of_vars = _read_numbers(file.readline())
+    costs = _read_multiline_numbers(file, number_of_vars)
+    sets = []
+    while file:
+        number_of_vars_in_constraint = _read_number(file.readline())
+        if not number_of_vars_in_constraint:
+            break
+        constraint = list(_read_multiline_numbers(file, number_of_vars_in_constraint))
+        constraint = _zero_index(constraint)
+        sets.append(constraint)
+    assert len(costs) == number_of_vars and len(sets) == number_of_cons
+    return set_cover(costs, sets)
+
+
+def _zero_index(numbers):
+    return map(lambda x: x - 1, numbers)
+
+
+def _rail_reader(file):
+    """
+    Reads rail set-cover instances mentioned in [1].
+
+    Parameters
+    ----------
+    file: file-like object
+
+    Returns
+    -------
+    model: scip.Model
+        A pyscipopt model of the loaded instance
+
+    References
+    ----------
+    ..[1] http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html
+    """
+    number_of_cons, number_of_vars = _read_numbers(file.readline())
+    costs = []
+    sets = [[] for _ in range(number_of_cons)]
+    col_idx = 0
+    while file:
+        line = file.readline()
+        if not line:
+            break
+        numbers = list(_read_numbers(line))
+        costs.append(numbers[0])
+        rows_covered = _zero_index(numbers[2:])
+        for row in rows_covered:
+            sets[row].append(col_idx)
+        col_idx += 1
+    sets = list(filter(lambda l: len(l) > 0, sets))
+    assert len(costs) == number_of_vars and len(sets) == number_of_cons
+    return set_cover(costs, sets)
+
+
+def orlib_instance(instance_name):
+    """
+    Loads an orlib Set-cover instance
+
+    Parameters
+    ----------
+    instance_name: str
+        Name of the set-cover file. example: "scp41.txt"
+
+    Returns
+    -------
+    model: scip.Model
+        A pyscipopt model of the loaded instance
+    """
+    # TODO: assert that instance_name correlated to one of the listed set-cover files
+    if instance_name[:3] == "scp":
+        return orlib_load_instance(instance_name, reader=_scp_reader)
+    elif instance_name[:4] == "rail":
+        return orlib_load_instance(instance_name, reader=_rail_reader)


Test patch:
diff --git a/geco/mips/tests/test_miplib.py b/geco/mips/tests/test_miplib.py
index c544035..451b3fe 100644
--- a/geco/mips/tests/test_miplib.py
+++ b/geco/mips/tests/test_miplib.py
@@ -2,7 +2,7 @@ import pandas as pd
 import pytest
 import itertools
 
-from geco.mips.miplib.base import *
+from geco.mips.loading.miplib import *
 
 
 def test_load_miplib_list():
@@ -44,9 +44,9 @@ def test_persistent_directory():
 
 
 def test_miplib_sources_with_solution():
-    _check_instance("30n20b8.mps.gz", with_solution=True)  # from miplib 2017
-    _check_instance("neos-941262.mps.gz", with_solution=True)  # from miplib 2010
-    _check_instance("vpm2.mps.gz", with_solution=True)  # from miplib 2003
+    _check_instance("30n20b8.mps.gz", with_solution=True)  # from loading 2017
+    _check_instance("neos-941262.mps.gz", with_solution=True)  # from loading 2010
+    _check_instance("vpm2.mps.gz", with_solution=True)  # from loading 2003
 
 
 def test_instance_not_found_error():
@@ -58,7 +58,7 @@ def test_solution_not_found_error():
     with pytest.raises(ValueError):
         Loader().load_instance(
             "bharat.mps.gz", with_solution=True
-        )  # one of miplib 2017 open instances with no known solution
+        )  # one of loading 2017 open instances with no known solution
 
 
 def _check_instance(instance_name, with_solution=False):
diff --git a/geco/mips/tests/test_set_cover.py b/geco/mips/tests/test_set_cover.py
index 0e8548e..2e8f460 100644
--- a/geco/mips/tests/test_set_cover.py
+++ b/geco/mips/tests/test_set_cover.py
@@ -3,9 +3,9 @@ import itertools
 
 import pytest
 
-from geco.mips.set_cover.generic import *
 from geco.mips.set_cover.yang import *
 from geco.mips.set_cover.sun import *
+from geco.mips.set_cover.orlib import *
 
 """
 Generic Tests
@@ -118,3 +118,22 @@ def test_expand_sun_params(n, base_n, base_m, seed1, seed2):
     # test correct size
     assert len(costs1) == len(costs2) == n
     assert len(sets1) == len(sets2) == base_m
+
+
+"""
+OR-Library tests
+"""
+
+
+def test_scp_orlib():
+    instance_name = "scp41.txt"
+    instance = orlib_instance(instance_name)
+    assert instance.getNVars() == 1000
+    assert instance.getNConss() == 200
+
+
+def test_rail_orlib():
+    instance_name = "rail507.txt"
+    instance = orlib_instance(instance_name)
+    assert instance.getNVars() == 63009
+    assert instance.getNConss() == 507