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.

On a New Class of Bilevel Programming Problems and its Use For Reformulating Mixed Integer Problems

FRANGIONI, ANTONIO
1995

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/29412
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 9
social impact