Maximum Clique Problem

Find the maximum subset of nodes in an incomplete graph \(G(V, E)\) in which all nodes are connected. We use a graph coloring heuristic (DSatur) as lower bound.

As an Integer Linear Problem, it can be modeled as a Maximum Independent Set on the complementary graph \(\overline{G} (V, E)\).

For more details, see Babel and Tinhofer (1990).

Babel, L., Tinhofer, G. A branch and bound algorithm for the maximum clique problem. ZOR - Methods and Models of Operations Research 34, 207–217 (1990). https://doi.org/10.1007/BF01415983

[1]:

import gc
import random

from bnbprob.maxclique import Graph, MaxClique, plot_clique
from bnbpy import LifoBnB, configure_logfile

[2]:

configure_logfile('maxclique.log')

[3]:

gc.disable()

[4]:

def random_instance(
    size: int, connectivity: float, seed: int | None = None
) -> list[tuple[int, int]]:
    if seed is not None:
        random.seed(seed)
    edges = []
    for i in range(size):
        for j in range(i + 1, size):
            if random.random() < connectivity:
                edges.append((i, j))
    return edges

[5]:

edges = random_instance(50, 0.6, seed=42)
graph = Graph.from_edges(edges)
problem = MaxClique(graph)
bnb = LifoBnB(problem)
sol = bnb.solve()
print(sol)

Status: OPTIMAL | Cost: -8.0 | LB: -8.0

[6]:

plot_clique(graph, sol.problem, seed=42)