Home

In this page you will learn how the VMND Heuristic works and how to properly download this repository to apply it to your MIP of interest!

¿What is VMND?

VMND is a hybrid algorithm for solving MIP which combines iteratively Branch and Cut with Local Search. This technique was proposed by Larrain et al in 2017 and has significantly outperformed benchmark solutions from other Branch and Cut algorithms.

As it was said before, this metaheuristic works by alternating phases of local search and branch and cut. The first step of this algorithm consists of finding an initial feasible solution (regarding integrality), then the algorithm enters into the Local Search Phase. The local search is performed by fixing some strategically chosen variables of the model and solving it. In case this new solution improves the current objective function, this solution is given to the Branch and Bound tree, as a heuristic. The branch and Cut is executed until a new improved solution is found, which will be given as input to the local search phase again.

The Local Search Phase works by searching solutions in a set of neighborhoods N. This neighborhood's set can be defined as the solutions reachable by applying an operator F into a solution X, also they are to be sorted from the smallest to the largest in terms of its MIP size. Each neighborhood n, has associated to it a set of valid parameterizations 1, ..., p_n, which correspond to the amount of different ways it is possible to alter the original solution by means of this operator. For example, let's consider a multiperiod, multivehicle routing problem:

• One possible neighborhood can be that one associated to the different routes of this problem. A valid parameterization in this neighborhood can be (1, 2) which corresponds to the route of the first vehicle in the second period. So if we have K vehicles and H periods, this neighborhood shall contain K * H different parameterizations. So, in this parameterization all model's variables are fixed except for those which somehow concern the vehicle 1 in the period 2.
• Another possible neighborhood can be the different periods of this instance. In this case, we have as many parameterizations as periods (from 1 to H). We can see that this is a much broader neighborhood, which includes the previous one (in each period), since the route parameterizations of all K vehicles on period h (from 1 to H) are contained inside the h'th parameterization of this neighborhood.

According to this definition, neighborhoods and its parameterizations are to be explored cyclically and in order. As it is shown in Explanation Diagram, Local Search Phase is commenced with an initial solution and then explores the first neighborhood, from the first to the last parameterization, searching for an improvement of the MIP incumbent (or a better improvement in case it finds one in a previous parameterization). Instead of solving until optimality the model in each parameterization, the solver is instructed to stop as soon as it finds an improvement. Finally, if a new solution is found, it is given to the Branch and Bound tree as a heuristic solution.

Explanation Diagram

If no improvement is found in the first neighborhood, the Local Search Phase begins exploring the second neighborhood and so on until the last one. If every single neighborhood is exhausted, the Branch and Cut procedure carries on with the same solution. The time set for Branch and Cut is set as alpha (a parameter given by the user) times the time spent on Local Search in case a new solution is found, otherwise time is not restriced and the algorithm performs Branch and Cut until a new incumbent is found.

Installation

This library was developed in Python 3.7 with Gurobi 8.1 as solver. The Gurobi license must be set and gurobipy must be installed with anaconda. The following packages are needed as well:

• conda 4.8.3 py37_0
• matplotlib 3.1.0
• networkx 2.3
• numpy 1.16.4
• pytest 5.0.1
• scikit-learn 0.21.2
• sklearn 0.0
• scipy 1.2.1

With these requirements met, you can just download the repository and import its functions and modules.

Features

This repository contains an implementation of the VMND heuristic in the module VMND.py. The neighborhoods and its parameterizations can be created automatically from the model (randomly or by more sophisticated techniques) or declared by the user. Also, as many routing problems need the aggregation of Lazy Constraints as well (typically subtour elimination), this procedure can be embedded into the Branch and Cut procedure through a user defined separation function.

Finally, some instances from the OR Brescia Instance Compilation were implemented as Gurobi models, such as:

• VRP
• MVRP
• IRPCS
• IRP
• OISCR

Furthermore, in the Experiments Module several instances can be executed, with different neighborhood variants as well as pure Branch and Cut. This module is specially desiged for running in a cluster/AWS, see more about it in the Experiments page.

A more detailed description of each problem can be found in User's Guide.

Contact us!

In case anything unusual occurs or you want to comment something, feel free to raise an issue or email me at micostabal "at" uc "dot" cl.

Citing this Repository

You can use the following Bibtex misc reference:

@misc{VMNDRepository,
    author       = {Martín Costabal, Homero Larrain},
    title        = {{VMND}},
    version      = {1.0},
    url          = {https://github.com/micostabal/VMND}
    }