Column Generation in Integer Linear Programming

This chapter introduces exact methods for solving integer linear programming problems with a large number of variables. These methods are known as branch-and price methods. The chapter examines an inequality for eliminating 0–1 column generation and it focuses on two integer linear programming problem models and a comparison between their linear relaxations. The chapter presents a schema of a column generation method for solving an integer linear programming (ILP) and the difficulties that can appear at the time of implementation. In the chapter two column generation algorithms are introduced: for the p-medians problem and for vehicle routing problems.