Error message

  • Deprecated function: Return type of DatabaseStatementBase::execute($args = [], $options = []) should either be compatible with PDOStatement::execute(?array $params = null): bool, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in require_once() (line 2244 of /home/lamsade/www/projets_conf/poc/includes/database/database.inc).
  • Deprecated function: Return type of DatabaseStatementEmpty::current() should either be compatible with Iterator::current(): mixed, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in require_once() (line 2346 of /home/lamsade/www/projets_conf/poc/includes/database/database.inc).
  • Deprecated function: Return type of DatabaseStatementEmpty::next() should either be compatible with Iterator::next(): void, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in require_once() (line 2346 of /home/lamsade/www/projets_conf/poc/includes/database/database.inc).
  • Deprecated function: Return type of DatabaseStatementEmpty::key() should either be compatible with Iterator::key(): mixed, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in require_once() (line 2346 of /home/lamsade/www/projets_conf/poc/includes/database/database.inc).
  • Deprecated function: Return type of DatabaseStatementEmpty::valid() should either be compatible with Iterator::valid(): bool, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in require_once() (line 2346 of /home/lamsade/www/projets_conf/poc/includes/database/database.inc).
  • Deprecated function: Return type of DatabaseStatementEmpty::rewind() should either be compatible with Iterator::rewind(): void, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in require_once() (line 2346 of /home/lamsade/www/projets_conf/poc/includes/database/database.inc).
  • Deprecated function: strlen(): Passing null to parameter #1 ($string) of type string is deprecated in drupal_random_bytes() (line 2268 of /home/lamsade/www/projets_conf/poc/includes/bootstrap.inc).
  • Deprecated function: Return type of DateObject::__wakeup() should either be compatible with DateTime::__wakeup(): void, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in include_once() (line 158 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Return type of DateObject::format($format, $force = false) should either be compatible with DateTime::format(string $format): string, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in include_once() (line 158 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Return type of DateObject::setTimezone($tz, $force = false) should either be compatible with DateTime::setTimezone(DateTimeZone $timezone): DateTime, or the #[\ReturnTypeWillChange] attribute should be used to temporarily suppress the notice in include_once() (line 158 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property SelectQuery::$alterTags is deprecated in SelectQuery->addTag() (line 978 of /home/lamsade/www/projets_conf/poc/includes/database/select.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: rtrim(): Passing null to parameter #1 ($string) of type string is deprecated in url() (line 2349 of /home/lamsade/www/projets_conf/poc/includes/common.inc).
  • Deprecated function: strlen(): Passing null to parameter #1 ($string) of type string is deprecated in _filter_url_trim() (line 1664 of /home/lamsade/www/projets_conf/poc/modules/filter/filter.module).
  • Deprecated function: Creation of dynamic property DateObject::$timeOnly is deprecated in DateObject->__construct() (line 221 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$dateOnly is deprecated in DateObject->__construct() (line 222 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$originalTime is deprecated in DateObject->__construct() (line 225 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$timeOnly is deprecated in DateObject->__construct() (line 221 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$dateOnly is deprecated in DateObject->__construct() (line 222 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$originalTime is deprecated in DateObject->__construct() (line 225 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$timeOnly is deprecated in DateObject->__construct() (line 221 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$dateOnly is deprecated in DateObject->__construct() (line 222 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$originalTime is deprecated in DateObject->__construct() (line 225 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$timeOnly is deprecated in DateObject->__construct() (line 221 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$dateOnly is deprecated in DateObject->__construct() (line 222 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$originalTime is deprecated in DateObject->__construct() (line 225 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$timeOnly is deprecated in DateObject->__construct() (line 221 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$dateOnly is deprecated in DateObject->__construct() (line 222 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property DateObject::$originalTime is deprecated in DateObject->__construct() (line 225 of /home/lamsade/www/projets_conf/poc/sites/all/modules/date/date_api/date_api.module).
  • Deprecated function: Creation of dynamic property SelectQuery::$alterTags is deprecated in SelectQuery->addTag() (line 978 of /home/lamsade/www/projets_conf/poc/includes/database/select.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property RegistrationType::$id is deprecated in EntityAPIController->load() (line 256 of /home/lamsade/www/projets_conf/poc/sites/all/modules/entity/includes/entity.controller.inc).
  • Deprecated function: Creation of dynamic property RegistrationType::$weight is deprecated in EntityAPIController->load() (line 256 of /home/lamsade/www/projets_conf/poc/sites/all/modules/entity/includes/entity.controller.inc).
  • Deprecated function: Creation of dynamic property RegistrationType::$status is deprecated in EntityAPIController->load() (line 256 of /home/lamsade/www/projets_conf/poc/sites/all/modules/entity/includes/entity.controller.inc).
  • Deprecated function: Creation of dynamic property RegistrationType::$module is deprecated in EntityAPIController->load() (line 256 of /home/lamsade/www/projets_conf/poc/sites/all/modules/entity/includes/entity.controller.inc).
  • Deprecated function: Creation of dynamic property RegistrationType::$held_expire is deprecated in EntityAPIController->load() (line 272 of /home/lamsade/www/projets_conf/poc/sites/all/modules/entity/includes/entity.controller.inc).
  • Deprecated function: Creation of dynamic property RegistrationType::$held_expire_state is deprecated in EntityAPIController->load() (line 272 of /home/lamsade/www/projets_conf/poc/sites/all/modules/entity/includes/entity.controller.inc).
  • Deprecated function: Creation of dynamic property RegistrationType::$rdf_mapping is deprecated in rdf_entity_load() (line 412 of /home/lamsade/www/projets_conf/poc/modules/rdf/rdf.module).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property Registration::$is_new is deprecated in Entity->__construct() (line 210 of /home/lamsade/www/projets_conf/poc/sites/all/modules/entity/includes/entity.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property SelectQuery::$alterTags is deprecated in SelectQuery->addTag() (line 978 of /home/lamsade/www/projets_conf/poc/includes/database/select.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: strlen(): Passing null to parameter #1 ($string) of type string is deprecated in _filter_url_trim() (line 1664 of /home/lamsade/www/projets_conf/poc/modules/filter/filter.module).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property Registration::$is_new is deprecated in Entity->__construct() (line 210 of /home/lamsade/www/projets_conf/poc/sites/all/modules/entity/includes/entity.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: strpos(): Passing null to parameter #1 ($haystack) of type string is deprecated in url_is_external() (line 2393 of /home/lamsade/www/projets_conf/poc/includes/common.inc).
  • Deprecated function: str_replace(): Passing null to parameter #3 ($subject) of type array|string is deprecated in url_is_external() (line 2395 of /home/lamsade/www/projets_conf/poc/includes/common.inc).
  • Deprecated function: ltrim(): Passing null to parameter #1 ($string) of type string is deprecated in url() (line 2311 of /home/lamsade/www/projets_conf/poc/includes/common.inc).
  • Deprecated function: Creation of dynamic property SelectQuery::$alterTags is deprecated in SelectQuery->addTag() (line 978 of /home/lamsade/www/projets_conf/poc/includes/database/select.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property SelectQuery::$alterTags is deprecated in SelectQuery->addTag() (line 978 of /home/lamsade/www/projets_conf/poc/includes/database/select.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).
  • Deprecated function: Creation of dynamic property DatabaseCondition::$stringVersion is deprecated in DatabaseCondition->compile() (line 1865 of /home/lamsade/www/projets_conf/poc/includes/database/query.inc).

SPOC 21 "Polyèdres et Combinatoire"

Date: 
Friday, 13 December, 2019

21ème séminaire du groupe POC

Le VENDREDI 13 DECEMBRE 2019

Au laboratoire LIP6 (Sorbonne Université)
4 place Jussieu 75005 Paris

Dans le campus Pierre et Marie Curie de Jussieu
Rotonde 26 - 1er étage - Couloir 25-26 - Salle 105

Sur le thème

Polyèdres et Combinatoire

 

Le séminaire est annulé compte tenu des difficultés de déplacements suite aux mouvements de grèves.

 

Entrée gratuite
Merci de vous inscrire à cette journée pour faciliter l'organisation

Pour voir la liste des inscrits

Programme de la journée:


9h30-10h30  Accueil "café - viennoiserie"


 

10h00-11h00

András SEBÖ
CNRS, Univ. Grenoble-Alpes, Laboratoire G-SCOP

Uniform Covers, Cones and Integrality Gap :  Connections and Challenges

A uniform cover is packing of combinatorial objects in graphs so that every edge is contained in the same number of objects. We show some relevant occurrences of uniform covers in combinatorial problems, their relation to polyhedra, to the integrality gap and to approximation ratios, and report about some recent results. Several related open problems will be stated.

 


 

11h00-12h00

Roland GRAPPE
LIPN, Université Paris 13

Characterizations of box-totally dual integral polyhedra

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.

This is a joint work with Patrick Chervet and Louis-Hadrien Robert.

 


 

12h00-14h00     Repas


 

14h00 - 15h00

Michele CONFORTI
Università degli Studi di Padova

The cut dominant and forbidden minors

The cut dominant of a graph is the unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts. Minimizing a nonnegative linear function over the cut dominant is equivalent to finding a minimum weight cut in the graph. We give a forbidden-minor characterization of the graphs whose cut dominant can be defined by inequalities with integer coefficients and right-hand side at most 2. Our result is related to the forbidden-minor characterization of TSP-perfect graphs by Fonlupt and Naddef. We prove that our result implies theirs, with a shorter proof. Furthermore, we establish general properties of forbidden minors for right-hand sides larger than 2.

This is joint work with Sam Fiorini and Kanstantsin Pashkovic
 


 

15h00 - 15h30     Pause


 

15h30 - 16h30

Hande YAMAN
Faculty of Economics and Business, KU Leuven, Belgique

Convex Hull Results for Generalizations of the Constant Capacity Single Node Flow Set

For single node flow sets with fixed costs and constant capacities on the inflow and outflow arcs, a family of constant capacity flow covers are known to provide the convex hull in different special  cases and are conjectured to provide it in the general case. Here we study more general mixed integer sets for which such single node flow cover inequalities suffice to give the convex hull. In particular we consider the case of  a path in which each node has one (or several) incoming and outgoing arcs with constant capacities and fixed costs. This can be seen as a lot-sizing set with production and sales decisions driven by costs and prices and  by the lower and upper bounds on stocks instead of being driven by demands as in the standard lot-sizing model. To describe the convex hulls, we characterize the extreme points, derive tight extended formulations and project out the additional variables using Fourier-Motzkin elimination. The validity of the conjecture for the single node flow set follows from our results.

This is joint work with Laurence A. Wolsey.
 


 

16h30 - 17h30

Mourad BAIOU
CNRS, Laboratoire LIMOS, Université Clermont-Auvergne

On some network security games

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.