2023

Heure:	16:00 - 17:00
Lieu:	https://bbb.lipn.univ-paris13.fr/b/wol-ma9-vjn - code: 514019
Résumé:	Hamiltonian degree condition for tough graphs
Description:	Cleophee Robin A graph G is hamiltonian if there exists a G cycle containing all G vertices exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G-S is at most |S|/t. We extended the Theorem of Hoàng by proving the following: Let G be a graph with degree sequence d_1,d_2, ..., d_n, and let t be a positive integer at most 4. If G is a t-tough and if for each i, t

Heure:	10:30 - 11:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	QP/NLP-based Branch-and-Bound algorithm for MINLP: It could work!
Description:	Luca Mencarelli We describe a novel QP/NLP-based Branch-and-Bound algorithm for convex MINLP. Then, we introduce a tailored version of the previous algorithm for (non-convex) Binary Nonlinear Optimization Problems (BNPs), relying on a simple convexification procedure and a tailor convex quadratic under-approximation. We survey computational experiences on convex instances of MINLPLib and on several literature and random generated instances for BNPs.

Heure:	10:30 - 11:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Multiplicité dans le partitionnement de graphes signés
Description:	Nejat Arinik Selon la théorie de l'équilibre structural, un graphe signé est structurellement équilibré s'il peut être partitionné en sous-groupes mutuellement hostiles (i.e. reliés seulement par des liens négatifs) tout en exhibant une solidarité interne (i.e. contenant uniquement des liens positifs). Mais un réseau réel (i.e. un graphe représentant un système du monde réel) est rarement parfaitement équilibré : on trouvera quelques liens positifs entre les groupes et/ou quelques liens négatifs à l'intérieur de certains groupes. L'un des défis du domaine est de quantifier le niveau de déséquilibre d'un tel réseau et d'identifier les liens qui causent ce déséquilibre. Le problème Correlation Clustering (CC) se définit précisément par l'obtention d'une partition possédant un déséquilibre minimal. Le partitionnement de graphes signés constitue une tâche importante du point de vue applicatif, étant donné que trouver une partition équilibrée aide à comprendre le système modélisé par le graphe signé. Cependant, l'approche standard dans la littérature se contente de chercher une seule partition, comme si elle caractérisait suffisamment le système étudié. Or, on peut avoir besoin de plusieurs partitions pour construire une image plus juste du système étudié. Même si cette notion de la multiplicité est extrêmement important du point de vue des utilisateurs finaux, elle a été très peu abordée dans la littérature. Une particulière situation dans laquelle on veut relaxer l'hypothèse de partition unique et en chercher plusieurs est lié au problème CC. Quand on résout une instance de ce problème, plusieurs partitions optimales peuvent coexister. La question qui se pose est de savoir ce qu'on perd, si on considère une seule partition optimale, alors qu'il en existe plusieurs. Idéalement, il faut les énumérer toutes avant de faire une analyse concluante. Pour ce faire, on propose une nouvelle méthode d'énumération et un framework basé sur l'analyse de clustering afin de d'abord complètement énumérer l'espace des partitions optimales, puis étudier empiriquement un tel espace. Nos résultats ont révélé une typologie de l'espace de partitions optimales : 1) une seule partition optimale ; 2) quelques partitions constituant une seule classe ; 3) beaucoup de partitions optimales constituant une seule classe de forme allongée ; 4) plusieurs partitions optimales constituant plusieurs classes de partitions.

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.