ArbitraryModelExample

To give a much more arbitrary example, we will use binkar10_1.mps, and solve it with VMND with both user-given neighborhoods and automatically created neighborhoods. This code can be copy/pasted or can be found in the Examples folder ArbitraryMIPExample.py.

Boilerplate code and Imports

As we saw in the previous example, we will asume we are in the Examples folder (otherwise path should be modified relatively), and we must import the parent directory with the modules VMND and Neighborhood. Also, we need the functions read and the Model class from gurobipy.

import sys
import os
sys.path.append(os.path.pardir)
from VMND import solver
from Neighborhood import Neighborhoods, varClusterFromMPS
from gurobipy import *

Creation of the MPS File

First we put the downloaded mps file inside the MIPLIB (binkar10_1.mps is already inside) folder and declare a string variable to this path.

path = os.path.join( os.path.pardir, 'MIPLIB', 'binkar10_1.mps' )

Creation on the Neighborhoods

Cluster Neighborhoods

First we will explain the Cluster Neighbrohoods, which automatically creates neighborhoods given a mps file. To use this function varClusterFromMPS, it must be imported from the Neighborhood module. This function loads the mps and creates a graph whose nodes are the model's variables and its edges are weighted with the amount of common constraints of both variables. Once this graph is built, we use the function SpectralClustering from sklearn to create a given number of clusters (given by numClu) with the weights of the graph, which can be interpreted as an "affinity matrix" of the nodes. Finally, the labels of each node induce the neighborhoods, so in each depth of Local Search we set free just one cluster of variables and fix the rest of the graph. Because of this design, each neighborhood has just one parameterization.

nbhs = varClusterFromMPS(path, numClu = 5, varFilter = None)

The input varFilter is a function which (if given) filters the varibles that the graph considers while reading the mps file. As this is a very expensive algorithm (the spectral clustering is cuadratic in memory), it is recomended to define wisely this parameter.

Neighborhoods created by the user: Functional Neighborhoods

If a user wishes to build neighborhoods of its own for a mps model this is a very practical way of doing this. Firstly we need to load the model and get its list of variables:

m = read(path)
klist = list( map( lambda var: var.VarName, m.getVars() ) )

If you print this list, you shall get:

['C0001', ..., 'C2298']

Once we have all the names of the variables on klist, we declare the outerNeighborhoods parameter, which in the case of Functional Neighborhoods consists of a dictionary whose keys are the consecutive integers corresponding to each neighborhood and the values are tuples who contain the names of that depth's parameterizations.

outerNbhs = {
    i : (0, ) for i in range(1, 6)
}

The final argument of the Neighborhoods parameterization is the function to be used. In this case we defined 5 neighborhoods, with only one parameterization each. We can see in this function how the variable num stores the number of the varaible (the name without the prefix 'C' as an integer) and the if/else sentences returns True if the variable is to be fixed.

def funNbhs(varName, depth, param):
    num = int(varName.lstrip('C'))
    if depth == 1:
        # Free if lower or equal than 500
        return num > 500
    elif depth == 2:
        # Free from 501 to 1000
        return depth < 501 or depth > 1000
    elif depth == 3:
        # Free from 1001 to 1500
        return  depth < 1001 or depth > 1500
    elif depth == 4:
        # Free from 1501 to 2000
        return  depth < 1501 or depth > 2000
    elif depth == 5:
        # Free from 2001 to 2298
        return depth < 2001
    else:
        # An error is raised if varaible is not in the correct format.
        print('Error, this name does not exist!')
        return 0

In this case, as we see in the upper pice of code, the first neighborhood fixes all but the first 500 variables, the second neighborhood all but the second 500 variables and so on, until the fifth, which fixes all but the last 298 variables. In general, larger MIP neighborhoods should be put at the end, but since this is just an example, it suffices to define them just like that.

Finally, the Neighborhoods instance is built, with all the parameters involving Functional Neighborhoods.

nbhs = Neighborhoods(
    lowest = 1,
    highest = 5,
    keysList= klist,
    randomSet= False, 
    outerNeighborhoods= outerNbhs,
    useFunction=True,
    funNeighborhoods= funNbhs

Neighborhoods created by the user: Physical Neighborhoods

A much simpler, but slower approach is making Physical Neighborhoods, which store for each depth and parameterization all the variables that will be fixed there.

In this case, all this information goes to the outerNeighborhoods parameter, as in this case it is a dictionary of dicitionaries. As we can see in the example down below, the first key is the depth and the second is the name of the parameterization. The value of the las dictionary is a tuple or a list of all the variables that remain fixed in that state. In the following piece of code the previous computed klist is filtered in each neighborhood / parameterization.

outerNbhs = {
    1 : {
        0 : [element for element in klist if int(element.lstrip('C')) > 500 ]
    },
    2 : {
        0 : [element for element in klist if int(element.lstrip('C')) <= 500 or int(element.lstrip('C')) >= 1001 ]
    },
    3 : {
        0 : [element for element in klist if int(element.lstrip('C')) <= 1000 or int(element.lstrip('C')) >= 1501 ]
    },
    4 : {
        0 : [element for element in klist if int(element.lstrip('C')) <= 1500 or int(element.lstrip('C')) >= 2001 ]
    },
    5 : {
        0 : [element for element in klist if int(element.lstrip('C')) <= 2000 ]
    }
}

Finally, the Neighborhoods object is created, this time only using the outerNeighborhoods parameter, since we are using Physical Neighborhoods. Of course, there must also be a match between that input, lowest and highest.

nbhs = Neighborhoods(
    lowest = 1,
    highest = 5,
    keysList= None,
    randomSet= False, 
    outerNeighborhoods= outerNbhs,
    useFunction=False,
    funNeighborhoods= None
)

Executing the VMND Heuristic

At this point, we have all the requirements needed to solve this mps model with the VMND Heuristic. To do this, we just invoke the solver function from VMND.py with the parameters we want.

solver(
    path,
    verbose = True,
    addlazy= False,
    funlazy = None,
    importNeighborhoods=True,
    importedNeighborhoods= nbhs,
    funTest= None,
    callback = 'vmnd',
    alpha = 2,
    minBCTime= 10,
    timeLimitSeconds= 300
)