Links Between Linear Bilevel and Mixed 0–1 Programming Problems |
| |
| Authors: | Audet C Hansen P Jaumard B Savard G |
| |
| Institution: | (1) Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal, Montréal, Québec, Canada;(2) Département MQ, École des Hautes Études Commerciales and GERAD, Montréal, Québec, Canada;(3) Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada;(4) Département de Mathématiques et de Génie Industriel, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada |
| |
| Abstract: | We study links between the linear bilevel and linear mixed 0–1 programming problems. A new reformulation of the linear mixed 0–1 programming problem into a linear bilevel programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0–1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0–1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation; i.e., when applied to any mixed 0–1 instance and its bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation. |
| |
| Keywords: | Bilevel programming mixed 0– 1 programming embedded algorithms branch-and-bound methods |
| 本文献已被 SpringerLink 等数据库收录！ |
|
