Refine
Document Type
- In Proceedings (3)
- ZIB-Report (3)
Language
- English (6)
Is part of the Bibliography
- no (6)
Keywords
Institute
- Mathematics of Telecommunication (6) (remove)
A central assumption in classical optimization is that all the input data of a
problem are exact. However, in many real-world problems, the input data are subject
to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal
solutions that are actually suboptimal or even infeasible. Robust optimization
offers a remedy for optimization under uncertainty by considering only the subset of
solutions protected against the data deviations. In this paper, we provide an overview
of the main theoretical results of multiband robustness, a new robust optimization
model that extends and refines the classical theory introduced by Bertsimas and Sim.
After introducing some new results for the special case of pure binary programs, we
focus on the harvest scheduling problem and show how multiband robustness can
be adopted to tackle the uncertainty affecting the volume of produced timber and
grant a reduction in the price of robustness.
The Frankl conjecture, also known as the union-closed sets conjecture, states that there exists an element in at least half of the sets of any (non-empty) union-closed family. From an optimization point of view, one could instead prove that 2a is an upper bound to the number of sets in a union-closed family with n elements where each element is in at most a sets, where a and n are non-negative integers. Formulating these problems as integer programs we observe that computed optimal values do not vary with n. We formalize these observations as conjectures, and show that they are not equivalent to the Frankl conjecture while still having
wide-reaching implications if proven true. Finally, we partially prove the new conjectures and discuss possible approaches to solve them completely.
We provide an overview of new theoretical results that we obtained while further investigating multiband robust optimization, a new model for robust optimization that we recently proposed to tackle uncertainty in mixed-integer linear programming. This new model extends and refines the classical Gamma-robustness model of Bertsimas and Sim and is particularly useful in the common case of arbitrary asymmetric distributions of the uncertainty. Here, we focus on uncertain 0-1 programs and we analyze their robust counterparts when the uncertainty is represented through a multiband set. Our investigations were inspired by the needs of our industrial partners in the research project ROBUKOM.