Several engineering problems are modeled as linear bilevel programs (linear BLPs) where one problem (upper-level problem) has constrained variables which are optimal solutions of another problem (lower-level problem). The well-known single-level reformulation approach replaces the lower-level linear program with its Karush-Kuhn-Tucker optimality conditions and then linearizes the complementary slackness conditions employing the big-M technique. Although this approach is relatively simple and upstanding, it requires finding the disjunctive parameters (big-M). Regularly heuristic techniques are used to tune the big-M parameters. It is well-known that these techniques could fail, even though they are common. Finding the correct big-M parameters is computational challenging and it is recently shown to be NP-hard in several applications. This research presents a new parameter-free disjunctive decomposition algorithm tailored for the linear BLPs which (1) does not need finding the big-M parameters, (2) guarantees that the obtained solution is optimal to the given linear BLP, and (3) it is computationally advantageous. Our experience shows promising performance of the proposed algorithm in solving several linear BLPs.
QC 20210629