A Branch-and-Price algorithm for a compressor scheduling problem

This work presents a Branch-and-Price algorithm for solving a compressor scheduling problem with applications in oil production. The problem consists in defining a set of compressors to be installed for supplying the gas-lift demand of oil wells while minimizing the associated costs. Owing to the non-convex nature of the objective function, two piecewise-linear formulations are tested in the pricing subproblem, which is solved with a two-phase strategy. Also, two branching strategies are proposed based on the original problem variables, and a specific rule is created for solving the master problem as an integer program for obtaining feasible solutions. Experimental results are reported for three sets of instances, for which the branch-and-price algorithm obtained more optimal solutions, and spent less time on average than the CPLEX solver applied to the piecewise-linear formulation. Furthermore, for the solution of the largest instances within a limited computational time, the proposed branch-and-price algorithm found good feasible solutions, outperforming CPLEX.