Minimizing Cash-Out Penalty Costs: A Bilevel Programming Model

Abstract: Natural gas pipeline operations inevitably involves imbalances. Most pipelines allow for some small imbalance tolerances. However, if imbalances are not resolved by the end of the month, the pipeline will penalize the shipper by imposing cash out prices. End-of-the-month imbalances are resolved by cash transactions between the pipeline and the shippers based on such prices. Depending on the amount of the imbalance position, this penalty may be onerous. Nevertheless, as long as one can anticipate the amount of penalty associated with a given imbalance position on any given day, day to day operations can be managed accordingly. The problem, is how to optimally managing shippers daily imbalance positions so as to minimize the cash-out penalty impossed by the pipeline company. We introduce a mixed integer bilevel programming model for this problem, and propose a conceptual simulated annealing heuristic.