18 Mars - 24 Mars


Retour à la vue des calendrier
Mardi 19 Mars
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Accelerated Column Generation for Cutting Stock and Bin Packing
Description: Accelerated Column Generation for Cutting Stock and Bin Packing One successful method for solving the cutting stock (CS) and bin packing
problem (BP) is branch-and-price.  The column generation master program
is a set covering problem where columns correspond to feasibly filled
bins that cover a subset of the items.  It is known that standard column
generation suffers from slow convergence (tailing off).  For CS, valid
inequalities on the dual prices of the covering constraints, so-called
dual optimal inequalities, were identified to be helpful to mitigate the
tailing off effect.  The presentation addresses three issues:  First,
the standard approach is the a priori construction of dual optimal
inequalities before solving the master program.  We show that the most
violated inequalities can be easily identified in the column generation
process and so be added dynamically.  For standard benchmark problems,
computation times were approximately halved.  Second, for BP not all CS
inequalities are dual optimal, i.e., fulfilled by at least one optimal
solution of the LP-relaxation of the master program.  We present a way
to handle these cases and to reconstruct primal feasible solutions
needed in the branch-and-bound process.  Third, we generalize our
results to the BP with conflicts. 
Jeudi 21 Mars
Heure: 12:30 - 14:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Fouille de sous-graphes fréquents à base d'arc consistance
Description: Brahim Douar Avec la croissance importante du besoin d'analyser une grande masse de données structurées tels que les composés chimiques, les structures de protéines ou même les réseaux sociaux, la fouille de sous-graphes fréquents est devenue un défi réel en matière de fouille de données. Ceci est étroitement lié à leur nombre exponentiel ainsi qu'à la NP-complétude du problème d'isomorphisme d'un sous-graphe général. Face à cette complexité, et pour gérer cette taille importante de l'espace de recherche, les méthodes classiques de fouille de graphes ont exploré des heuristiques de recherche basées sur le support, le langage de description des exemples (limitation aux chemins,  aux arbres, etc.) ou des hypothèses (recherche de sous-arborescence communes, de chemins communs, etc.). Dans le cadre de notre travail de recherche, nous nous basons sur une méthode d'appariement de graphes issue du domaine de la programmation par contraintes, nommée AC-projection, qui a le mérite d'avoir une complexité polynomiale. Nous introduisons des approches de fouille de graphes permettant d'améliorer les approches existantes pour ce problème. En particulier, nous proposons deux algorithmes, FGMAC et AC-miner, permettant de rechercher les sous-graphes fréquents à partir d'une base de graphes. Ces deux algorithmes profitent, différemment, des propriétés fortes intéressantes de l'AC-projection. En effet, l'algorithme FGMAC adopte un parcours en largeur de l'espace de recherche et exploite l'approche par niveau introduite dans Apriori, tandis que l'algorithme AC-miner parcourt l'espace en profondeur par augmentation de motifs, assurant ainsi une meilleure mise à l'échelle pour les grands graphes.  Ces deux approches permettent l'extraction d'un type particulier de graphes, il s'agit de celui des sous-graphes AC-réduits fréquents. Dans un premier temps, nous prouvons, théoriquement, que l'espace de recherche de ces sous-graphes est moins important que celui des sous-graphes fréquents à un isomorphisme près. Ensuite, nous menons une série d'expérimentations permettant de prouver que les algorithmes FGMAC et AC-miner sont plus efficients que ceux de l'état de l'art. Au même temps, nous prouvons que les sous-graphes AC-réduits fréquents, en dépit de leur nombre sensiblement réduit, ont le même pouvoir discriminant que les sous-graphes fréquents à un isomorphisme près. Cette étude est menée en se basant sur une évaluation expérimentale de la qualité des sous-graphes AC-réduits fréquents dans un processus de classification supervisée de graphes.