|
|
 |
|
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. |
Jeudi 23 Mars
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Exact algorithms for linear matrix inequalities and application to the moment problem |
| Description: |
Simone Naldi In this talk I will discuss computer algebra algorithms for solving exactly linear matrix inequalities, that is, the feasibility of a semidefinite program. These algorithms rely on the determinantal structure behind SDP. The main motivation is for certifying lower bounds in polynomial optimization, for instance, for computing the sum of squares certificates of multivariate polynomials. Recently a new application to the so-called truncated moment problem gives new perspectives that will be discussed in the second part of the talk. This consists of the decision problem whether a sequence of real numbers, indexed by monomials of degree d in n variables, is the moment sequence of a nonnegative Borel measure with support in some basic semialgebraic set. This is based on joint work with D. Henrion and M. Safey El Din. |
|
|
