SPOC 22 "Séminaire POC octobre 2020"
Date:
Friday, 30 October, 2020
22ème séminaire du groupe POC
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é" ( Serveur Discord POC https://discord.gg/XQkFDTF )
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
New integer and Bilevel Formulations for the k-Vertex Cut Problem
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
Characterizations of box-totally dual integral polyhedra
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
On some network security games
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
On the minimum s-t cut problem with budget constraints
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)
A novel integer linear programming approach for global L_0 minimization
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:
