<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1671</id>
    <completedYear>2024</completedYear>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>255</pageFirst>
    <pageLast>285</pageLast>
    <pageNumber>31 Seiten</pageNumber>
    <edition/>
    <issue>1</issue>
    <volume>47</volume>
    <type>article</type>
    <publisherName>Springer</publisherName>
    <publisherPlace>Berlin/Heidelberg</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-06-05</completedDate>
    <publishedDate>2024-06-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Robust combinatorial optimization problems under budgeted interdiction uncertainty</title>
    <abstract language="eng">In robust combinatorial optimization, we would like to find a solution that performs well under all realizations of an uncertainty set of possible parameter values. How we model this uncertainty set has a decisive influence on the complexity of the corresponding robust problem. For this reason, budgeted uncertainty sets are often studied, as they enable us to decompose the robust problem into easier subproblems. We propose a variant of discrete budgeted uncertainty for cardinality-based constraints or objectives, where a weight vector is applied to the budget constraint. We show that while the adversarial problem can be solved in linear time, the robust problem becomes NP-hard and not approximable. We discuss different possibilities to model the robust problem and show experimentally that despite the hardness result, some models scale relatively well in the problem size.</abstract>
    <parentTitle language="eng">OR Spectrum (ISSN: 1436-6304)</parentTitle>
    <identifier type="issn">0171-6468</identifier>
    <identifier type="issn">1436-6304</identifier>
    <identifier type="doi">10.1007/s00291-024-00772-0</identifier>
    <identifier type="urn">urn:nbn:de:101:1-2408131120370.349068848723</identifier>
    <enrichment key="opus.import.date">2025-07-29T13:01:01+00:00</enrichment>
    <enrichment key="opus.source">sword</enrichment>
    <enrichment key="opus.import.user">deepgreen</enrichment>
    <enrichment key="opus.import.file">attachment; filename=deposit.zip</enrichment>
    <enrichment key="opus.import.checksum">ba97655ed15adedd1cf0f5a19b155125</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">false</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <author>Marc Goerigk</author>
    <author>Mohammad Khosravi</author>
    <subject>
      <language>eng</language>
      <type>swd</type>
      <value>-</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Robust optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Budgeted uncertainty</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Knapsack uncertainty</value>
    </subject>
    <collection role="ddc" number="330">Wirtschaft</collection>
    <collection role="open_access" number="">open_access</collection>
    <collection role="institutes" number="">Wirtschaftswissenschaftliche Fakultät</collection>
    <collection role="Import" number="import">Import</collection>
    <collection role="Transformationsvertrag" number="">DEAL Springer Nature</collection>
    <thesisPublisher>Universität Passau</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-uni-passau/files/1671/00291_2024_Article_772.pdf</file>
  </doc>
  <doc>
    <id>1875</id>
    <completedYear>2024</completedYear>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber>16 Seiten</pageNumber>
    <edition/>
    <issue>166</issue>
    <volume>2024</volume>
    <type>article</type>
    <publisherName>Elsevier</publisherName>
    <publisherPlace>Amsterdam</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-03-04</completedDate>
    <publishedDate>2024-03-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Benchmarking problems for robust discrete optimization</title>
    <abstract language="eng">Robust discrete optimization is a highly active field of research where a plenitude of combinations between decision criteria, uncertainty sets and underlying nominal problems are considered. Usually, a robust problem becomes harder to solve than its nominal counterpart, even if it remains in the same complexity class. For this reason, specialized solution algorithms have been developed. To further drive the development of stronger solution algorithms and to facilitate the comparison between methods, a set of benchmark instances is necessary but so far missing. In this paper we propose a further step towards this goal by proposing several instance generation procedures for combinations of min–max, min–max regret, two-stage and recoverable robustness with interval, discrete, budgeted or ellipsoidal uncertainty sets. Besides sampling methods that go beyond the simple uniform sampling method that is the de-facto standard to produce instances, also optimization models to construct hard instances are considered. Using a selection problem for the nominal ground problem, we are able to generate instances that are several orders of magnitudes harder to solve than uniformly sampled instances when solving them with a general mixed-integer programming solver. All instances and generator codes are made available online.</abstract>
    <parentTitle language="eng">Computers &amp; Operations Research (Online ISSN: 1873-765X)</parentTitle>
    <identifier type="doi">10.1016/j.cor.2024.106608</identifier>
    <identifier type="urn">urn:nbn:de:bvb:739-opus4-18752</identifier>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <enrichment key="review.accepted_by">2</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <author>Marc Goerigk</author>
    <author>Mohammad Khosravi</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Robust optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Benchmarking</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Instance generator</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Combinatorial optimization</value>
    </subject>
    <collection role="ddc" number="004">Datenverarbeitung; Informatik</collection>
    <collection role="ddc" number="330">Wirtschaft</collection>
    <collection role="open_access" number="">open_access</collection>
    <collection role="institutes" number="">Wirtschaftswissenschaftliche Fakultät</collection>
    <collection role="Transformationsvertrag" number="">DEAL Elsevier</collection>
    <thesisPublisher>Universität Passau</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-uni-passau/files/1875/goerigk_khosravi_benchmarking.pdf</file>
  </doc>
</export-example>
