Discrete bilevel programming: Application to a natural gas cash-out problem

In this paper, we present a mathematical framework for the problem of minimizing the cash-out penalties of a natural gas shipper. The problem is modeled as a mixed-integer bilevel programming problem having one Boolean variable in the lower level problem. Such problems are difficult to solve. To obtain a more tractable problem we move the Boolean variable from the lower to the upper level problem. The implications of this change of the problem are investigated thoroughly. The resulting lower level problem is a generalized transportation problem. The formulation of conditions guaranteeing the existence of an optimal solution for this problem is also in the scope of this paper. The corresponding results are then used to find a bound on the optimal function value of our initial problem.