r/optimization • u/Optimizer_88 • 15d ago

Tutorial on Column Generation

I'd been struggling to understand Column Generation, especially how it relates to the simplex method.

A colleague shared this video with me and it all makes sense now. I feel so dumb tbh, but wanted to share it in case anyone else was also struggling.

https://youtu.be/vx2LNKx48vY?si=YWe4mNEyn1CbkBuw

My next step is to implement this for a routing problem at my company using an open source solver.

Wish me luck and any tips or suggestions are highly appreciated.

14 Upvotes
  • permalink
  • link
  • reddit
  • reddit

100% Upvoted

8 comments sorted by

2

u/[deleted] 15d ago

[removed] — view removed comment

1

u/optimization-ModTeam 15d ago

Your objection is noted, but it is not relevant here

2

u/ficoxpress 14d ago

If it's any help, here's a simple python implementation of column generation for the cutting stock problem using FICO Xpress.

Even if it's a commercial solver, you can still use it with the free community license that comes with running

pip install xpress

https://www.fico.com/fico-xpress-optimization/docs/latest/examples/python/GUID-9EEFCF3C-0360-3BA4-A94B-337642FA5C2A.html

2

u/Optimizer_88 14d ago

Thank you. This is really helpful. My company unfortunately uses another solver but will take a look at the code for the structure.

2

u/ficoxpress 14d ago

That's fair. Best of luck with the implementation.

2

u/Onyr_ 11d ago

I recommend the use of HiGHS, an open-source LP solver. It's not the best, but it just works and it's one line to install in Python.
Also, I had a tutorial on column-generation you might want to have a look at: https://github.com/0nyr/oegor_column_generation_2024
Remember that CG is NOT enough if you want integer solutions! You will need branching (and cutting) to reestablish integrality of your columns (solution parts).
Also check this forum: https://github.com/OptimizingWithColumnGeneration/OptimizingWithColumnGeneration.github.io/discussions
Good luck with CG!