A Branch-and-Price algorithm for a compressor scheduling problem. (February 2018) - Friske, Marcelo Wuttig; Buriol, Luciana S.; Camponogara, Eduardo
Highlights: We developed a branch-and-price algorithm for a compressor scheduling problem. We tested two piecewise-linear formulations to handle the non-convex objective. A two-phase approach is used for the pricing subproblem. Two branch rules was applied to guide the search. The proposed algorithm is faster and provide better solutions than CPLEX. Abstract: 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.