On a new class of Bilevel Programming Problems and its use for reformulating Mixed Integer Problems

On a new class of Bilevel Programming Problems and its use for reformulating Mixed Integer Problems

0.00 Avg rating0 Votes
Article ID: iaor19981313
Country: Netherlands
Volume: 82
Issue: 3
Start Page Number: 615
End Page Number: 646
Publication Date: May 1995
Journal: European Journal of Operational Research
Authors:
Keywords: programming: integer
Abstract:

We extend some known results about the Bilevel Linear Problem (BLP), a hierarchical two-stage optimization problem, showing how it can be used to reformulate any Mixed Integer (Linear) Problem; then, we introduce some new concepts, which might be useful to fasten almost all the known algorithms devised for BLP. As this kind of reformulation appears to be somewhat artificial, we define a natural generalization of BLP, the Bilevel Linear/Quadratic Problem (BL/QP), and show that most of the exact and/or approximate algorithms originally devised for the BLP, such as GSA or K-th Best, can be extended to this new class of Bilevel Programming Problems. For BL/QP, more ‘natural’ reformulations of MIPs are available, leading to the use of known (nonexact) algorithms for BLP as (heuristic) approaches to MIPs: we report some contrasting results obtained in the Network Design Problem case, showing that, although the direct application of our (Dual) GSA algorithm is not of any practical use, we obtain as a by-product a good theoretical characterization of the optimal solutions set of the NDP, along with a powerful scheme for constructing fast algorithms for the Minimum Cost Flow Problem with piecewise convex linear cost functions.

Reviews

Required fields are marked *. Your email address will not be published.