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.

Heure:	10:30 - 11:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Reformulations pour l'optimisation convexe par morceaux
Description:	Renan Spencer Trindade La programmation non linéaire en nombres entiers (PNLNE) a fait l'objet d'une attention croissante de la part des chercheurs ces dernières années en raison de sa capacité à modéliser une grande variété d'applications dans le monde réel. Cependant, obtenir un optimum global d'un problème PNLNEs non convexes reste très difficile. Il est donc primordial d'exploiter, quand possible, toutes les propriétés mathématiques des PNLNE qu'on souhaite résoudre. Notre étude est motivée par la résolution de PNLNE lorsque le non-convexité se manifeste par la somme de fonctions univariées non convexes. Nous proposons une méthode basée sur des relations PNLNE convexes, obtenues en traitant séparément les intervalles où chaque fonction univariée est convexe ou concave. Dans la relaxation PNLNE convexe, chaque intervalle concave est remplacé par une linéarisation par morceaux. Pour résoudre le PNLNE résultant, nous utilisons une méthode de plans coupants qui utilise des coupes perspectives. Pour atteindre l'optimum globale, la précision de la relaxation de l'intervalle concave est incrémentée de manière itérative. Ce processus nécessite l'introduction de nouvelles variables binaires pour l'activation des intervalles dans lesquels les fonctions sont définies. Toutefois, cette étape de reformulation peut en fait être réalisée de différentes manières. Dans notre travail, nous comparons les trois différentes formulations classiques tant sur le plan théorique que sur le plan pratique. Nous prouvons que, contrairement au cas linéaire, les formulations ne sont pas équivalentes lorsque la reformulation en perspective est appliquée. Nous montrons l'impact des différentes formulations par des résultats de calcul.