Airline scheduling problems are an example of a more complex type of scheduling that takes into account a lot of restrictions and regulations posted by airline companies. In this paper, the accent is on solving the crew pairing problem – grouping series of duties with breaks which cover flights in the way that crew begins and ends the journey at the same base. Mathematically saying, we describe this problem by optimization problem, or to be more precisely, by the problem of integer linear programming. The goal is finding optimal pairings with minimal cost to cover each flight exactly once. We give a standard formulation of the problem and suggest methods for its solving. The linear problem which is used to describe the crew pairing problem usually has a lot of conditions. We reduce the number of conditions by applying Dantzig–Wolfe decomposition on the problem. Dantzig–Wolfe decomposition is based on representation theorem of polyhedron. We represent polyhedron in terms of its extreme points and extreme rays, which usually makes the number of variables very large. Solving a linear problem with large number of variables is more complex, so there is a need for an effcient method for solving it. The column generation method is applied on a restricted master problem with a small subset of columns. In each iteration, it looks for a non-basic variable to enter the base and optimize the objective function. We get a decision to generate a new column by solving pricing subproblem. If condition matrix has a block–diagonal structure, the formulation of the linear programming problem in terms of Dantzig–Wolfe decomposition in a combination with column generation can be applied to the parallel subproblem solving instead of solving the original problem. There is the theory of duality behind the theory of the column generation. Another approach to problem solving is Lagrange relaxation. It is the approach that enables reshaping the model by removing complicated conditions and putting them to the objective function with addition of a Lagrangian multiplier. Elaboration of the theory of Lagrange relaxation leads to the conclusion that for any value of the Lagrange multiplier the optimal value of the relaxed problem is the lower bound for the optimal value of the objective function of the original problem. The goal is to find the best possible lower bound, i.e. to find the multiplier of the highest quality for which the optimal value of Lagrangian relaxed problem is as large as possible – we solve Lagrangian dual problem. Further, we consider the convexification of the Lagrangian dual, which allows us to apply the Dantzig-Wolfe decomposition, i.e., set formulation in terms of its extreme points and extreme rays. There is a description of an approach for solving the problem of integer linear programming by column generation. Finally, since the enumeration of pairings from the first, traditional formulation of the problem can be very demanding, we offer a different formulation of the crew pairing problem. The advantage of the new problem formulations is that its linear relaxation provides stronger bound on the optimal value of objective function of the original problem compared to the linear relaxation of the problem according to the traditional formulation.