Exact and Approximate Schemes for Robust Optimization Problems with Decision Dependent Information Discovery

Rosario Paradiso (r.paradisovu.nl)
Angelos Georghiou (georghiou.angelosucy.ac.cy)
Said Dabia (s.dabiavu.nl)
Denise Tönissen (d.d.tonissenvu.nl)

Abstract: Uncertain optimization problems with decision dependent information discovery allow the decision maker to control the timing of information discovery, in contrast to the classic multistage setting where uncertain parameters are revealed sequentially based on a prescribed filtration. This problem class is useful in a wide range of applications, however, its assimilation is partly limited by the lack of efficient solution schemes. In this paper we study two-stage robust optimization problems with decision dependent information discovery where uncertainty appears in the objective function. The contributions of the paper are twofold: (i) we develop an exact solution scheme based on a nested decomposition algorithm, and (ii) we improve upon the existing K-adaptability approximate by strengthening its formulation using techniques from the integer programming literature. Throughout the paper we use the orienteering problem as our working example, a challenging problem from the logistics literature which naturally fits within this framework. The complex structure of the routing recourse problem forms a challenging test bed for the proposed solution schemes, in which we show that exact solution method outperforms at times the K-adaptability approximation, however, the strengthened K-adaptability formulation can provide good quality solutions in larger instances while significantly outperforming existing approximation schemes even in the decision independent information discovery setting. We leverage the effectiveness of the proposed solution schemes and the orienteering problem in a case study from Alrijne hospital in the Netherlands, where we try to improve the collection process of empty medicine delivery crates by co-optimizing sensor placement and routing decisions.

Keywords: robust optimization, decision dependent information discovery, exact method, $K$-adaptability, orienteering problem, sensor placement, Alrijne hospital

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences

Citation:

Download: [PDF]

Entry Submitted: 07/23/2021
Entry Accepted: 07/23/2021
Entry Last Modified: 07/23/2021

Modify/Update this entry