Repository: CharJon/GeCO (language: python)

Issue:
Graph Coloring



Discussion / hints:

Fix patch:
diff --git a/.coveragerc b/.coveragerc
new file mode 100644
index 0000000..d978679
--- /dev/null
+++ b/.coveragerc
@@ -0,0 +1,2 @@
+[run]
+omit = *tests*
diff --git a/.gitignore b/.gitignore
index cd6ddbe..c8e9d66 100644
--- a/.gitignore
+++ b/.gitignore
@@ -129,4 +129,7 @@ dmypy.json
 .pyre/
 
 # Pycharm files
-.idea
\ No newline at end of file
+.idea
+
+# Local data
+data/local/
\ No newline at end of file
diff --git a/README.md b/README.md
index 1f46e3e..5ab697f 100644
--- a/README.md
+++ b/README.md
@@ -58,7 +58,8 @@ All the following instances are implemented following some of the generation tec
 - Production Planning
 - Maximum Independent Set 
 - Maximum Cut
-- Packing 
+- Packing
+- Graph Coloring
 
 # Contributing
 If you want to add some new generator, fix a big or enhance the repository in some way, please refer to our [guide](CONTRIBUTING.md).
diff --git a/geco/mips/graph_coloring/__init__.py b/geco/mips/graph_coloring/__init__.py
new file mode 100644
index 0000000..e69de29
diff --git a/geco/mips/graph_coloring/generic.py b/geco/mips/graph_coloring/generic.py
new file mode 100644
index 0000000..2c5b84a
--- /dev/null
+++ b/geco/mips/graph_coloring/generic.py
@@ -0,0 +1,308 @@
+import pyscipopt as scip
+import itertools
+import networkx as nx
+
+
+def assignment(
+    graph, color_upperbound, name="Assignment Graph Coloring", with_variables=False
+):
+    """
+    Generates a graph coloring ILP formulation (ASS-S) as described in [1].
+
+    Parameters
+    ----------
+    graph: networkx graph
+        Input graph
+    color_upperbound: int
+        Maximum number of colors to use
+    name: str
+        Name of the model
+    with_variables: bool
+        return variables with the generated model (used to extend model)
+
+    Returns
+    -------
+        A pyscipopt model of the generated instance
+
+    References
+    ----------
+    .. [1] A.Jabrayilov, P.Mutzel "New Integer Linear Programming Models for the Vertex Coloring Problem"
+    """
+    model = scip.Model(name)
+
+    graph = nx.convert_node_labels_to_integers(graph, first_label=0)
+    colors = range(color_upperbound)
+
+    # add variables and their cost
+    x = {
+        (vertex, color): model.addVar(
+            lb=0, ub=1, obj=0, name=f"x_{vertex}_{color}", vtype="B"
+        )
+        for vertex, color in itertools.product(graph.nodes, colors)
+    }
+
+    w = {
+        color: model.addVar(lb=0, ub=1, obj=1, name=f"w_{color}", vtype="B")
+        for color in colors
+    }
+
+    # add constraint (2)
+    for v in graph.nodes:
+        model.addCons(scip.quicksum(x[v, color] for color in colors) == 1)
+
+    # add constraint (3)
+    for u, v in graph.edges:
+        for color in colors:
+            model.addCons(x[u, color] + x[v, color] <= w[color])
+
+    model.setMinimize()
+    if with_variables:
+        return model, w, x
+    else:
+        return model
+
+
+def assignment_asymmetric(
+    graph, color_upperbound, name="Assignment Extended Graph Coloring"
+):
+    """
+    Generates a graph coloring ILP formulation (ASS) as described in [1] which
+    uses symmetry breaking rules from [2].
+
+    Parameters
+    ----------
+    graph: networkx graph
+        Input graph
+    color_upperbound: int
+        Maximum number of colors to use
+    name: str
+        Name of the model
+
+    Returns
+    -------
+        A pyscipopt model of the generated instance
+
+    References
+    ----------
+    .. [1] A.Jabrayilov, P.Mutzel "New Integer Linear Programming Models for the Vertex Coloring Problem"
+    .. [2] I.Mendez, P.Zabala "A Branch-and-Cut Algorithm for Graph Coloring"
+    """
+    model, w, x = assignment(graph, color_upperbound, name, with_variables=True)
+
+    graph = nx.convert_node_labels_to_integers(graph, first_label=0)
+    colors = list(range(color_upperbound))
+
+    # add constraint (5)
+    for color in colors:
+        model.addCons(w[color] <= scip.quicksum(x[v, color] for v in graph.nodes))
+
+    # add constraint (6)
+    for color in colors[1:]:
+        model.addCons(w[color] <= w[color - 1])
+    return model
+
+
+def representatives(graph, name="Representatives Graph Coloring"):
+    """
+    Generates a graph coloring ILP formulation (REP) as described in [1].
+
+    Parameters
+    ----------
+    graph: networkx graph
+        Input graph
+    name: str
+        Name of the model
+
+    Returns
+    -------
+        A pyscipopt model of the generated instance
+
+    References
+    ----------
+    .. [1] A.Jabrayilov, P.Mutzel "New Integer Linear Programming Models for the Vertex Coloring Problem"
+    """
+    model = scip.Model(name)
+
+    graph = nx.convert_node_labels_to_integers(graph, first_label=0)
+
+    # add variables and their cost
+    x = {}
+    for (u, v) in itertools.product(graph.nodes, graph.nodes):
+        if not graph.has_edge(u, v) or u == v:
+            obj = 1 if u == v else 0
+            x[u, v] = model.addVar(lb=0, ub=1, obj=obj, name=f"x_{u}_{v}", vtype="B")
+
+    # add constraint (8)
+    for v in graph.nodes:
+        non_adjacent_vertices = (graph.nodes - graph.neighbors(v)).union({v})
+        model.addCons(scip.quicksum(x[u, v] for u in non_adjacent_vertices) >= 1)
+
+    # add constraint (9)
+    for u in graph.nodes:
+        non_adjacent_vertices = graph.nodes - graph.neighbors(u) - {u}
+        for v, w in graph.edges:
+            if v in non_adjacent_vertices and w in non_adjacent_vertices:
+                model.addCons(x[u, v] + x[u, w] <= x[u, u])
+
+    model.setMinimize()
+    return model
+
+
+def set_covering(graph, subsets, name="Set Covering Graph Coloring"):
+    """
+    Generates a graph coloring ILP formulation (COV) as described in [1].
+
+    Parameters
+    ----------
+    graph: networkx graph
+        Input graph
+    subsets: Iterable of sets
+        Independent Sets of nodes
+    name: str
+        Name of the model
+
+    Returns
+    -------
+        A pyscipopt model of the generated instance
+
+    References
+    ----------
+    .. [1] A.Jabrayilov, P.Mutzel "New Integer Linear Programming Models for the Vertex Coloring Problem"
+    """
+    model = scip.Model(name)
+
+    graph = nx.convert_node_labels_to_integers(graph, first_label=0)
+
+    x = {
+        tuple(s): model.addVar(lb=0, ub=1, obj=1, name=f"x_{s}", vtype="B")
+        for s in subsets
+    }
+
+    for v in graph.nodes:
+        model.addCons(scip.quicksum(x[tuple(s)] for s in subsets if v in s) >= 1)
+
+    model.setMinimize()
+
+    return model
+
+
+def _partial_ordering_base_model(graph, colors, model):
+    q = 0
+
+    # add variables and their cost
+    y = {
+        (color, vertex): model.addVar(
+            lb=0,
+            ub=1,
+            obj=1 if vertex == q else 0,
+            name=f"y_{color}_{vertex}",
+            vtype="B",
+        )
+        for vertex, color in itertools.product(graph.nodes, colors)
+    }
+
+    z = {
+        (vertex, color): model.addVar(
+            lb=0, ub=1, obj=0, name=f"z_{vertex}_{color}", vtype="B"
+        )
+        for vertex, color in itertools.product(graph.nodes, colors)
+    }
+
+    # add constraint (16) and (17)
+    for v in graph.nodes:
+        model.addCons(z[v, 1] == 0)
+        model.addCons(y[colors[-1], v] == 0)
+
+    # add constraint (18), (19) and (21)
+    for v, c in itertools.product(graph.nodes, colors[:-1]):
+        model.addCons(y[c, v] - y[c + 1, v] >= 0)
+        model.addCons(y[c, v] + z[v, c + 1] == 1)
+        model.addCons(y[c, q] - y[c, v] >= 0)
+
+    model.setMinimize()
+
+    return model, y, z
+
+
+def partial_ordering(graph, color_upperbound, name="Partial Ordering Graph Coloring"):
+    """
+    Generates a graph coloring ILP formulation (POP) as described in [1].
+
+    Parameters
+    ----------
+    graph: networkx graph
+        Input graph
+    color_upperbound: int
+        Maximum number of colors to use
+    name: str
+        Name of the model
+
+    Returns
+    -------
+        A pyscipopt model of the generated instance
+
+    References
+    ----------
+    .. [1] A.Jabrayilov, P.Mutzel "New Integer Linear Programming Models for the Vertex Coloring Problem"
+    """
+    model = scip.Model(name)
+
+    graph = nx.convert_node_labels_to_integers(graph, first_label=0)
+    colors = list(range(color_upperbound))
+
+    model, y, z = _partial_ordering_base_model(graph, colors, model)
+
+    # add constraint (20)
+    for (u, v), c in itertools.product(graph.edges, colors[:-1]):
+        model.addCons(y[c, u] + z[u, c] + y[c, v] + z[v, c] >= 1)
+
+    return model
+
+
+def hybrid_partial_ordering(
+    graph, color_upperbound, name="Hybrid Partial Ordering Graph Coloring"
+):
+    """
+    Generates a graph coloring ILP formulation (POP2) as described in [1].
+
+    Parameters
+    ----------
+    graph: networkx graph
+        Input graph
+    color_upperbound: int
+        Maximum number of colors to use
+    name: str
+        Name of the model
+
+    Returns
+    -------
+        A pyscipopt model of the generated instance
+
+    References
+    ----------
+    .. [1] A.Jabrayilov, P.Mutzel "New Integer Linear Programming Models for the Vertex Coloring Problem"
+    """
+    model = scip.Model(name)
+
+    graph = nx.convert_node_labels_to_integers(graph, first_label=0)
+    colors = list(range(color_upperbound))
+
+    # add variables and their cost
+    x = {
+        (vertex, color): model.addVar(
+            lb=0, ub=1, obj=0, name=f"x_{vertex}_{color}", vtype="B"
+        )
+        for vertex, color in itertools.product(graph.nodes, colors)
+    }
+
+    model, y, z = _partial_ordering_base_model(graph, colors, model)
+
+    # add constraint (14)
+    for v, c in itertools.product(graph.nodes, colors):
+        model.addCons(x[v, c] == 1 - (y[c, v] + z[v, c]))
+
+    # add constraint (23)
+    for (u, v), c in itertools.product(graph.edges, colors):
+        model.addCons(x[u, c] + x[v, c] <= 1)
+
+    return model


Test patch:
diff --git a/geco/mips/tests/test_graph_coloring.py b/geco/mips/tests/test_graph_coloring.py
new file mode 100644
index 0000000..d237208
--- /dev/null
+++ b/geco/mips/tests/test_graph_coloring.py
@@ -0,0 +1,108 @@
+import networkx as nx
+import pytest
+
+from geco.mips.graph_coloring.generic import *
+
+
+def _test_cycle_instance_output(model):
+    model.hideOutput()
+    model.optimize()
+    assert model.getStatus() == "optimal"
+    assert model.getObjVal() == 3
+
+
+def test_assignment():
+    graph = nx.cycle_graph(5)
+    H = 5
+    model = assignment(graph, H)
+    n = len(graph.nodes)
+    m = len(graph.edges)
+
+    # test variables and constraints
+    assert model.getNVars() == n * H + H
+    assert model.getNConss() == n + m * H
+
+    _test_cycle_instance_output(model)
+
+
+def test_assignment_asymmetric():
+    graph = nx.cycle_graph(5)
+    H = 5
+    model = assignment_asymmetric(graph, H)
+    n = len(graph.nodes)
+    m = len(graph.edges)
+
+    # test variables and constraints
+    assert model.getNVars() == n * H + H
+    assert model.getNConss() == n + m * H + H + (H - 1)
+
+    _test_cycle_instance_output(model)
+
+
+def test_representatives():
+    graph = nx.cycle_graph(5)
+    model = representatives(graph)
+    n = len(graph.nodes)
+    m = len(graph.edges)
+
+    # test variables and constraints
+    assert n <= model.getNVars() <= n ** 2
+    assert n <= model.getNConss() <= n + n * m
+
+    _test_cycle_instance_output(model)
+
+
+def test_set_covering():
+    graph = nx.cycle_graph(5)
+    subsets = [{0, 1}, {2, 3}, {4}]
+    model = set_covering(graph, subsets)
+    n = len(graph.nodes)
+
+    # test variables and constraints
+    assert 1 <= model.getNVars() <= 2 ** n
+    assert n <= model.getNConss() <= n * (2 ** n)
+
+    _test_cycle_instance_output(model)
+
+
+def test_partial_ordering():
+    graph = nx.cycle_graph(5)
+    H = 5
+    model = partial_ordering(graph, H)
+    n = len(graph.nodes)
+
+    # test variables and constraints
+    assert model.getNVars() == 2 * n * H
+    assert n <= model.getNConss() == 2 * n + 4 * n * (H - 1)
+
+    _test_cycle_instance_output(model)
+
+
+def test_hybrid_partial_ordering():
+    graph = nx.cycle_graph(5)
+    H = 5
+    model = hybrid_partial_ordering(graph, H)
+    n = len(graph.nodes)
+
+    # test variables and constraints
+    assert model.getNVars() == 3 * n * H
+    assert n + n * H <= model.getNConss() == 2 * n + 3 * n * (H - 1) + n * H + n * H
+
+    _test_cycle_instance_output(model)
+
+
+def test_node_labeling():
+    g = nx.karate_club_graph()
+    g = nx.convert_node_labels_to_integers(g, first_label=1)
+    H = 10
+    models = [
+        representatives(g),
+        assignment(g, H),
+        assignment_asymmetric(g, H),
+        partial_ordering(g, H),
+        hybrid_partial_ordering(g, H),
+    ]
+    for m in models:
+        m.hideOutput()
+        m.optimize()
+        assert m.getStatus() == "optimal" and m.getObjVal() == 5