Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A New Approach for Solving Linear Bilevel Programs Based on Parameter-Free Disjunctive Decomposition
KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electric Power and Energy Systems.ORCID iD: 0000-0003-1823-9653
KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electric Power and Energy Systems.ORCID iD: 0000-0002-9998-9773
Department of Mechanical Engineering, University of Maryland, Maryland, USA.
KTH, School of Electrical Engineering and Computer Science (EECS), Electrical Engineering, Electric Power and Energy Systems.ORCID iD: 0000-0001-9448-6061
2021 (English)Conference paper, Oral presentation with published abstract (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
2021.
Keywords [en]
Linear bilevel program, bilevel optimization, big-M technique, disjunctive-based decomposition, linear programming.
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering
Research subject
Applied and Computational Mathematics, Optimization and Systems Theory; Electrical Engineering; Järnvägsgruppen - Elsystem
Identifiers
URN: urn:nbn:se:kth:diva-297984OAI: oai:DiVA.org:kth-297984DiVA, id: diva2:1573274
Conference
31st European Conference on Operational Research (EURO2021)
Note

QC 20210629

Available from: 2021-06-24 Created: 2021-06-24 Last updated: 2024-03-18Bibliographically approved

Open Access in DiVA

fulltext(93 kB)83 downloads
File information
File name FULLTEXT01.pdfFile size 93 kBChecksum SHA-512
b709f6d8a5adfef26df807e5de999646af5572497b365dec25c4491c0f3f9c38d339de921acf7de324d85c8d7002e71ddc9c93fe4ed728b1cfd0c460d827bc46
Type fulltextMimetype application/pdf

Other links

Conference website

Search in DiVA

By author/editor
Mohammadi, SaeedHesamzadeh, Mohammad RezaKhastieva, Dina
By organisation
Electric Power and Energy Systems
Other Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 84 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 335 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf