Minimum Dominating Set Example

Download Notebook

The Minimum Dominating Set problem finds the smallest set of vertices such that every vertex of the graph is either in the set or adjacent to at least one vertex in the set. It is NP-hard, with applications in placing facilities, monitors, or relay stations so that every location is served directly or by a neighbor.

import getpass
import os

import numpy as np
from dotenv import load_dotenv

from local_solver.scip import SCIP
from luna_usecases.minimum_dominating_set import (
    MinimumDominatingSetCollection,
    MinimumDominatingSetData,
    MinimumDominatingSetFormulation,
    MinimumDominatingSetInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define a 6-node graph. A dominating set covers every node directly or through a neighbor.

adj = np.array(
    [
        [0, 1, 1, 0, 0, 0],
        [1, 0, 1, 0, 0, 0],
        [1, 1, 0, 1, 0, 0],
        [0, 0, 1, 0, 1, 1],
        [0, 0, 0, 1, 0, 1],
        [0, 0, 0, 1, 1, 0],
    ]
)
node_names = ["A", "B", "C", "D", "E", "F"]
data = MinimumDominatingSetData.from_adjacency_matrix(adjacency_matrix=adj, node_names=node_names)
print(data.to_string())

Plot Data

Visualize the graph structure.

data.plot()

Create Formulation

Minimize selected nodes while ensuring every node is selected or adjacent to a selected node.

formulation = MinimumDominatingSetFormulation()
print(formulation.to_string(data))

Create Instance

Combine data and formulation into a solvable instance.

instance = MinimumDominatingSetInstance(data=data, formulation=formulation)
print(instance.to_string())

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

Collections

Generate a benchmark collection of random instances for batch processing.

collection = MinimumDominatingSetCollection.from_random(min_nodes=4, max_nodes=6, num_instances=2, seed=42)
model = collection.instances[0].formulate()
print(model)