User's Guide

VMND Module: User's Guide

The main purpose of this library is to provide an implementation of the VMND (Variable MIP neighborhood descent) according to the work of Larrain et al. 2017 to an arbitrary MIP instance. The combination between Local Search and Branch and Cut (B&C) is proven to be very powerful to reduce execution times.

To succesfully run this heuristic you only need two inputs (one of the following is optional):

1. Write the model in .mps format (gurobi does this easily).
2. Define the variables to be fixed in each of the neighborhoods.
3. (optional) Define a separation function (lazy constraint aggregation function).

Each of the previous steps are explained in detail in the following steps.

Steps:

1.- Define Inputs:

   1.1. Define Initial Model: Firstly it is necessary to define a Gurobipy Model() instance, with all the variables, constraints and objective function except for those constraints which should be added as lazy. It is very important to define each model variable with a good name because in order to add lazy constraints and to declare neighborhoods you will access the variables through them. It is recomended to have a list with all variable names of the model. Once you define the model, you can use the gurobipy function model.write(path) to create iys .mps files.

  1.2.-Define Neighborhoods

Local search is done by fixing some variables to their last MIP incumbent value. To correctly handle this process the Neighborhood class was created, it handles the changes of them, their architecture and all the important basic functionality.

     1.2.1. Manually Generate them(recomended): Generating one's neighborhoods can be done in two very different ways, depending on the control we have on the model's variables and names. It can happen that just with knowing what is the name of the variable it can be determined whether it is fixed or not in a certain depth/parameterization, for example the variables often have a prefix and subindexes and this usually enough to know this. If that is not the case we just can enumerate extensively all variables that stay fixed in a certain depth/parameterization for each of this cases. For the first case we use Functional Nighborhoods and for the second case Physical Neighborhoods. This second approach can be memory and resource consuming and that can impact negatively the performance of local search, so it is used only when we don't have control or information on the prefixes or indexes of variables.

The first way of setting neighborhoods, is the Functional Neighborhoods and it consists on declaring a function that, given the name of the variable, the depth and parameterization, determines by a boolean output whether that variable stays fixed. For this, three inputs shall be needed. First, a list (or tuple) of the (names as strings) most important variables is needed, these are, all the variables that will be fixed in some parameterization of some neighborhood. The point of this list is declaring a significant set of variables, not all of them, as in many routing and integer problems it suffices to fix a relatively small amount of variables to fix the entire solution. An example of this list is the following (klist may be a misleading name since it is a tuple, but these two types are good for this input):

klist = ('y_0', 'y_1', 'y_2', ..., 'y_99')

Also, the "architecture" of the neighborhoods and parameterizations is also to be provided, this time through the outerNeighborhoods input (see this on the documentation of the class). The value of the dictionary of the neighborhoods is not another dictionary (as in the case of Physical Neighborhoods), but a tuple or list containing the parameterizations of each neighborhood (as it is defined in the example down below):

outer1Example = {
1: {
    (1, 2)
},
2: {
    ((0, 1), (0, 2))
   }
}

Finally the argument useFunction must be set to true and the function must be provided. This function (an example funNbhs can be seen below) has three arguments: varName, depth and param, these are: the variable's name, the current neighborhood and the parameterization respectively. The output of this function is a boolean (which fixes the variable in (depth, param) if is True). The following python code shows an example on how to build this function:

def funNbhs(varName, depth, param):
    prefix, number = varName.split('_')
    if depth == 1:
        if param == 1:
            if int(number) <= 49:
                return False
            else:
                return True
        elif param == 2:
            if int(number) > 49:
                return False
            else:
                return True
    elif depth == 2:
        ...
    return True

Here it can be seen how the function retrieves the variable's name or prefix "y" with the number from 0 to 99 (the elements of klist). We can also observe how in the first neighborhood and first parameterization the first 50 "y" variables are set free (False means they are not fixed) and in the second parameterization the second 50 variables are set free.

Finally, once you gather all these parameters, you shall declare the neighborhood object with Functional Neighborhoods like this:

nbhs =  Neighborhoods(
    lowest = 1,
    highest = 2,
    keysList = klist,
    randomSet = False,
    outerNeighborhoods = outer1Example,
    funNeighborhoods = funNbhs,
    useFunction = True
)

Now, the second way, the Physical Neighborhoods, consists as well of generating an instance of Neighborhoods, this time the only input needed is "outerNeighborhoods" has to follow this structure (see the following python code):

outer2Example = {
1: {
    1 : ['y_{}'.format(i) for i in range(50, 100)],
    2 : ['y_{}'.format(i) for i in range(50)]
},
2: {
    (0, 1) : [...],
    (0, 2) : [...]
   }
}

Here we can see two neighborhoods(numbered from 1 to 2), which must be denoted always as consecutive integers (if there is one missing an error will occur). Also, in each of these neighborhoods we shall find another dictionary whose keys are the neighborhood's parameterizations and whose values are a list of the variable names fixed in that parameterization (in the example they're the same as before). As we explain in the Documentation, it suffices for a parameterization's name to be hashable (as we see integers 1, 2 and a tuples (0, 1) and (0, 2) ), it is not as strict as in case of the neighborhoods. Of course variable names are to be the same as in the mps file (and be of string format). The solver is designed to foresee when neighborhood variables (or variables within keysList) do not belong to the model, that error will be notified and the execution won't start.

Finally, once you have ready the outerNeighborhoods, you shall declare the neighborhood object with Physical Neighborhoods like this:

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

     1.2.2.- Import them from a .txt file: The function importNeighborhoods receives a path and returns the neighborhoods object contained in the .txt file of that path.

The Neighborhoods file format must have the following structure (and be a .txt file):

• First Line: (string) Name of the neighborhood, without spaces.
• Second Line: (integer) Lowest neighborhood number (number denoted as nl).
• Third Line: (integer) Highest neighborhood number (number denoted as nh).
• The following lines describe the i-th (from i = nl, ..., nh) neighborhood and follow this structure.
  • i: (integer) the number of the i-th neighborhood.
  • ni: (integer) the number of parameterizations of the i-th neighborhood.
  • The following 2 * ni lines follow this structure:
  • name_i_j: (integer or string) Name or integer describing the j-th parameterization of the i-th neighborhood.
  • fixed_i_j: (string) Names of the fixed variables separated by a space of the j-th parameterization of the i-th neighborhood.

     1.2.4.- Build them through a variable cluster : (recomended for not too large instances when used in notebook, mps below 15000kb) This way of generating instances consists of a cluster based on "connected" variables, this means that variables will be grouped according to the amount of constraints they share. To do this, an affinity matrix is constructed, assigning to each pair of variables an "affinity" which is the number of common constraints. Afterwards, a spectral clustering is performed with this matrix, based on the number of clusters given by the user. Finally each variable is set free in each neighborhood depending on the label given by the spectral clustering. It was determined because of this that there is only one parameterization in each neighborhood. To efficiently do this, the function varClusterFromMPS was created and must be imported from Neighborhood.py module. This function requires three arguments, path which is the path towards the mps file, an integer numClu which represents the amount of cluster variables and varFilter which is a function whose input is the name of a variable (a string) and returns a boolean, which determines if that variable is inside the list keysList described above. The purpose of the last function is to reduce the size of the key variables to those that determine the result of the model and make faster and lighter the clustering process.

nbhs = varCluster(path = 'my/path/file.mps', numClu = 10, varFilter = lambda var : var[0] == 'y')

In the previous example we can see that in this case, the varFilter function only considers names whose prefix is 'y' (here the prefix can be filtered by means of string split function or other techniques).

     1.2.5.- Generate them randomly (not recomended) : This is the simplest way, you only need to provide the input keysList (the klist defined previously) and let the input randomSet to True, which should have all the variables of the model or at least all the variables considered to be fixed during Local Search Phase. Often this won't be very efficient since there will be many variables here, so the sampling and saving process will take much longer than expected.

nbhs =  Neighborhoods(
    lowest = 1,
    highest = 2,
    keysList= klist,
    randomSet = True,
    outerNeighborhoods = None,
    funNeighborhoods= None,
    useFunction = False
)

   1.3.- [OPTIONAL]Define the Lazy Constraints aggregation

In this section, we explain how you can add constraints while branch and cut method is executing. To do this, it is necessary to define a separation function, which as input receives a dictionary with the values (and as keys the string with the name of each variable) of the current solution and as output returns a list with the Cut objects that are to be added. This cut objects are added internally as lazy constraints.

This Cut object that must be inside the output list of the separation function must contain three different attributes (see also the example below):

    1.3.1 nonzero: This attribute must be a dictionary, containing as keys the string names of the nonzero elements and with the constraint coefficient (int or float) as values.
    1.3.2.- sense: represents the sense of the constraint, it can be '<=', '>=' or '==' (as string).
    1.3.3.- rhs : The right hand side of the constraint, it can be a float or an int.

MyCut = Cut(
    {
        'x_0_1' : 1,
        'x_1_1' : 1
    },
    '<=',
    1
)

2.- Ejecute Model:

The execution of the VMND heuristic can be done only in certain places of the folder (In the folder Instances, in Main.py or in VMND.py) as long as you import correctly the solver function from the VMND.py module. To successfully run this procedure you must first set a few additional parameters:

1. path: The path that leads to the .mps file described above.
2. addLazy: Boolean, indicates whether lazy constraints will be added during B&C.
3. funLazy: The separation function described above. Only called if the previous argument addLazy is true.
4. importNeighborhoods: Boolean, if false the neighborhoods will be randomly generated, otherwise the user must provide them.
5. importedNeighborhoods: A Neighborhoods object, if the importNeighborhoods is true it declares this argument as the neighborhoods used for local search.
6. funTest: Function used to test the ouput variables or to see the output. The input of this function must be a dictionary with the variable names as keys. It can be None and no final checking procedure will be done.
7. alpha: Ratio between the time spent in B&C and Local Search phase (it is recomended 2 or 1, see Larrain et al. 2017 to see more values).
8. callback: 'vmnd' to execute VMND heuristic, for any other string value, the solver function executes pure branch and cut.
9. verbose: True if you want to see detailed console log of the B&C and Local Search Phase.
10. minBCTime : A float indicating the minimum amount of time that should be spent on Branch and Cut on each iteration of VMND.
11. timeLimitSeconds : A float indicating the time limit executing the model. If this is not desired, None should be added.
12. plotGapsTime : A boolean indicating that in each interval of 30 seconds the gaps and times will be saved. At the end of the execution, a plot of the gap's evolution is shown (a matplotlib.pyplot plot).
13. writeTestLog : A boolean indicating whether it is desired to generate a testlog file for testing or warning purposes.

3.- Analize and Visualize results:

Once executed, solver returns a Gurobipy solved Model() object. Since any analysis or visualization is case dependent, each case is individually implemented in the Instances folder. In most of the cases a route visualization is made for every period and vehicle.

• VRP: The routes of each truck can be visualized in a single matplotlib plot.
• IRP: Each plot represents a pair vehicle, period.
• IRPCS : Each plot represents a pair vehicle, period.
• TSP : Traveling Salesman Problem. The routes can be seen through a matplotlib plot.
• MVRPD: The routes for each period can be visualized as a matplotlib plot. Also the method analyzeRes shows the costs associated with:
  • Penalty
  • Routing
  • Inventory Holding.

If this is not clear enough, email me! at [email protected]