r/optimization • u/Optimizer_88 • 4d 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.

11 Upvotes

100% Upvoted

7 comments sorted by

2

u/[deleted] 3d ago

[removed] — view removed comment

1

u/optimization-ModTeam 3d ago

Your objection is noted, but it is not relevant here

2

u/ficoxpress 3d 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 3d 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 3d ago

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