Mars 2023

Heure:	10:30 - 11:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Catégories de sommets pour le problème de domination
Description:	Vincent Bouquet Cette présentation porte sur les sommets qui appartiennent à tous les ensembles dominants minimums d'un graphe. Nous caractérisons ces sommets en fonction de leur criticité relativement au nombre de domination. Cette criticité mesure comment le retrait d'un sommet du graphe affecte le nombre de domination. Nous nous intéressons ensuite à cette caractérisation dans quelques classes de graphes: les graphes triangulés, les cographes, ainsi que des sous-classes des graphes sans griffe. Pour ces graphes, nous montrons que les sommets persistants sont toujours critiques: c'est-à-dire que le retrait d'un sommet persistant fait augmenter le nombre de domination.

Heure:	12:00 - 13:00
Lieu:	Visio - https://bbb.lipn.univ-paris13.fr/b/wol-ma9-vjn - 514019
Résumé:	Partial Optimality in Cubic Correlation Clustering
Description:	Silvia Di Gregorio The higher-order correlation clustering problem is an expressive model, and recently, local search heuristics have been proposed for several applications. Certifying optimality, however, is NP-hard and practically hampered already by the complexity of the problem statement. Here, we focus on establishing partial optimality conditions for the special case of complete graphs and cubic objective functions. In addition, we define and implement algorithms for testing these conditions and examine their effect numerically, on two datasets.

Heure:	10:30 - 11:00
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Robust min-max regret covering problems
Description:	Amadeu Almeida Coco This presentation discusses two min-max regret covering problems: the min-max regret Weighted Set Covering Problem (min-max regret WSCP) and the min-max regret Maximum Benefit Set Covering Problem (min-max regret MSCP). These problems are the robust optimization counterparts, respectively, of the Weighted Set Covering Problem and of the Maximum Benefit Set Covering Problem. In both problems, uncertainty in data is modeled by using an interval of continuous values, representing all the infinite values every uncertain parameter can assume. This study has the following major contributions: (i) a proof that MSCP is ?p2-Hard, (ii) a mathematical formulation for the min-max regret WSCP, (iii) exact and (iv) heuristic algorithms for the min-max regret WSCP and the min-max regret MSCP. We reproduce the main exact algorithms for the min-max regret WSCP found in the literature: a Logic-based Benders decomposition, an extended Benders decomposition, and a branch-and-cut. In addition, such algorithms have been adapted for the min-max regret MSCP. Moreover, five heuristics are applied for both problems: two scenario-based heuristics, a path relinking, a pilot method, and a linear programming-based heuristic. The goal is to analyze the impact of such methods on handling robust covering problems in terms of solution quality and performance.

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.

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.