Simon de Givry Permanent researcher (CR1, HdR) at INRA MIAT INRA Centre de recherches de Toulouse Unité de Mathématiques et Informatique Appliquées de Toulouse 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: simon.degivry_AT_toulouse.inra.fr Access from Toulouse: Metro line B (Ramonville exit) then Bus 62 (INRA exit in Castanet-Tolosan)

Events

• CUHK13, invited presentation on Combinatorial Optimization for Life Sciences, Chinese University of Hong-Kong, China, November 1st, 2013.
• 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.

• WCB14, workshop on Constraint Based Methods for Bioinformatics held in conjunction with CP 2014, Lyon, France, September 8th, 2014.
• WCB13, workshop on Constraint Based Methods for Bioinformatics held in conjunction with CP 2013, Uppsala, Sweden, September 16th, 2013.
• 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.

• AIGM14, workshop on Algorithmic issues for Inference in Graphical Models, Paris, France, September 22th, 2014.
• AIGM13, workshop on Algorithmic issues for Inference in Graphical Models, Paris, France, September 13th, 2013.
• AIGM12, workshop on Algorithmic issues for Inference in Graphical Models held in conjunction with ECAI 2012, Montpellier, France, August 28th, 2012.
• AIGM10, workshop on Graphical models for reasoning on biological systems: computational challenges, held in conjunction with ECCS 2012, Lisbon, Portugal, September 16th, 2010.

• 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.

• NETBIO 2014, atelier du réseau méthodologique MIA sur Inférence de réseaux biologiques, Paris, France, 18-19 Septembre, 2014.

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.
• Algorithmes et Modèles probabilistes 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

• numberjack/Toulbar2: A python-based combinatorial optimisation platform. It is designed to support a number of underlying C/C++ solvers including MIP solvers (SCIP,CPLEX,Gurobi), two SAT solvers (MiniSat) and (Walksat), a CP solver (Mistral, versions 1 and 2), and a WCSP solver (Toulbar2). It includes a simple portfolio approach reading flatzinc format.
• 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.

• 4C visitor (2013), a 6-month research experience in the 4C lab to combine WCSP and CP approaches, Cork, Ireland.
• French-Hong-Kong Procore project (2012-2014) towards a practical library of global cost functions.
• French ANR project (2012-2019) on genetic and molecular discovery (WP6) to develop the economic competitiveness of the sunflower crop.
• 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.
• Structure learning of gene networks (in French, 2009-), a research working group supported by INRA MIA.
• 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.
• Jimmy Lee, The Chinese University of Hong-Kong, China. Weighted CSP.
• Brigitte Mangin, INRA MIA, Toulouse, France. Genetics.
• Pedro Meseguer, IIIA-CSIC, Bellaterra, Spain. Weighted CSP.
• Barry O'Sullivan, UCC, head of the 4C team at Cork, Ireland.
• Steve Prestwich, UCC, Cork, Ireland.
• 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 (in French), October 2009 - December 7th 2012 (co-supervised with Brigitte Mangin, INRA MIA). See GeneBayesNet.
• Aurélie Favier, école doctorale MITT, Université Paul Sabatier, Toulouse, Bayesian Network processing, applications in genetics (haplotype inference) (in French), October 2008 - December 12th 2011 (co-supervised with Andres Legarra, INRA SAGA). See toulbar2 and Haplotype inference in half-sib families.

Master Students

• Philippe Leleux, M2R IAICI Université Paul Sabatier, Assemblage de génome à l'aide des réseaux de fonctions de coûts (in French), March 2014-September 25th 2014.
• 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: June 2014