Primal and dual bounds for adjustable robust optimization – DROI

Many real-life decision making problems can be modeled as mathematical optimization problems. Often, the data of these problems is not known with precision, because of measurement errors, variability or the time duration of the processes under study, or simple lack of access to reliable data. For instance, in power generation, energy demand is highly uncertain at the time when strategic planning decisions are to be made. In oil production or mining, the measurements concerning the quantity and purity of resources are not sufficiently accurate. Whereas, in a disaster management context, we may simply lack the data to characterize the adverse effects of natural disasters.

Robust optimization has evolved as a key paradigm for handling such data uncertainty within mathematical optimization problems: it
requires little historical information, can be used without characterizing probability distributions and often leads to tractable optimization problems that can be treated with existing deterministic optimization paradigms. However, the picture is more complex when some of the decisions (referred to as recourse decisions) can be adjusted after the uncertain data is known, to mitigate the effects of uncertainty, leading to adjustable robust optimization problems. Adjustable problems with discrete variables or multiple decision periods are particularly difficult to solve and, up to now, no scalable exact method has emerged. On the other hand, approximate methods, based on restricting the functional form of possible recourse actions, called "decision rules" can be developed. Some examples of decision rules proposed in the literature include affine and piecewise-affine rules in the case where recourse variables are continuous, and piecewise constant rules in the case where some recourse variables are restricted to be integers.

The goal of this project is two-fold: on the one hand, we will study novel decision rules in order to improve the quality and generality of applicability of the solutions proposed, on the other hand we will provide numerical quality measures on these solutions by developing corresponding duality tools. This will require studying the theoretical properties of the resulting optimization problems, and developing novel solution algorithms. Our methodological developments will be accompanied by numerical development and testing on applications that include the kidney exchange problem under compatibility uncertainty and the scheduling of nuclear reactors under outage duration uncertainty.