We explore the possibility of solving bilevel linear programming problems using multiple objective linear programming. New multiple objective algorithms are developed and their performance, in pivots and pivot volume, is compared to the Bard and Moore branch and bound algorithm using performance ratios and performance profiles.

We introduce new valid cuts for the continuous bilevel linear programming (BLP) problems. Then we propose a new Branch-and-Cut algorithm for BLP. The first phase of our algorithm generates the new cuts to reduce the size of the feasible region without eliminating the optimal solution. The second phase consists of a Branch-and-Bound procedure to ensure finite termination with a global optimal solution. Different features of the algorithm, in particular, the cut selection criterion and the branching criterion are studied in details. We also propose a set of algorithmic tests and procedures to improve the method. Finally, we illustrate the performance through numerical experiments. Our algorithm outperforms pure Branch-and-Bound when tested on a series of randomly generated problems.

La présentation a pour but d'illustrer comment des coupes disjonctives peuvent être générées pour un programme biniveau linéaire. Les résultats fondamentaux en programmation disjonctive seront présentés, et une application à la programmation 0-1 sera illustrée à l'aide d'un exemple. On introduit alors le programme biniveau linéaire, pour ensuite le reformuler sous forme de programme de complémentarité linéaire. Avec cette formulation, on peut voir le programme biniveau comme un programme disjonctif. Nous montrons ensuite comment il est possible de produire des coupes disjonctives pour le programme biniveau linéaire.

We consider a pricing problem where a company (a leader) strives to maximize its revenue raised from tariffs imposed on a set of network connections in its control while taking into account the cost minimizing behaviour of the customers. This problem, involving two decision makers acting non cooperatively and in a sequential way, is modeled through a bilevel program. We propose an exact method based on the characterization of feasible follower solutions as sets of paths. A comparison on instances solved to optimality through a mixed integer formulation is made to assess the efficiency of the method.