A class of algorithms for mixed-integer bilevel min–max optimization

Yen Tang, Jean Philippe P. Richard, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

Abstract

In this paper, we introduce a new class of algorithms for solving the mixed-integer bilevel min–max optimization problem. This problem involves two players, a leader and a follower, who play a Stackelberg game. In particular, the leader seeks to minimize over a set of discrete variables the maximum objective that the follower can achieve. The complicating features of our problem are that a subset of the follower’s decisions are restricted to be integer-valued, and that the follower’s decisions are constrained by the leader’s decisions. We first describe several bilevel min–max programs that can be used to obtain lower and upper bounds on the optimal objective value of the problem. We then present algorithms for this problem that finitely terminate with an optimal solution when the leader variables are restricted to take binary values. Finally, we report the results of a computational study aimed at evaluating the quality of our algorithms on two families of randomly generated problems.

Original languageEnglish (US)
Pages (from-to)225-262
Number of pages38
JournalJournal of Global Optimization
Volume66
Issue number2
DOIs
StatePublished - Oct 1 2016
Externally publishedYes

Bibliographical note

Funding Information:
The authors gratefully acknowledge an anonymous referee, whose remarks led to an improved presentation of our research. This work has been supported by the National Science Foundation through Grant CMMI-11000765, the Defense Threat Reduction Agency through Grant HDTRA1-10-1-0050, the Air Force Office of Scientific Research under Grant FA9550-12-1-0353, and the Office of Naval Research under grant N000141310036.

Publisher Copyright:
© 2015, Springer Science+Business Media New York.

Keywords

  • Algorithms
  • Bilevel programming
  • Integer programing
  • Interdiction problems

Fingerprint

Dive into the research topics of 'A class of algorithms for mixed-integer bilevel min–max optimization'. Together they form a unique fingerprint.

Cite this