LS2.py

# Purpose: Implementation for the second local strategy used (2-improvement LS for Maximum Independent Set, with stochastic restart)
import numpy as np
import time
import copy
import random
from util import randomMIS

def LS2(graph, cutoff, seed):
    '''
    Find a VC using local search strategy 2.

    Parameters
    ----------
    graph : graph() class
        the original test case, stored as a graph instance.
    cutoff : int
        Maximum runtime in seconds.
    seed : int
        Random seed used.

    Returns:
    ----------
    currentbest : int
        the number of vertices in the computed VC.
    bestIDs : set(int)
        list of vertices in the computed VC.
    Trace : list(pair(float,int))
        solution trace of the algorithm, where in each entry, first element is the cumulative runtime, and the second element the solution at the time.
    '''
    random.seed(seed)
    start_time = time.time()
    [quality,IDs,NC,tightness,tight0] = randomMIS(graph)
    randomruntime = time.time()
    Trace = [(randomruntime - start_time,quality)]
    currentbest = np.Infinity
    bestIDs = set()
    # Run until max time or local maximum found
    while (time.time()-randomruntime) < cutoff:
        u = -1
        v = -1
        w = -1
        ## Find combination of u, v, w so that u is replaced with v, w in the indepedent set
        for u_ in NC.keys():
            if (u != -1) and (v != -1) and (w != -1): break
            ### only check for v, w in the 1-tightness neighbors of u
            if len(NC[u_]) < 2:
                continue
            checked = set()
            for v_ in NC[u_]:
                if (u != -1) and (v != -1) and (w != -1): break
                for w_ in NC[u_]:
                    if (u != -1) and (v != -1) and (w != -1): break
                    ### check if v and w are connected
                    if (v_ != w_) and ((v_,w_) not in checked) and ((w_,v_) not in checked):
                        checked.add((v_,w_))
                        if graph.AdjacencyMatrix[v_-1][w_-1] == 0:
                            u = u_
                            v = v_
                            w = w_
                            break
        ## if u, v, w combination found, make replacements
        if (u != -1) and (v != -1) and (w != -1):
            NC.pop(u)
            NC[v] = set(graph.AdjacencyList[v])
            NC[w] = set(graph.AdjacencyList[w])
            tightness[u-1] = 0
            tightness[v-1] = -1
            tightness[w-1] = -1
            ### update tightness of the vertices
            IDs = set(graph.AdjacencyList.keys())-set(NC.keys())
            for neighbor in IDs:
                if graph.AdjacencyMatrix[neighbor-1][u-1] == 1:
                    tightness[neighbor-1]-=1
                    if tightness[neighbor-1] == 0:
                        tight0.add(neighbor)
                if graph.AdjacencyMatrix[neighbor-1][v-1] == 1:
                    if (tightness[neighbor-1] == 0) and (neighbor != u):
                        tight0.remove(neighbor)
                    tightness[neighbor-1]+=1
                if graph.AdjacencyMatrix[neighbor-1][w-1] == 1:
                    if (tightness[neighbor-1] == 0) and (neighbor != u):
                        tight0.remove(neighbor)
                    tightness[neighbor-1]+=1
            if tightness[u-1] == 0:
                tight0.add(u)
            ### update 1-tight neighbors of vertices in the indepedent set
            for vertex in NC:
                LX = copy.copy(NC[vertex])
                for neighbor in LX:
                    if tightness[neighbor-1] != 1:
                        NC[vertex].remove(neighbor)
            ### update VC solution
            quality = len(IDs)
            if quality < currentbest:
                Trace = Trace + [(time.time()-start_time, quality)]
        ## if u, v, w not found, add free vertex randomly to the independent set if any available
        else:
            if len(tight0)>0:
                freevertex = random.sample(tight0, 1)[0]
                NC[freevertex] = set(graph.AdjacencyList[freevertex])
                tightness[freevertex-1]=-1
                tight0.remove(freevertex)
                ### update tightness of neighbors of free vertex
                for neighbor in graph.AdjacencyList[freevertex]:
                    if tightness[neighbor-1] == 0:
                        tight0.remove(neighbor)
                    tightness[neighbor-1]+=1
                ### update 1-tight neighbors of vertices in the indepedent set
                for vertex in NC:
                    LX = copy.copy(NC[vertex])
                    for neighbor in LX:
                        if tightness[neighbor-1] != 1:
                            NC[vertex].remove(neighbor)
                ### update VC solution            
                IDs = set(graph.AdjacencyList.keys())-set(NC.keys())
                quality = len(IDs)
                if quality < currentbest:
                    Trace = Trace + [(time.time()-start_time, quality)]
            ## another random initializations if no improvement or free vertex
            else:
                if quality < currentbest:
                    currentbest = copy.copy(quality)
                    bestIDs = copy.copy(IDs)
                    Trace = Trace + [(time.time()-start_time, quality)]
                [quality,IDs,NC,tightness,tight0] = randomMIS(graph)
    if currentbest == np.Infinity:
        currentbest = quality
        bestIDs = IDs
        Trace = Trace + [(time.time()-start_time, quality)]
    return [currentbest,bestIDs,Trace]