Linear programming (LP) is a technique for optimizing a linear objective function subject to linear constraints. The interior point method (IPM) is one of the most efficient and widely used algorithms for solving LP problems. In this article, you will learn the basic steps to effectively use the IPM for LP.
The IPM is a class of algorithms that iteratively find an optimal solution by moving along the feasible region of the LP problem. Unlike the simplex method, which moves along the edges of the feasible region, the IPM moves through the interior of the region, hence the name. The IPM has several advantages over the simplex method, such as faster convergence, better numerical stability, and scalability to large problems.
Before applying the IPM, you need to formulate the LP problem in a standard form. This means that the objective function is a linear function of the decision variables, the constraints are linear equalities, and the decision variables are non-negative. You can convert any LP problem to this form by using techniques such as introducing slack or surplus variables, changing the signs of variables or coefficients, and splitting variables into positive and negative parts.
The IPM requires a feasible starting point, which means a point that satisfies all the constraints and has positive values for the decision variables. There are several methods for finding such a point, such as using a phase one procedure, applying a heuristic, or solving a related problem. The choice of the starting point may affect the performance and the convergence of the IPM, so it is important to select a good one.
The IPM generates a search direction by solving a system of linear equations that incorporates the objective function, the constraints, and a barrier function. The barrier function is a term that penalizes points that are close to the boundary of the feasible region, and ensures that the IPM stays in the interior. The search direction is a vector that points to a better solution, and is usually computed by using Newton's method or a variant of it.
The IPM updates the solution by moving along the search direction by a certain step size. The step size determines how far the IPM moves in each iteration, and is usually chosen to maintain feasibility and decrease the objective function value. The step size can be computed by using a line search method, such as backtracking or Armijo rule, or by using a fixed or adaptive rule.
The IPM checks for optimality by using a stopping criterion that measures the distance from the optimal solution. The stopping criterion is usually based on the duality gap, which is the difference between the primal and the dual objective function values. The duality gap is zero at the optimal solution, and decreases as the IPM converges. The IPM stops when the duality gap is smaller than a given tolerance, or when it reaches a maximum number of iterations.
Most people don’t need to worry about the content in this article. It’s very unlikely that you will have to code up an algorithm for solving linear programs (LP) from scratch. Your job will most likely involve you modeling the LP and calling a solver to solve the problem. Additionally, state-of-the-art solvers like Gurobi or CPLEX have a variety of options to help speed up the solve time.
You do not need to implement the Interior Point Method (IPM) from scratch by yourself. It is already available in most of the commercial solvers like CPLEX, or Gurobi with the name as Barrier Methods. Just skip the steps after the second one, implement your model in one of the solvers, select Barrier as an optimizer for your problem and move forward...