# Shortest Path Problem with Resources Constraint (SPPRC)

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…

# A tutorial on using Column Generation to solve MIP problems (Part 2)

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…

# A tutorial on using Column Generation to solve MIP problems (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