Implementing Column Generation algorithms

[gustavocmv]

Hi!

Python-MIP currently supports Constraint Generation through the model.cuts_generator and model.lazy_constrs_generator, and there is a great example in the Docs concerning the Traveling Salesman Problem and the sub-tours elimination constraint.

However, I can't find any example of how to implement Column Generation schemes such as the ones commonly used to solve Vehicle Routing Problems with the Set Covering formulation, where the column-generating subproblem is usually solved using the Constrained Shortest Path problem. Does anyone have a column generation MWE available to share? I would love to study it and also contribute the implementation to Python-MIP docs if the maintainers feel it would be a good addition.

Edit: There is a library called vrpy implementing this approach to the VRP, but it uses PuLP as the python interface to the MIP Solver and the development seems to be stale.

[rschwarz]

It may not be documented well, but there is a test case for column generation: test_column_generation

[gustavocmv]

@rschwarz thanks for pointing it out!
I will study it and try to implement it for my use case.

@tuliotoffolo @h-g-s would a documented example of column generation be a good addition to the docs?

[sebheger]

@gustavocmv feel free to add a PR with an extended example :-)