ssp.py

Go to the documentation of this file.

 
"""
Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2012
"""
 
from pyscipopt import Model, quicksum
 
 
def ssp(V, E):
    """ssp -- model for the stable set problem
    Parameters:
        - V: set/list of nodes in the graph
        - E: set/list of edges in the graph
    Returns a model, ready to be solved.
    """
    model = Model("ssp")
 
    x = {}
    for i in V:
        x[i] = model.addVar(vtype="B", name="x(%s)" % i)
 
    for (i, j) in E:
        model.addCons(x[i] + x[j] <= 1, "Edge(%s,%s)" % (i, j))
 
    model.setObjective(quicksum(x[i] for i in V), "maximize")
 
    model.data = x
    return model
 
 
import random
 
 
def make_data(n, prob):
    """make_data: prepare data for a random graph
    Parameters:
       - n: number of vertices
       - prob: probability of existence of an edge, for each pair of vertices
    Returns a tuple with a list of vertices and a list edges.
       """
    V = range(1, n + 1)
    E = [(i, j) for i in V for j in V if i < j and random.random() < prob]
    return V, E
 
 
if __name__ == "__main__":
    random.seed(1)
    V, E = make_data(100, .5)
 
    model = ssp(V, E)
    model.optimize()
    print("Optimal value:", model.getObjVal())
 
    x = model.data
    print("Maximum stable set:")
    print([i for i in V if model.getVal(x[i]) > 0.5])