Documentation

Modules

Connected Components(ConComp)

This module contains three functions:

1. graphMaker: Given a list of tuple (of length two containing each of the graph edges) and the number of nodes, creates the incidence matrix (i.e a list of lists containing 1 if an edge exists).
2. getSubsets: Receives two arguments, a list of tuples containing the edges of the graph and an integer that represents the number of nodes of the graph. Returns a list of lists, each one representing the connected components of the graph that don't contain the zero vertex or the "depot". This is used to obtain how many cuts are needed in the B&C phase.
3. MFComponents: Same input parameters as the previous function. Returns a list of lists, each one representing the connected components of the graph that don't contain the zero vertex or the "depot". This is used to obtain how many cuts are needed in the B&C phase, this function is different from getSubsets() since it return all connected compenents and uses the maximum flow algorithm to get connected components.

There are a few examples of their usage in the __init__.

Cuts

This module contains the class Cut and a few other functions involving Lazy constraint creation.

Attributes

• nonzero: Describes the nonzero coefficients that exist in a lazy constraint added by user. It should be a dictionary whose keys are the model variables defined in the .mps file and the values are the nonzero coefficients from the constraint.
• sense: can de '<=' or '==' or '>='.
• rhs: Float or int, is the right hand side of the constraint.

Methods

• str : Prints in console the constraint.

The following functions are used to generate lazy constraints to the problems in the Instances folder.

1. genSubTourLazy: Returns a function that given a dictionary of the solution variables checks if satisfies the subtour elimination constraints of the routing variables. The inputs are the number n of nodes (or retailers), the number of periods H and the number of vehicles K. The arguments mainStVarName and secondStVarName are used to declarate the name that the subtour and visit variables have in the model (for example in IRPCS subtour variables are x and visit variables are y).

2. SubtourElim: Is the classic Gurobi Callback function used to add Lazy Constraints.

3. getCheckSubtour: Has the same arguments as genSubTourLazy, it checks for extra connected components and returns True or False, printing existing subtour. The purpose of this function is Testing.

Functions

The first important function in this module is powerset which generates a python generator of all subsets contained in a sequence, was previously used as an option to generate all posible cuts.

There are as well plenty of functions that transform the keys of the dictionary of variales into tuples in order to identify the subindexes and add cuts. Some of this functions are transformKey, IRPCStransformKey, keyOpVRP, keyOpTSP, which transform the string keys of each problem to a tuple consisting of the the variable name (y, x or z) and the subindexes as integers.

Finally, there are some functionas that get the variables and constraints from a gurobipy model. This functions are the generators get_expr_coos, get_matrix_coos, get_expr_coos_new, get_matrix_coos_new. The function VisualizeNonZeros Generates a matplotlib plot that visualizes the nonzero elements of the matrix.

The most important function is genClusterNeighborhoods, which uses genAffinityMatrix. This function is used to compute the labels of the variables when created from the constraint-variable cluster.

Neighborhoods

This module contains the Neighborhood class, which handles the changes, import, export and logging of local search depths (depth and neighborhood are synonyms and these words are used interchangeably).

Neighborhood Class:

Attributes

• lowest: (integer) Lowest possible neighborhood number.

• highest: (integer) Highest possible neighborhood number.

• depth: (integer) Current depth of the local search phase.

• keysList:(list of strings) List containing the model variable's names.

• neighborhoods: Description of the instance neighborhoods, parameterizations and fixed variables. Given by the input outerNeighborhoods, which can be either:

  • A dictionary of dictionaries whose keys are the integers associated to each depth and the values are other dictionaries whose keys are the names of the parameterizations and its values are lists or tuples containing the names of the variables fixed in that state. This type of input is used for Physical Neighborhoods.
  • A dictionary whose keys are the integers associated to each depth and the values are lists or tuples containing the names of the parameterizations. This type of input is used for Functional Neighborhoods.

  Each of the keys of this dictionary are the neighborhood numbers, they need to be consecutive integers, otherwise an error occurs. In each of the values of this dictionary there is another dictionary, containing as keys the parameterizations of each of the neighborhoods. The keys of the parameterizations need not to be integers, it suffices to be a hashable Python object (tuple, int, etc...). In the case of Physical Neighborhoods the value asociated to each parameterization is supposed to be a list of strings, each one representing the variable that is fixed in each parameterization.

• useFunction: Indicates if a function will be used to determine when a variable is fixed, i.e if you are using Functional Neighborhoods.

• funNeighborhoods: The function used to determine when a variables is fixed in Local Search. This will only be used if the parameter useFunction is true.

As it is described in the user's guide, neighborhoods can be given by the user, created or set randomly and in this document you can find many examples to get acquainted with the methods.

Methods

• depth : getter and setter methods.
• canTncNeigh : Returns boolean indicating whether neighborhood can be increased.
• resetDepth : changes current depth to the lowest possible, printing a reset message on console.
• createRandomNeighborhoods : Sets neighborhoods randomly, according to input keysList.
• importNeighborhood: Sets neighborhoods according to outer dictionary given.
• exportNeighborhood: Writes current neighborhood in a .txt file (the format is also explained in the other page of the wiki).

Also this three functions help to build the outerNeighborhoods parameter.

• importNeighborhoods : Imports neighborhoods from a txt file.
• genIRPNeighborhoods : Builds the outerNeighborhoods parameter for an IRP instance, provided the number of nodes n, the number of periods H and the number of vehicles K are given.
• genIRPNeighborhoods : Builds the outerNeighborhoods parameter for an IRP instance, provided the number of nodes n, the number of periods H and the number of vehicles K are given, this time with a string key format.

Others

Contains the function loadMPS, which accepts as input a string containing the path of the mps file. This function was required since some constraints or bounds can be modified to be used by Gurobi. For example, integer variables from the mps model that are bounded in [0, 1] are declared as GRB.BINARY in the gurobi model.

Testing

This folder contains the file Test.py and a Folder Logs constaining .testlog files.

Test.py

Module designed to check the execution of the heuristic and to output warnings and the succesfull neighborhood explorations.

The file type .testlog was created to report the overall process (similar to Gurobi log, but way more succint), the automatic creation of this file can be enabled by setting the parameter writeTestLog of the solver function (in VMND.py file). Once the execution of the heuristic is over, the file is saved in the Logs folder and the testing can be performed. To run the test procedure the following command has to be executed from the windows CMD or anaconda prompt:

python Test.py testfile.testlog

of course, the file testfile.testlog must be already in the folder.

The Log Class

The log class is designed to process the .testlog files, it has the followign methods:

• __init__: It takes as parameter a string, which should be the path of the .testlog file.
• run: It processes the input file. A boolean parameter printState can enable a debug step-by-step console print.
• printResults: Prints a summary of the general process: neighborhoods explored and number of succesfull explorations. Also prints warnings if something unexpected occurs.

VMND

This module contains the implementations of the heuristic. The main funcins are:

• testLogUpdate: Function taking as input two parameters, the path and the new Log (both strings). It writes the new Log into the file.

• gapTimesPlot: Takes as input the gaps times list (of tuples of floats), an attribute of the model instance (model._gapsTimes) and shows its matplotlib plot.

• checkVariables: Internal usage. Checks whether all variables in the neighborhoods belong to the loaded mps model.

• SubtourElimCallback: This is a classic Gurobi subtour elimination Callback. This version includes the separation procedure given by the user through the lazy constraint function. The solver function uses this callback if set for.

• VMNDCallback: As every valid Gurobi Callback, the arguments of this function are model and where. A very detailed explanation of this function can be found on the section A detailed Diagram of the callback VMND.

• localSearch: The input of this function is a gurobipy. Model() object. It modifies internally the attributes of the model accoriding to the result of the local search problems. The local search model is loaded from the .mps file and the lazy constraints are added inmediatly. Afterwards, the variables are fixed iteratively by adding constraints to each variable. Finally, the improved solutions if found are stored in an internal parameter of the model. A very detailed explanation of this function can be found on the section A detailed Diagram of the callback VMND.

• solver: It executes the heuristic for a given input model in mps format, its neighborhoods and the separation function. The inputs are the followiing:

  • path : The path where the mps model is located.
  • addLazy : Indicates whether the user will add a separation function to add additional constraints.
  • funLazy : The separation function to be used, if previous argument addLazy is True.
  • importNeighborhoods : Indicates whether the user will his own neighborhoods or not.
  • importedNeighborhoods : The neighborhoods to be used, if previous argument importNeighborhoods is True.
  • funTest : A function used to corroborate that output valriables meet the expecteed results, in most cases to check subtour errors.
  • callback : The heuristic which is to be used. For VMND heuristic use 'vmnd'. For any other input string pure B&C will be used.
  • verbose : If true, prints in console the local search and branch and cut log.
  • minBCTime : A float indicating the minimum amount of time that should be spent on Branch and Cut on each iteration of VMND.
  • timeLimitSeconds : A float indicating the time limit executing the model. If this is not desired, this input should be None.
  • writeTestLog : A boolean which enables the creation of a .testlog file, with a summary of the execution of the Heuristic. The summary can be processed by running the Test.py file (in the Testing folder).
  • plotGapsTime : A boolean that activates the storage of gaps and times every 5 seconds. A plot showing the evolution of the MIPGAP through time is shown at the end of the execution.

• creator: Loads model from given path.

• compareGaps: This function is not yet ready. Its purpose is to plot and save the perfomance (MIPGap vs time) of both pure B&C and VMND.