This is the third part of the tutorial on Column generation. The links to previous parts are Part1 and Part2.

We are now entering the hardest part of the Column Generation algorithm. Let’s put aside the CG and just focus on the subproblem i.e. SPPRC. Fully explaining the SPPRC without using mathematical notation is a challenging task, so I will post links for further reading along the way to anyone interested. We will only look at a dynamic programming-based exact algorithm in this part. The algorithm presented here is only a basic version to give readers a taste of solving…

(This article is a sequel to Part 1 of the tutorial.)

In this part, we will look at the Column Generation (CG) algorithm and then discuss some aspects of the subproblem. As there will be a lot to cover in the subproblem, we will only look at some intuition of solving the subproblem. The next article on this series will be dedicated to the subproblem’s algorithm and more details. As usual, we will keep the mathematical jargon limited to only where absolutely required.

Figure 2.1 shows the primal and the dual of the Master Problem (MP) introduced in Part 1…

Mixed Integer Problems (MIP) are central to solving most of the decision-making problems both in academia and industry. Although being used in the majority of decision-making problem formulations, MIPs are notorious for requiring high computation power and time to solve for practical-sized problems. For sure, recent advancements in solvers like Gurobi, FICO, Cplex, etc. have made cutting edge improvements in solving time for MIPs but the exponential nature of the problem makes it difficult to scale. As such the use of advanced decomposition algorithms like Column Generation (CG) can be useful. …

Nabin Kafle

Operations Research Develper at Southwest Airlines

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store