Date:

Friday, 30 October, 2020

**Le VENDREDI 30 OCTOBRE 2020**

**En distanciel**

**"Entrée" gratuite**

**Afin de signaler votre présence, ****merci de vous inscrire à cette journée.**

**Pour voir la liste des inscrits**

**Informations de connexion: **

- Pour les exposés scientifiques ainsi que les questions scientifiques (Plateforme zoom)
- Pour les "Pauses-café sans café"

Programme de la journée:

Entre les exposés scientifiques, les discussions scientiifiques ou tout simplement amicales sont les bienvenues.

Les exposés ci-dessous tenteront de débuter à l'heure fixée sous zoom.

Entre les exposés, rejoingnez le serveur Discord POC pour des discussions plus informelles par petits groupes lors des "Pause-café sans café" (où il n'est pas interdit de boire du café).

**9h45-10h00 Test de connexion et accueil**

**10h00-11h00 **

**Ivana LJUBIC**

ESSEC business school

PDF: SPOC22_Ljubic.pdf

VIDEO: chaîne youtube POC

The family of Critical Node Detection Problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the $k$-vertex cut problem. The problems asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least $k$ components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the $k$ mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature.

Joint work with **F. Furini**, **E. Malaguti** and **P. Paronuzzi**

**Pause-café sans café **

Retrouvons-nous sous le salon "Discord" (voir en début de page)

**11h00-12h00**

**Roland GRAPPE **

LIPN, Université Paris 13

PDF: SPOC22_Grappe.pdf

VIDEO: chaîne youtube POC

A polyhedron is box-integer if its intersection with any integer box is an integer polyhedron. We introduce principally box-integer polyhedra : they are the polyhedra whose dilatations are box-integer as soon as they are integer. We will present several characterizations of principally box-integer polyhedra, which involve matrices and strong integrality properties of linear sytems. In particular, this will provide new characterizations of box-totally dual integral polyhedra, which are polyhedra defined by linear systems having strong integrality properties.

**Pause-café sans café **

Retrouvons-nous sous le salon "Discord" (voir en début de page)

**12h00-14h00 Pause**

**14h00 - 15h00**

**Mourad BAIOU**

CNRS, Laboratoire LIMOS, Université Clermont-Auvergne

PDF: SPOC22_Baiou.pdf

We study two-players games on graphs, where one player (the defender) chooses a tree, and (simultaneously) the other player (the attacker) chooses an edge hoping to detect the defender. For each edge *e* there is a probability *p(e)* that the attacker will detect the defender if both players have chosen

the edge *e*. Also the attacker incurs on a cost* c(e)* if he chooses the edge *e*. The defender has to find a tree-selection strategy that minimizes the average probability of being detected. The attacker has to find a probabilistic selection strategy that maximizes the average detection probability minus its average cost. We give polynomial algorithms to find both strategies. We also extend this to security games on matroids.

**Pause-café sans café **

Retrouvons-nous sous le salon "Discord" (voir en début de page)

**15h00 - 16h00**

**Hassan AISSI**

LAMSADE, Université Paris Dauphine

PDF:

VIDEO: chaîne youtube POC

We consider in this paper a generalization of the minimum $s-t$ cut problem. Suppose we are given a directed graph $G=(V,A)$ with two distinguished nodes $s$ and $t$, $k$ non-negative cost functions $c^1,\ldots,c^k:A \leftarrow \mathbb{Z}_+$, and $k-1$ budget bounds $b_1, \ldots,b_{k-1}$ where $k$ is a constant. The goal is to find a $s-t$ cut $C$ satisfying budget constraints $c^h(C) \leqslant b_h$, for $h = 1,\ldots,k-1$, and whose cost $c^k(C)$ is minimum. We study the linear relaxation of the problem and give necessary and sufficient conditions for which it has an integral optimal basic solution. We also give a strongly polynomial time combinatorial algorithm for solving it. As a corollary, we obtain a $(1,k)$-pseudo-approximation algorithm for the problem.

Joint work with **A. Ridha Mahjoub**

**Pause-café sans café **

Retrouvons-nous sous le salon "Discord" (voir en début de page)

**16h00 - 17h00 **

**Diego DELLE DONNE**

Laboratoire d'Informatique de l'École Polytechnique (LIX)

PDF: SPOC22_DelleDonne.pdf

VIDEO: chaine youtube POC

Given a vector y \in R^n$ and a matrix H \in R^{n×m}, the sparse approximation problem P_0/p asks for a solution x such that ||y−Hx||_p ≤ \alpha, for a given scalar \alpha, minimizing the size of the support ||x||_0 := |{j | x_j != 0}|. Existing convex mixed-integer programming formulations for P_0/p are of a kind referred to as "big M", meaning that they involve the use of a bound M on the values of x. When a proper value for M is not known beforehand, these formulations are not exact. In this work we study the polytopes arising from these formulations and derive valid inequalities for them. We first use these inequalities to design a branch-and-cut algorithm for these models. Additionally, we prove that these inequalities are sufficient to describe the polytope of "feasible supports" for P_0/p. Based on this result, we introduce a new (and the first to our knowledge) M-independent integer linear programming formulation for P_0/p. We propose a practical approach to tackle this formulation, which has exponentially many constraints. The proposed methods are then compared in a computational experimentation with the goal of testing their practical potential contribution.

Joint work with** Matthieu Kowalski **and **Leo Liberti**.

**Pause-café sans café **

Retrouvons-nous sous le salon "Discord" (voir en début de page)

Lien sur fichier: