Σp2-completeness of a robust binary linear program with binary uncertainty set">A note on Σp2-completeness of a robust binary linear program with binary uncertainty set

作者：Matthias Claus; Maximilian Simmoteit

来源：Operations Research Letters, 2020.

DOI：10.1016/j.orl.2020.07.006

• Robust binary linear programming
• ,Σ2p,-completeness
• ,K,-adaptability

We show that the robust binary linear program with uncertain objective function and binary uncertainty set defined by linear constraints is Σ2p-complete. This result is then extended to the K-adaptability version of the problem, where one of K pre-calculated solutions can be chosen after the uncertain parameter is revealed.

• 单位
  1