A sequential LCP method for bilevel linear programming

• Type: Article in International Scientific Journal
• Date: 1991

Authors

J. Júdice (Author) Other; Ana Maria Faustino (Author) FEUP

Journal

Title: Annals of Operations Research

Vol. 34

Pages: 89-106

ISSN: 0254-5330

Publisher: Springer Nature

Scientific classification

FOS: Engineering and technology > Other engineering and technologies

CORDIS: Physical sciences > Computer science > Programming

Other information

Resumo (PT): In this paper, we discuss an SLCP algorithm for the solution of Bilevel Linear Programs (BLP) which consists of solving a sequence of Linear Complementarity Problems (LCP) by using a hybrid enumerative method. This latter algorithm incorporates a number of procedures that reduce substantially the search for a solution of the LCP or for showing that the LCP has no solution. Computational experience with the SLCP algorithm shows that it performs quite well for the solution of small- and medium-scale BLPs with sparse structure. Furthermore, the algorithm is shown to be more efficient than a branch-and-bound method for solving the same problems.

Abstract (EN): In this paper, we discuss an SLCP algorithm for the solution of Bilevel Linear Programs (BLP) which consists of solving a sequence of Linear Complementarity Problems (LCP) by using a hybrid enumerative method. This latter algorithm incorporates a number of procedures that reduce substantially the search for a solution of the LCP or for showing that the LCP has no solution. Computational experience with the SLCP algorithm shows that it performs quite well for the solution of small- and medium-scale BLPs with sparse structure. Furthermore, the algorithm is shown to be more efficient than a branch-and-bound method for solving the same problems.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18