An Algorithm to Solve a Gas Cash-Out Problem

Abstract: In this paper, an algorithm for solving a natural gas cash-out problem is proposed. The problem is modeled as a mixed bi-level linear programming problem. Our proposed algorithm is based on a direct iterative scheme which splits the computation into two almost independent stages: (1) search for the pipeline's optimal response and, based upon that, the gas shipper's optimal distribution of the last day gas imbalances; (2) verifying the feasibility of the obtained optimal distribution of the last day imbalances (which involves solution of a quadratic programming problem). This idea of splitting leads to a computational scheme that may be valid for a wide enough class of bilevel programming problem. The algorithm is illustrated by solving a test instance.