Optimization Online


Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method

Thomas Kleinert (thomas.kleinert***at***fau.de)
Martin Schmidt (martin.schmidt***at***uni-trier.de)

Abstract: Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain feasible points of good quality quickly or to enhance the search process of exact global methods. However, there are comparably few heuristics for bilevel problems. In this paper, we develop such a primal heuristic for bilevel problems with mixed-integer linear or quadratic upper level and linear or quadratic lower level. The heuristic is based on a penalty alternating direction method, which allows for a theoretical analysis. We derive a convergence theory stating that the method converges to a stationary point of an equivalent single-level reformulation of the bilevel problem and extensively test the method on a test set of more than 2800 instances - which is one of the largest computational test sets ever used in bilevel programming. The study illustrates the very good performance of the proposed method, both in terms of running times and solution quality. This renders the method a suitable sub-routine in global bilevel solvers as well as a reasonable standalone approach.

Keywords: Bilevel optimization, Mixed-integer bilevel optimization, Stationary points, Penalty methods, Alternating direction methods

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 03/11/2019
Entry Accepted: 03/11/2019
Entry Last Modified: 05/06/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society