|
|
 |
|
Mercredi 22 Mars
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Two non-linear stochastic problems with catastrophic consequences |
| Description: |
Alberto Santini We study two stochastic problems in which some events occur with low probability but can have catastrophic consequences. The first is the 0-1 Time-bomb Knapsack Problem, an extension of the classical Knapsack Problem in which each item has an associated probability of exploding and destroying the entire content of the knapsack. The objective is to maximise the expected profit of the selected items. The second is the Hazardous Orienteering Problem (HOP), which extends the classical Orienteering Problem. In the HOP, the vehicle picks up parcels at the customers it visits. Some of these parcels have a probability of exploding and destroying the entire content of the vehicle. This probability depends on the amount of time the parcel spends on board the vehicle, following an exponential distribution. The objective is again to maximise the expected collected profit.
We propose mathematical formulations and valid inequalities, exact algorithms based on branch-and-bound and dynamic programming, and primal and dual bounding techniques for both problems. |
|
|
