A Branch-and-Price algorithm for a compressor scheduling problem. (February 2018)

• Record Type: Journal Article
• Authors: Friske, Marcelo Wuttig; Buriol, Luciana S.; Camponogara, Eduardo
• Is Part Of: Computers & industrial engineering. Volume 116(2018)
• Page Start: 72
• Page End: 81
• Publication Date: 2018-02
• Subjects: Compressor scheduling problem -- Branch-and-price -- Column generation -- Piecewise-linear formulation; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2017.12.022
• Languages: English
• ISSNs: 0360-8352

Abstract

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.