A natural gas cash-out problem:: A bilevel programming framework and a penalty function method

One of the many complex problems that arise from the transmission and marketing of natural gas is when a shipper draws a contract with a pipeline company to deliver a certain amount of gas among several points. What is actually delivered is often different from the amount that had been originally agreed upon. This phenomenon is called an imbalance. When an imbalance occurs, the pipeline penalizes the shipper by imposing a cash-out penalty policy. Since this penalty is a function of the operating daily imbalances, an important decision-making problem for the shippers is how to carry out their daily imbalances so as to minimize their incurred penalty. In this paper, we introduce the problem of minimizing the cash-out penalty costs from the point of view of a natural gas shipping party. We present a mixed integer bilevel linear programming model and discuss its underlying assumptions. To solve it efficiently, we reformulate it as a standard mathematical program and describe a penalty-function algorithm functions for its solution. The algorithm is well-founded and its convergence is proved. Results of numerical experiments support the algorithm's robustness providing a valuable solution technique for this very important and complex problem in the natural gas market.