"A primer in Column Generation" is the first chapter of the book Column Generation, which is a good tutorial for Column Generation Techniques for solving integer linear programming problems.
This paper is divided into four parts:
This first part provides an example to motivate the column generation, which is shortest path problem with a time constraint. It provides detailed solution steps using column generation within the branch-and-bound framework.
The second part provides theoretical part and introduces the Dantzig-Wolfe Decomposition.
The third part gives a dual point of view of the Dantzig-Wolfe Decomposition, which is the Lagrangian relaxation.
The fourth part actually hits a hot topic these days, how to exploit the matrix structure for diagonal blocks, which is the title of those days-"on finding a good formulation"
No comments:
Post a Comment