Simon de Givry Permanent researcher (CR1, HdR) at INRA Biometrics and Artificial Intelligence INRA Centre de recherches de Toulouse Station de biométrie et d'intelligence artificielle Chemin de borde rouge B.P. 52627 - 31326 CASTANET-TOLOSAN CEDEX FRANCE Phone: (+33) (0)5 61 28 50 74 Secr.: (+33) (0)5 61 28 52 75 Fax: (+33) (0)5 61 28 53 35 Email: degivry_AT_toulouse-inra-fr Access from Toulouse: Metro line B (Ramonville exit) then Bus 62 (INRA exit in Castanet-Tolosan)

Events

• JFPC'12, program chair of the French conference on Constraint Programming, Toulouse, May 22-24th, 2012.
• HDR(slides), Habilitation à dirigé des recherches (in French), UPS, Toulouse, March 29th, 2011.
• KIEV10, tutorial on Search Methods Exploiting the Problem Structure at Theoretical and Applied Problems of Structural Pattern Recognition Workshop, Kiev, Ukraine, September 26th, 2010.
• CP10VCSP, tutorial on Valued Constraint Satisfaction Problems by Martin Cooper & Peter Jeavons & Simon de Givry at CP'10, St Andrews, Scotland, September 7th, 2010.
• IJCAI09OPTIM, tutorial on Combinatorial Optimization for Graphical Models by Rina Dechter & Radu Marinescu & Simon de Givry & Thomas Schiex at IJCAI'09, Pasadena, USA, July 12th, 2009.

• WCB11, workshop on Constraint Based Methods for Bioinformatics held in conjunction with CP 2011, Perugia, Italy, September 12th, 2011.
• WCB10, workshop on Constraint Based Methods for Bioinformatics held in conjunction with ICLP 2010, Edinburgh, Scotland, July 21th, 2010.
• WCB09, workshop on Constraint Based Methods for Bioinformatics held in conjunction with CP 2009, Lisbon, Portugal, September 20th, 2009.
• WCB08, workshop on Constraint Based Methods for Bioinformatics held in conjunction with CPAIOR 2008, Paris, France, May 22th, 2008.
• WCB07, workshop on Constraint Based Methods for Bioinformatics held in conjunction with ICLP 2007, Porto, Portugal, September 13, 2007.
• WCB06, workshop on Constraint Based Methods for Bioinformatics held in conjunction with CP 2006, Nantes, France, September 25th, 2006.

• Soft 2011, CP-2011 workshop on Preferences and Soft Constraints, Perugia, Italy, September 12th, 2011.
• Soft 2010, CP-2010 workshop on Preferences and Soft Constraints, St Andrews, Scotland, September 6th, 2010.
• Soft 2008, CP-2008 workshop on Preferences and Soft Constraints, Sydney, Australia, September 15th, 2008. Special year on Cost Function Processing.
• Alenya 2008, The Unique Informal Workshop on Cost Function processing, Alenya, France, February 14-15th, 2008.
• Soft 2006, CP-2006 workshop on Preferences and Soft Constraints, Nantes, France, September 25th, 2006. Special year on Structural decomposition and Tractability.
• Soft 2005, CP-2005 workshop on Preferences and Soft Constraints, Sitges, Spain, October 1st, 2005.

Publications

• Selected list of publications
• Complete list of publications (bibtex file)

Teaching

• Théorie des graphes (in French), module Systèmes informatique et décision, ENSAE, Toulouse.
• Méthodes de preuves, Optimisation et Satisfaction de contraintes (in French), M2R IA, Université Paul Sabatier, Toulouse. Also includes several tutorials from the constraint programming community.
• Modèles probabilistes et Algorithmes pour la Biologie (in French), M2R IA, Université Paul Sabatier, Toulouse.
• Cartographie génétique (in French), M1 Bioinformatique et biologie des Systèmes, module Génomique et génétique statistique, Université Paul Sabatier, Toulouse.

Softwares

• GeneBayesNet: demonstrates the reconstruction of gene regulatory networks from genetical genomics data using Bayesian network structure learning techniques. It aims at recovering the underlying gene regulation network given measures of expression data and SNP occurrences for a set of related individuals.
• ToolBar/toulbar2: solves cost function networks. The new C++ version toulbar2 (ToolBar is no more developed) incorporates very recent algorithmic results. It is able to deal with weighted CSP, weighted Max-Sat, Bayesian Networks (MPE task), and quadratic pseudo-Boolean optimization. This is a collaborative work open to additional developpers. An on-line version (web service), restricted to small problems, is available here toulbar2 solver demo. See also CostFunction, WCSP and SoftCSP.
• CARThAGENE: solves marker ordering problems and can also join maps (genetic or radiated hybrid) on simple pedigrees: backcross, RI (ri self, ri sib), F2 intercross, phase known outbreds and radiated hybrids.
• MendelSoft: detects Mendelian errors in complex pedigree using weighted constraint satisfaction techniques.
• MilPat: searches RNA motifs and their intermolecular contacts with constraint networks. See also Darn!, from Matthias Zytnicki, dealing with preferences for sorting RNA motif solutions in the weighted CSP framework.
• Eclair©/ToOLS©: solves combinatorial optimization problems in a constraint programming framework. Eclair is a finite domain constraint solver with real-time features and is written in the Claire programming language. ToOLS is part of Eclair and is dedicated to the design of partial and hybrid search algorithms. Eclair and ToOLS are copyright THALES Research & Technology.
• VCSP (only SUN Solaris binaries): solves valued constraint satisfaction problems with partial forward checking, russian doll search and simulated annealing methods. Provides several simplification techniques to bound the optimum (see [Givry98a,Cabon98,Givry97b,Verfaillie97a]). Uses the same input file format (`.ds') as in LVCSP.

Benchmarks

• CostFunction: a new collection of benchmarks from various domains: WCSP, Bayesian Networks, Markov Random Fields, Max-SAT,...
• WCSP: a collection of benchmarks, problem generators and input langages/translators for ToolBar and other soft constraint solvers (lvcsp, vcsp, and incop).
• bep: a choco benchmark (b_photo.cl), also used to validate ToOLS©. This is a satellite mission management problem that is a mix between a Traveling Salesman Problem with Time Windows and a Knapsack problem. The directory contains randomly-generated instances with 50, 100, and 200 candidate photographs.

Projects, Collaborations and Students

• CostFunction, a constraint programming extension to combinatorial optimization.
• SoftCSP, a (wiki) collaborative web site dedicated to Soft Constraint Satisfaction Problems.

• Structure learning of gene networks (in French, 2009-), a research working group supported by INRA MIA.
• French ANR project (janv 2011-juillet 2014) on introducing stronger local consistency filtering algorithms for solving constraint optimization problems with global cost functions and for bounding the normalization constant in probabilistic graphical models.
• French ANR project (dec 2005-dec 2008) on strategies and algorithms for decomposing and solving constraint optimization problems.
• French ARC project (2005-2007) on integrated biological networks.
• French-Ireland Ulysse project (2006, 2008) on conditional preferences and soft constraints. Also explore new valuation structures.

• Martin Cooper, IRIT, Toulouse, France. Weighted CSP.
• Thomas Faraut, INRA LGC, Toulouse, France. Comparative RH mapping.
• Hélène Fargier, IRIT, Toulouse, France. Valued CSP and compilation.
• Christine Gaspin, INRA MIA, Toulouse, France. RNA Structured Motifs Search.
• Christophe Hitte, CNRS / UMR 6061, Rennes, France. Comparative RH mapping applied to the Dog genome.
• Laurent Jeannin, THALES Research & Technology FRANCE, Orsay. Partial and hybrid search algorithms in constraint programming.
• Philippe Jégou, LSIS - Université Paul Cézanne, Marseille, France. Tree decomposition and counting.
• Javier Larrosa, UPC, Barcelona, Spain. Weighted CSP.
• Brigitte Mangin, INRA MIA, Toulouse, France. Genetics.
• Pedro Meseguer, IIIA-CSIC, Bellaterra, Spain. Weighted CSP.
• Thomas Schiex, INRA MIA, head of the bioinformatics team at Toulouse, France.
• Gérard Verfaillie, ONERA CERT, Toulouse, France. Weighted CSP.

Post Doctoral Students

• Marti Sanchez, Weighted CSP processing, July 2006-May 2008.

Ph.D. Students

• Jimmy Vandel, école doctorale MITT, Université Paul Sabatier, Toulouse, Learning gene regulatory networks in genetical genomics experiments, October 2009-October 2012 (co-supervised with Brigitte Mangin, INRA MIA).
• Aurélie Favier, école doctorale MITT, Université Paul Sabatier, Toulouse, Bayesian Network processing, applications in genetics (haplotype inference) (in French), October 2008-December 2011 (co-supervised with Andres Legarra, INRA SAGA).

Master Students

• Mickaël Gomes, L3 IUT de Toulouse, Intégration du solver ToulBar2 dans NumberJack, March 2012-August 2012.
• Jimmy Vandel, Université Paul Sabatier, Toulouse, Reconstruction de réseau de régulation de gènes à l'aide de données génomiques, February 2009-June 2009.
• Rony Rozas, Université Paul Sabatier, Toulouse, Algorithmes pour la satisfaction de contraintes flexibles ; Optimisation de préférences multi-critères, February 2009-June 2009.
• Joëlson Randriamparany, Université de Fianarantsoa, Madagascar, Etude de la classe des problèmes sous-modulaires pour la résolution des CSP pondérés binaires, September 2006-November 2006.
• Laetitia Albenque, ENSEEIHT, Toulouse, Problème du voyageur de commerce multi-objectifs avec données manquantes, application en bio-informatique à la cartographie comparée, June 2006-August 2006.

Personal links

GomaEsperance

Contact: Simon de Givry Last Update: September 2012