Linear bilevel programs (linear BLPs) have been widely used in computational mathematics and optimization in several applications. Single-level reformulation for linear BLPs replaces the lower-level linear program with its Karush-Kuhn-Tucker optimality conditions and linearizes the complementary slackness conditions using the big-M technique. Although the approach is straightforward, it requires finding the big-M whose computation is recently shown to be NP-hard. This paper presents a disjunctive-based decomposition algorithm which does not need finding the big-Ms, whereas guaranteeing that obtained solution is optimal. Our experience shows promising performance of our algorithm.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The (In)Famous Big-M Technique for Solving Bilevel Programs

  • Saeed Mohammadi,
  • Mohammad Reza Hesamzadeh,
  • Dina Khastieva

摘要

Linear bilevel programs (linear BLPs) have been widely used in computational mathematics and optimization in several applications. Single-level reformulation for linear BLPs replaces the lower-level linear program with its Karush-Kuhn-Tucker optimality conditions and linearizes the complementary slackness conditions using the big-M technique. Although the approach is straightforward, it requires finding the big-M whose computation is recently shown to be NP-hard. This paper presents a disjunctive-based decomposition algorithm which does not need finding the big-Ms, whereas guaranteeing that obtained solution is optimal. Our experience shows promising performance of our algorithm.