@incollection{Borchers97,
author = "B. Borchers and J.E. Mitchell and S. Joy",
booktitle = "Satisfiability Problem: Theory and Applications",
editor = "D. Du and J. Gu and P.M. Pardalos",
pages = "519-536",
publisher = "AMS",
series = "DIMACS Series in Discrete Mathematics and Theoretical
                   Computer Science",
title = "{A} {B}ranch-{A}nd-{C}ut {A}lgorithm for {MAX}-{SAT} and weighted                    {MAX}-{SAT}",
volume = "35",
year = "1997",
}


@conference{Schiex95b,
author = "H. Fargier and J. Lang and R. Martin-Clouaire and Thomas Schiex",
address = "Montr{\'e}al, Canada",
booktitle = "Proc. of the 11$^th$ Int. Conf. on Uncertainty in                    Artificial Intelligence",
month = "aug",
title = "{A} constraint satisfaction framework for decision under                    uncertainty",
year = "1995",
}


@conference{G08,
author = "L. El Ghaoui and A. Gueye",
booktitle = "Neural Information Processing Systems",
number = "1",
title = "{A} {C}onvex {U}pper {B}ound on the {L}og-{P}artition {F}unction for {B}inary {G}raphical {M}odels",
url = "http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-146.pdf",
year = "2008",
}


@techreport{Barth95,
author = "P. Barth",
institution = "Max-Planck Institut F{\"u}r Informatik",
number = "MPI-I-95-2",
title = "{A} {D}avis-{P}utnam based {E}numeration {A}lgorithm for {L}inear                    {P}seudo-{B}oolean {O}ptimization",
year = "1995",
}


@conference{Ghedira94a,
author = "Khaled Ghedira",
address = "Odense, Denmark",
booktitle = "Proc. of the 5$^th$ European workshop of Modeling                    Autonomous Agents in Multi-Agent World",
title = "{A} {D}istributed approach to {P}artial {C}onstraint                    satisfaction problems",
year = "1994",
}


@conference{Regin94,
author = "J.C. R{\'e}gin",
address = "aaai94l",
booktitle = "aaai94p",
pages = "362-367",
title = "{A} filtering algorithm for constraints of difference in                    {CSP}s",
year = "1994",
}


@techreport{Guesgen94,
author = "Hans Werner Guesgen",
address = "Berkeley, California",
institution = "International Computer Science Institute",
month = "jun",
number = "TR-94-026",
title = "{A} {F}ormal {F}ramework for {W}eak {C}onstraint {S}atisfaction                    {B}ased on {F}uzzy {S}ets",
year = "1994",
}


@incollection{Kumar88a,
author = "Vipin Kumar and Dana S. Nau and Laveen N. Kanal",
booktitle = "Search in Artificial Intelligence",
chapter = "3",
editor = "L. Kanal and V. Kumar",
keywords = "recherche, branch and bound",
pages = "91-130",
publisher = "Springer-Verlag",
title = "{A} {G}eneral {B}ranch and {B}ound {F}ormulation for {O}r/{A}nd                    {G}raph and {G}ame {T}ree {S}earch",
year = "1988",
}


@article{Wer07,
author = "T. Werner",
journal = "IEEE Trans. on Pattern Recognition and Machine                    Intelligence",
month = "jul",
number = "7",
pages = "1165-1179",
title = "{A} {L}inear {P}rogramming {A}pproach to {M}ax-sum                    {P}roblem: {A} {R}eview.",
url = "ftp://cmp.felk.cvut.cz/pub/cmp/articles/werner/Werner-PAMI-2007.pdf",
volume = "29",
year = "2007",
}


@article{CDC+04,
author = "D A. Cohen and M C. Cooper and P G. Jeavons and A A. Krokhin",
journal = "Journal of Artificial Intelligence Research",
pages = "1-22",
title = "{A} {M}aximal {T}ractable {C}lass of {S}oft                    {C}onstraints",
volume = "22",
year = "2004",
}


@article{WJW05,
author = "M J Wainwright and Tommi S Jaakkola and Alan S Willsky",
journal = "IEEE Transactions on Information Theory",
number = "7",
pages = "2313-2335",
title = "{A} {N}ew {C}lass of {U}pper {B}ounds on the {L}og {P}artition {F}unction",
url = "http://people.csail.mit.edu/tommi/papers/WaiJaaWil05_Upper.pdf",
volume = "51",
year = "2005",
}


@conference{ZGS07,
author = "M. Zytnicki and C. Gaspin and T. Schiex",
address = "Dijon, France",
booktitle = "Proceedings of the 2006 ACM Symposium on Applied                    Computing (SAC)",
month = "apr",
pages = "394-398",
title = "{A} new local consistency for weighted {CSP} dedicated                    to long domains",
year = "2007",
}


@article{Hooker88,
author = "J. N. Hooker",
journal = "Decision Support Systems",
keywords = "contraintes, logique propositionnelle, PL, PL01",
number = "4",
pages = "45-69",
title = "{A} {Q}uantitative {A}pproach to {L}ogical {I}nference",
volume = "1",
year = "1988",
}


@article{BB02,
author = "F. Bartolucci and J. Besag",
journal = " Biometrika",
pages = "724-730",
title = "{A} recursive algorithm for {M}arkov random fields",
url = "http://biomet.oxfordjournals.org/content/89/3/724.abstract",
year = "2002",
}


@conference{LK01,
author = "M. Leisink and B. Kappen",
booktitle = "NIPS 2000. Neural Information Processing System",
pages = "266-272",
title = "{A} tighter bound for graphical models",
url = "http://www.snn.ru.nl/nijmegen/components/com_pubman/pubs/Leisink.NC01.pdf",
volume = "13",
year = "2001",
}


@article{Borchers99,
author = "B. Borchers and J. Furman",
journal = "Journal of Combinatorial Optimization",
number = "4",
pages = "299-306",
title = "{A} {T}wo-{P}hase {E}xact {A}lgorithm for {MAX}-{SAT} and {W}eighted                    {MAX}-{SAT} {P}roblems",
volume = "2",
year = "1999",
}


@conference{Bennaceur98,
author = "M. S. Affane and H. Bennaceur",
address = "ecai98l",
booktitle = "ecai98p",
pages = "209--213",
title = "{A} weighted arc consistency technique for {M}ax-{CSP}",
year = "1998",
}


@article{HJ90,
author = "P. Hansen and B. Jaumard",
journal = "Computing",
pages = "279-303",
publisher = "Springer-Verlag",
title = "{A}lgorithms for the {M}aximum {S}atisfiability {P}roblem",
volume = "44",
year = "1990",
}


@techreport{Shafer91,
author = "G. Shafer",
address = "Lawrence",
institution = "University of Kansas, School of Business",
number = "232",
title = "{A}n {A}xiomatic {S}tudy of {C}omputation in {H}ypertrees",
type = "Working paper",
year = "1991",
}


@conference{Horsch00,
author = "Micheal C. Horsch and William S. Havens",
address = "Singapore",
booktitle = "Principles and Practice of Constraint Programming - CP
                   2000",
month = "sep",
pages = "525-530",
series = "LNCS",
title = "{A}n {E}mpirical {S}tudy of {P}robabilistic {A}rc {C}onsistency as
                   a {V}ariable {O}rdering",
volume = "1894",
year = "2000",
}


@conference{Wallace96a,
author = "R. Wallace",
address = "Cambridge, MA",
booktitle = "Proc. of the 2nd International Conference on
                   Principles and Practice of Constraint Programming
                   (CP-96), LNCS 1118",
pages = "482--496",
title = "{A}nalysis of {H}euristic {M}ethods for {P}artial
                   {C}onstraint {S}atisfaction {P}roblems",
year = "1996",
}


@conference{Cabon98,
author = "B. Cabon and S. de Givry and G. Verfaillie",
address = "Pisa, Italy",
booktitle = "Proc. of the 4th International Conference on
                   Principles and Practice of Constraint Programming
                   (CP-98)",
pages = "117--131",
title = "{A}nytime {L}ower {B}ounds for {C}onstraint {V}iolation
                   {M}inimization {P}roblems",
year = "1998",
}


@conference{Wallace-applying,
author = "Richard Wallace and Eugene Freuder",
address = "Amsterdam",
booktitle = "Proceedings ECAI'94 Workshop on Constraint
                   Satisfaction Issues raised by Practical Applications",
editor = "Thomas Schiex and Christian Bessi{\`e}re",
month = "aug",
title = "{A}pplying {A}lgorithms for {C}onstraint {S}atisfaction to
                   {M}aximum {S}atisfiability",
year = "1994",
}


@conference{Tsang90,
author = "Edward P.K. Tsang",
address = "Stockholm, Sweden",
booktitle = "Proc. of the 8$^th$ ECAI",
keywords = "CSP, optimisation, algorithmes genetiques",
pages = "649-654",
title = "{A}pplying {G}enetic {A}lgorithms to {C}onstraint {S}atisfaction
                   {O}ptimization {P}roblems",
year = "1990",
}


@phdthesis{Gaspin90,
author = "C. Gaspin",
address = "Toulouse, France",
keywords = "reseaux de neurones, recuit, contraintes, optimisation",
school = "Ecole Nationale Sup{\'e}rieure de l'A{\'e}ronautique
                   et de l'Espace",
title = "{A}pproche connexionniste des probl{\`e}mes
                   d'optimisation combinatoires en variables bivalentes~:
                   {T}raduction des contraintes",
type = "Th{\`e}se de doctorat",
year = "1990",
}


@incollection{Resende97,
author = "M.G.C. Resende and L.S. Pitsoulis and P.M. Pardalos",
booktitle = "Satisfiability problem: Theory and Applications",
editor = "D. Du and J. Gu and P.M. Pardalos",
pages = "393--405",
publisher = "AMS",
series = "DIMACS Series on Discrete Mathematics and Theoretical
                   Computer Science",
title = "{A}pproximate solution of weighted {MAX}-{SAT} problems                    using {GRASP}.",
volume = "35",
year = "1997",
}


@conference{CD08,
author = "Arthur Choi and Adnan Darwiche",
booktitle = "Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence",
pages = "79-87",
title = "{A}pproximating the {P}artition {F}unction by {D}eleting and then {C}orrecting for {M}odel {E}dges",
url = "http://www.auai.org/uai2008/UAI_camera_ready/choi.pdf",
year = "2008",
}


@article{Bodlaender95,
author = "Hans L. Bodlaender and John R. Gilbert and Hj{\'a}lmt{\'y}r Hafsteinsson and Ton Kloks",
journal = "Journal of Algorithms",
pages = "238-255",
title = "{A}pproximating {T}reewidth, {P}athwidth, {F}rontsize, and
                   {S}hortest {E}limination {T}ree",
volume = "18",
year = "1995",
}


@phdthesis{P01,
author = "N. Peyrard",
title = "{A}pproximations de type champ moyen des mod{\`e}les de champ de {M}arkov pour la segmentation de donn{\'e}es spatiales",
year = "2001",
}


@conference{Schiex00,
author = "T. Schiex",
address = "Marseille",
booktitle = "Actes de JNPC'00",
month = "jun",
title = "{A}rc coh{\'e}rence pour contraintes molles",
year = "2000",
}


@conference{Schiex00b,
author = "T. Schiex",
address = "Singapore",
booktitle = "Principles and Practice of Constraint Programming - CP                    2000",
month = "sep",
pages = "411-424",
series = "LNCS",
title = "{A}rc consistency for soft constraints",
volume = "1894",
year = "2000",
}


@article{cooper.ea04,
author = "M C. Cooper and T. Schiex",
journal = "ai",
number = "1-2",
pages = "199-227",
title = "{A}rc consistency for soft constraints",
volume = "154",
year = "2004",
}


@conference{Zhang03,
author = "A. Rangan and W. Zhang",
address = "Acapulco, Mexico",
booktitle = "ijcai03p",
month = "aug",
note = "To appear",
title = "{B}ackbone {G}uided {L}ocal {S}earch for {M}aximum
                   {S}atisfiability",
year = "2003",
}


@article{FPRW09,
author = "N. Friel and A. N. Pettitt and R. Reeves and E. Wit",
journal = "Journal of Computational and Graphical Statistics",
pages = "243-261",
title = "{B}ayesian inference in hidden {M}arkov random fields for binary data defined on large lattices",
volume = "18",
year = "2009",
}


@conference{Larrosa00,
author = "J. Larrosa",
address = "Singapore",
booktitle = "Principles and Practice of Constraint Programming - CP
                   2000",
month = "sep",
pages = "291--305",
series = "LNCS",
title = "{B}oosting search with variable elimination",
volume = "1894",
year = "2000",
}


@article{LK03,
author = "M. Leisink and B. Kappen",
journal = "Journal of Artificial Intelligence Research",
pages = "139-154",
title = "{B}ound {P}ropagation",
url = "www.jair.org/media/1130/live-1130-2134-jair.ps",
volume = "19",
year = "2003",
}


@conference{terrioux03,
author = "C. Terrioux and P. Jegou",
booktitle = "Proc. of the Ninth International Conference on
                   Principles and Practice of Constraint Programming
                   (CP-2003)",
title = "{B}ounded backtracking for the valued constraint
                   satisfaction problems",
}


@conference{deGivry97,
author = "Simon de Givry and G{\'e}rard Verfaillie and Thomas Schiex",
address = "Schloss Hagenberg, Austria",
booktitle = "Proc. of the Third International Conference on
                   Principles and Practice of Constraint Programming",
month = "oct",
pages = "405-419",
title = "{B}ounding the {O}ptimum of {C}onstraint {O}ptimization
                   {P}roblems",
year = "1997",
}


@conference{MK08,
author = "Joris M Mooij and Hilbert J Kappen",
booktitle = "Advances in Neural Information Processing Systems 21 (NIPS*2008)",
editor = "D. Koller and D. Schuurmans and Y. Bengio and L. Bottou",
pages = "1105--1112",
title = "{B}ounds on marginal probability distributions",
url = "http://people.kyb.tuebingen.mpg.de/jorism/articles/NIPS2008_0950.pdf",
year = "2008",
}


@article{dechter99,
author = "Rina Dechter",
journal = "Artificial Intelligence",
number = "1--2",
pages = "41--85",
title = "{B}ucket {E}limination: {A} {U}nifying {F}ramework for
                   {R}easoning",
volume = "113",
year = "1999",
}


@conference{BenAndMe99,
author = "M. S. Affane and H. Bennaceur and T. Schiex",
booktitle = "Actes de JNPC'99",
pages = "95-102",
title = "{C}omparaison de deux minorants param{\'e}triques pour
                   {M}ax-{CSP}",
year = "1999",
}


@article{Darwiche04,
author = "J. D. Park and A. Darwiche",
journal = "Journal of Artificial Intelligence Research",
pages = "101--133",
title = "{C}omplexity results and {A}pproximation {S}trategies for
                   {MAP} explanations",
volume = "21",
year = "2004",
}


@incollection{Bennaceur03,
author = "H. Bennaceur and A. Osmani",
booktitle = "Developments in Applied Artificial Intelligence",
pages = "217-240",
publisher = "Springer",
series = "22718",
title = "{C}omputing lower bounds for {M}ax-{CSP} problems",
type = "LNCS",
year = "2003",
}


@manual{ConFlex,
author = "",
edition = "1.0",
month = "nov",
note = "Available at textsfhttp://www-bia.inra.fr/T/conflex/Logiciels/welcome.html",
organization = "INRA (Toulouse)",
title = "{C}on'{F}lex {U}ser {M}anual",
year = "1996",
}


@conference{Freuder93,
author = "Richard J. Wallace and Eugene C. Freuder",
address = "aaai93l",
booktitle = "aaai93p",
title = "{C}onjunctive {W}idth {H}euristics for {M}aximal {C}onstraint
                   {S}atisfaction",
year = "1993",
}


@conference{Borning89,
author = "A. Borning and M. Mahert and A. Martindale and M. Wilson",
booktitle = "Int. conf. on logic programming",
keywords = "CSP, CLP, HCLP, preferences, satisfaction partielle,
                   optimisation",
pages = "149-164",
title = "{C}onstraint hierarchies and logic programming",
year = "1989",
}


@conference{Bistarelli00,
author = "S. Bistarelli and R Gennari and F. Rossi",
address = "Singapore",
booktitle = "Principles and Practice of Constraint Programming - CP
                   2000",
month = "sep",
pages = "83-97",
series = "LNCS",
title = "{C}onstraint propagation for {S}oft {C}onstraints:
                   generalizationand {T}ermination conditions",
volume = "1894",
year = "2000",
}


@article{Montanari91,
author = "Ugo Montanari and Francesca Rossi",
journal = "ai",
keywords = "CSP, coherence locale, coherence globale",
pages = "143-170",
title = "{C}onstraint relaxation may be perfect",
volume = "48",
year = "1991",
}


@conference{Meseguer95,
author = "P. Meseguer and J. Larrosa",
address = "ijcai95l",
booktitle = "ijcai95p",
pages = "579-584",
title = "{C}onstraint satisfaction as {G}lobal {O}ptimization",
year = "1995",
}


@conference{Bistarelli95,
author = "S. Bistarelli and U. Montanari and F. Rossi",
address = "ijcai95l",
booktitle = "ijcai95p",
month = "aug",
title = "{C}onstraint {S}olving over {S}emirings",
year = "1995",
}


@article{YFW05,
author = "J. S. Yedidia and W. T. Freeman and Y. Weiss",
journal = "Information Theory, IEEE Transactions on",
number = "7",
pages = "2282--2312",
title = "{C}onstructing free-energy approximations and generalized belief propagation algorithms",
url = "http://www.cs.princeton.edu/courses/archive/spr06/cos598C/papers/YedidaFreemanWeiss2004.pdf",
volume = "51",
year = "2005",
}


@conference{Collinot87,
author = "A. Collinot and C. Le Pape",
address = "ijcai87l",
booktitle = "ijcai87p",
keywords = "CSP, coherence locale",
month = "aug",
title = "{C}ontrolling {C}onstraint {P}ropagation",
year = "1987",
}


@conference{GJ07,
author = "A. Globerson and T. Jaakkola",
booktitle = "Uncertainty in Artificial Intelligence",
title = "{C}onvergent {P}ropagation {A}lgorithms via {O}riented {T}rees ",
url = "http://people.csail.mit.edu/gamir/pubs/GloJaa_UAI07.pdf",
year = "2007",
}


@article{Martin-Clouaire94,
author = "R. Martin-Clouaire and J-P. Rellier",
journal = "AI Applications: Natural Resources, Agriculture, and
                   Environmental Science",
number = "1",
title = "{C}rop {M}anagement {P}lanning as a {F}uzzy and {U}ncertain
                   {C}onstraint {S}atisfaction {P}roblem",
volume = "9",
year = "1995",
}


@conference{Martin-Clouaire93a,
author = "R. Martin-Clouaire",
address = "Aachen, Germany",
booktitle = "Proc. of the First European Congress on Fuzzy and
                   Intelligent Technologies (EUFIT)",
keywords = "CSP, flou, preferences, optimisation, applications",
month = "sep",
title = "{CSP} techniques with fuzzy linear contraints:
                   practical issues",
year = "1993",
}


@conference{Martin-Clouaire92,
author = "R. Martin-Clouaire",
address = "Palma de Mallorca",
booktitle = "Proc. of the International Conference on Information
                   Processing of Uncertainty in Knowledge based Systems",
keywords = "CSP, flou, preferences, optimisation, applications",
month = "jul",
pages = "37-40",
title = "{D}ealing with {S}oft {C}onstraints in a {C}onstraint
                   {S}atisfaction {P}roblem",
year = "1992",
}


@article{Gyssens94,
author = "M. Gyssens and P.G. Jeavons and D. A. Cohen",
journal = "Artificial Intelligence",
pages = "57-89",
title = "{D}ecomposing constraint satisfaction using database
                   techniques",
volume = "66",
year = "1994",
}


@conference{Wah97,
author = "Benjamin W. Wah and Yi Shang",
address = "ijcai97l",
booktitle = "ijcai97p",
pages = "378-383",
title = "{D}iscrete {L}agrangian-{B}ased {S}earch for {S}olving
                   {MAX}-{SAT} {P}roblems",
year = "1997",
}


@article{bessiere2008domain,
author = "C. Bessiere and K. Stergiou and T. Walsh",
journal = "Artificial Intelligence",
number = "6-7",
pages = "800--822",
publisher = "Elsevier",
title = "{D}omain filtering consistencies for non-binary
                   constraints",
volume = "172",
year = "2008",
}


@article{Bensana99,
author = "Eric Bensana and Michel Lema^itre and G{\'e}rard Verfaillie",
journal = "Constraints",
number = "3",
pages = "293-299",
title = "{E}arth {O}bservation {S}atellite {M}anagement",
volume = "4",
year = "1999",
}


@article{Arnborg85,
author = "S. Arnborg",
journal = "BIT",
pages = "2-23",
title = "{E}fficient algorithms for combinatorial problems on
                   graphs with bounded decomposability --- {A} survey",
volume = "25",
year = "1985",
}


@article{PFR03,
author = "A. N. Pettitt and N. Friel and R. Reeves",
journal = "Royal Statistical Society Journal: Series B (Statistical Methodology)",
number = "1",
pages = " 235-246",
title = "{E}fficient calculation of the normalizing constant of the autologistic and related models on the cylinder and lattice",
url = "http://eprints.qut.edu.au/7870/1/7870.pdf",
volume = "65",
year = "2003",
}


@article{RP04,
author = "R. Reeves and A. N. Pettitt",
journal = "Biometrika",
number = "3",
pages = "751-757",
title = "{E}fficient recursions for general factorisable models",
url = "http://biomet.oxfordjournals.org/content/91/3/751.abstract",
volume = "91",
year = "2004",
}


@conference{LGK06,
author = "S.-I. Lee and V. Ganapathi and D. Koller",
booktitle = "Advances in Neural Information Processing Systems
                 (NIPS 2006)",
title = "{E}fficient {S}tructure {L}earning of {M}arkov {N}etworks using {L}1-{R}egularization",
url = "http://ai.stanford.edu/~koller/papers.cgi?entry=Lee+al:NIPS06",
year = "2007",
}


@conference{Freuder91a,
author = "Eugene C. Freuder",
address = "aaai91l",
booktitle = "aaai91p",
keywords = "CSP, representation compacte",
pages = "227-233",
title = "{E}liminating {I}nterchangeable {V}alues in {C}onstraint
                   {S}atisfaction {P}roblems",
year = "1991",
}


@conference{Wallace96,
author = "R. Wallace",
address = "aaai96l",
booktitle = "aaai96p",
pages = "188-195",
publisher = "AAAI Press/MIT Press",
title = "{E}nhancements of {B}ranch and {B}ound {M}ethods for the
                   {M}aximal {C}onstraint {S}atisfaction {P}roblem",
volume = "1",
year = "1996",
}


@article{HG10,
author = "C{\'e}cile Hardouin and Xavier Guyon",
journal = "Comptes Rendus de l'Acad{\'e}mie des Sciences",
number = "3-4",
pages = "199-201",
publisher = "Elsevier Masson SAS",
title = "{E}xact marginals and normalizing constant for {G}ibbs distributions",
url = "http://linkinghub.elsevier.com/retrieve/pii/S1631073X09004051",
volume = "348",
year = "2010",
}


@conference{Sch07,
author = "D. Schlesinger",
booktitle = "Energy Minimization Methods in Computer Vision
                   and Pattern Recognition",
month = "aug",
number = "4679/2007",
pages = "28-38",
series = "LNCS",
title = "{E}xact {S}olution of {P}ermuted {S}ubmodular {M}in{S}um
                   {P}roblems",
year = "2007",
}


@conference{Larrosa2005,
author = "J. Larrosa and S. de Givry and F. Heras and M. Zytnicki",
address = "ijcai05l",
booktitle = "ijcai05p",
month = "aug",
pages = "84--89",
title = "{E}xistential arc consistency: getting closer to full
                   arc consistency in weighted {CSP}s",
year = "2005",
}


@conference{biso00,
author = "Alessandro Biso and Francesca Rossi and Alessandro Sperduti",
address = "San Francisco",
booktitle = "KR2000: Principles of Knowledge Representation and
                   Reasoning",
editor = "Anthony G. Cohn and Fausto Giunchiglia and Bart Selman",
pages = "435--444",
publisher = "Morgan Kaufmann",
title = "{E}xperimental {R}esults on {L}earning {S}oft {C}onstraints",
year = "2000",
}


@conference{Haselbock93,
author = "Alois Haselb{\"o}ck",
address = "ijcai93l",
booktitle = "ijcai93p",
month = "aug",
pages = "282-287",
title = "{E}xploiting {I}nterchangeabilities in {C}onstraint
                   {S}atisfaction {P}roblems",
year = "1993",
}


@conference{Larrosa96,
author = "J. Larrosa and P. Meseguer",
address = "Boston (MA)",
booktitle = "Proc. of CP'96",
pages = "308-322",
title = "{E}xploiting the use of {DAC} in {M}ax-{CSP}",
year = "1996",
}


@conference{degivry06,
author = "de Givry, S. and T. Schiex and G. Verfaillie",
booktitle = "Proc. of the National Conference on Artificial
                   Intelligence, AAAI-2006",
pages = "22--27",
title = "{E}xploiting {T}ree {D}ecomposition and {S}oft {L}ocal
                   {C}onsistency in {W}eighted {CSP}",
year = "2006",
}


@conference{LMP05,
author = "C M. Li and F. Many{\`a} and J. Planes",
address = "Sitges, Spain",
booktitle = "Proc of CP'2005",
number = "3709",
pages = "403-414",
series = "LNCS",
title = "{E}xploiting {U}nit {P}ropagation to {C}ompute {L}ower
                   {B}ounds in {B}ranch and {B}ound {M}ax-{SAT} {S}olvers",
year = "2005",
}


@article{Kirousis93,
author = "Lefteris M. Kirousis",
journal = "ai",
pages = "147-160",
title = "{F}ast parallel constraint satisfaction",
volume = "64",
year = "1993",
}


@conference{Gramm00a,
author = "J. Gramm and R. Niedermeier",
address = "Rome, Italy",
booktitle = "Proceedings of the 4th Italian Conference on
                   Algorithms and Complexity",
editor = " G. Bongiovanni and G. Gambosi and R. Petreschi",
month = "mar",
pages = "174--186",
publisher = "Springer",
series = "LNCS",
title = "{F}aster exact solutions for {M}ax2{S}at",
volume = "1767",
year = "2000",
}


@article{Berlandier95,
author = "Pierre Berlandier",
journal = "Revue d'Intelligence Artificielle",
number = "3",
pages = "225-238",
title = "{F}iltrage de probl{\`e}mes par consistance de chemin
                   restreinte",
volume = "9",
year = "1995",
}


@phdthesis{Bellicha96,
author = "A. Bellicha",
address = "Montpellier, France",
school = "Universit{\'e} de Montpellier~II, Sciences et
                   techniques du Languedoc",
title = "{F}lexibilit{\'e} dans les probl{\`e}mes de satisfaction
                   de contraintes",
type = "Th{\`e}se de doctorat",
year = "1996",
}


@techreport{Dupin93,
author = "de Saint-Cyr, Florence Dupin",
address = "Toulouse, FRANCE",
institution = "I.R.I.T.",
title = "{F}ormalisation et applications de la logique des
                   p{\'e}nalit{\'e}s",
year = "1993",
}


@conference{Satoh90,
author = "Ken Satoh",
address = "Stockholm",
booktitle = "Proc. of the 8$^th$ ECAI",
keywords = "contraintes, preferences, logique",
pages = "585-590",
title = "{F}ormalizing {S}oft {C}onstraints by {I}nterpretation
                   {O}rdering",
year = "1990",
}


@conference{GD10,
author = "V. Gogate and P. Domingos",
booktitle = "26th Conference on Uncertainty in Artificial Intelligence",
title = "{F}ormula-{B}ased {P}robabilistic {I}nference",
url = "http://www.cs.washington.edu/homes/vgogate/papers/uai10.pdf",
year = "2010",
}


@phdthesis{Koster99b,
author = "A M C A. Koster",
address = "The Netherlands",
month = "nov",
note = "Available at www.zib.de/koster/thesis.html.",
school = "University of Maastricht",
title = "{F}requency assignment: {M}odels and {A}lgorithms",
year = "1999",
}


@conference{Debruyne97a,
author = "Romuald Debruyne and Christian Bessi{\`e}re",
address = "Linz, Austria",
booktitle = "Proc. of CP'97",
month = "nov",
number = "1330",
pages = "312-326",
publisher = "Springer-Verlag",
series = "LNCS",
title = "{F}rom {R}estricted {P}ath {C}onsistency to {M}ax-{R}estricted
                   {P}ath {C}onsistency",
year = "1997",
}


@conference{Ruttkay94,
author = "Zsofia Ruttkay",
address = "Orlando, Florida",
booktitle = "Proc. FUZZ-IEEE'94",
title = "{F}uzzy constraint satisfaction",
year = "1994",
}


@article{Fargier94c,
author = "Didier Dubois and H{\'e}l{\`e}ne Fargier and Henri Prade",
journal = "Journal of Intelligent Manufacturing",
title = "{F}uzzy constraints in job-shop scheduling",
year = "1994",
}


@article{Bistarelli2001,
author = "S. Bistarelli and R. Gennari and F. Rossi",
journal = "Constraints: An International Journal",
month = "jan",
number = "1",
title = "{G}eneral {P}roperties and {T}ermination {C}onditions for {S}oft
                   {C}onstraint {P}ropagation",
volume = "8",
year = "2001",
}


@article{Krentel92,
author = "Mark W. Krentel",
journal = "Theoretical Computer Science",
pages = "183--198",
title = "{G}eneralizations of sf {O}pt{P} to the polynomial
                   hierarchy",
volume = "97",
year = "1992",
}


@conference{Schiex94a,
author = "de Saint Cyr, Florence Dupin and J{\'e}r{\^o}me Lang and Thomas Schiex",
address = "France",
booktitle = "Actes de RFIA'94",
keywords = "CSP, Lexico, preferences, optimisation, additif,
                   penalites, flous",
pages = "507-518",
title = "{G}estion de l'inconsistance dans les bases de
                   connaissances~: une approche syntaxique bas{\'e}e sur
                   la logique des p{\'e}nalit{\'e}s",
year = "1994",
}


@article{Lau01,
author = "T.L. Lau and P.K. Tsang",
journal = "Constraints",
number = "4",
pages = "373-398",
title = "{G}uided genetic algorithm and its application to radio
                   link frequency assignment problems",
volume = "6",
year = "2001",
}


@conference{Mills2000,
author = "P. Mills and E. Tsang",
booktitle = "SAT2000 --- Highlights of Satisfiability Research in
                   the Year 2000",
editor = "I.P. Gent and H. van Maaren and T. Walsh",
pages = "89-106",
publisher = " IOS Press, Amsterdam",
title = "{G}uided local search for solving {SAT} and weighted
                   {MAX}-{SAT} problems",
year = "2000",
}


@article{cooper05,
author = "M C. Cooper",
journal = "Constraints",
pages = "283-305",
title = "{H}igh-{O}rder {C}onsistency in {V}alued {C}onstraint
                   {S}atisfaction",
volume = "10",
year = "2005",
}


@misc{KX08,
author = "M. Kolar and E. P. Xing",
title = "{I}mproved {E}stimation of {H}igh-dimensional {I}sing {M}odels",
url = "http://arxiv.org/abs/0811.1239",
year = "2008",
}


@conference{Freuder90a,
author = "P. Snow and E.C. Freuder",
booktitle = "Proc. of the 8$^th$ biennal conf. of the canadian
                   society for comput. studies of intelligence",
month = "may",
pages = "227-230",
title = "{I}mproved {R}elaxation and {S}earch {M}ethods for {A}pproximate
                   {C}onstraint {S}atisfaction with a {M}aximin {C}riterion",
year = "1990",
}


@conference{Larrosa2003,
author = "J. Larrosa and T. Schiex",
address = "ijcai03l",
booktitle = "ijcai03p",
month = "aug",
pages = "239-244",
title = "{I}n the quest of the best form of local consistency for
                   {W}eighted {CSP}",
year = "2003",
}


@incollection{Dubois91,
author = "Didier Dubois and J{\'e}r{\^o}me Lang and Henri Prade",
booktitle = "Fuzzy logic for the Management of Uncertainty",
editor = "L.A. Zadeh and J. Kacprzyk",
pages = "335-351",
publisher = "Wiley and sons",
title = "{I}nconsistency in possibilistic {K}nowledge bases - to
                   live or not to live with it",
year = "1991",
}


@conference{Dixon02,
author = "H. Dixon and M. Ginsberg",
booktitle = "Proceedings of the Eighteenth National Conference on
                   Artificial Intelligence (AAAI-02)",
pages = "635-640",
title = "{I}nference methods for a pseudo-boolean satisfiability
                   solver",
year = "2002",
}


@article{MKGD10,
author = "R. Mateescu and K. Kask and V. Gogate and R. Dechter",
journal = "Journal of Artificial Intelligence Research",
title = "{J}oin-{G}raph {P}ropagation {A}lgorithms",
url = "http://www.jair.org/media/2842/live-2842-4886-jair.pdf",
volume = "37",
year = "2010",
}


@article{M10,
author = "Joris M. Mooij",
journal = "Journal of Machine Learning Research",
month = "Aug",
pages = "2169-2173",
title = "{L}ib{DAI}: {A} {F}ree and {O}pen {S}ource {C}++ {L}ibrary for {D}iscrete {A}pproximate {I}nference in {G}raphical {M}odels",
url = "http://www.jmlr.org/papers/volume11/mooij10a/mooij10a.pdf",
volume = "11",
year = "2010",
}


@article{Lauritzen88,
author = "S.L. Lauritzen and D.J. Spiegelhalter",
journal = "Journal of the Royal Statistical Society -- Series B",
pages = "157-224",
title = "{L}ocal computations with probabilities on graphical
                   structures and their application to expert systems",
volume = "50",
year = "1988",
}


@book{Aarts97,
author = "Emile Aarts and Jan Karel Lenstra",
publisher = "John Wiley and sons",
series = "Interscience Series in Discrete Mathematics and
                   Optimization",
title = "{L}ocal {S}earch in {C}ombinatorial {O}ptimization",
year = "1997",
}


@article{WJ06,
author = "Martin J. Wainwright and Martin I. Jordan",
journal = "IEEE Transactions on Signal Processing",
number = "54",
pages = "2099-2109",
title = "{L}og-{D}eterminant {R}elaxation for {A}pproximate {I}nference in {D}iscrete {M}arkov {R}andom {F}ields",
url = "http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJor06.pdf",
year = "2006",
}


@misc{LVCSP,
author = "M. Lema{\^i}tre",
howpublished = "Available at sf
                   ftp://ftp.cert.fr/pub/lemaitre/LVCSP",
title = "{LVCSP}: a {L}ibrary for {V}alued {CSP}",
}


@conference{Berlandier94,
author = "P. Berlandier and B. Neveu",
address = "New Orleans, LA",
booktitle = "Proc. of the 6$^th$ IEEE International Conference
                   on Tools with Artificial Intelligence (TAI94)",
title = "{M}aintaining {A}rc {C}onsistency through {C}onstraint
                   {R}etraction",
year = "1994",
}


@article{Schiex99,
author = "J. Larrosa and P. Meseguer and T. Schiex",
journal = "ai",
month = "jan",
number = "1",
pages = "149-163",
title = "{M}aintaining {R}eversible {DAC} for {M}ax-{CSP}",
volume = "107",
year = "1999",
}


@conference{WM08,
author = "Ydo Wexler and Christopher Meek",
address = "Vancouver, Canada",
booktitle = "NIPS",
title = "{MAS}: a multiplicative approximation scheme for probabilistic  inference",
year = "2008",
}


@techreport{Schiex98a,
author = "T. Schiex",
institution = "INRA",
month = "jul",
number = "1998/02",
title = "{M}aximizing the reversible {DAC} lower bound in
                   {M}ax-{CSP} is textsf{NP}-hard",
year = "1998",
}


@conference{degivry05,
author = "de Givry, S. and I. Palhiere and Z. Vitezica and T. Schiex",
address = "Sitges, Spain",
booktitle = "Proc. of ICLP-05 workshop on Constraint Based Methods
                   for Bioinformatics",
title = "{M}endelian error detection in complex pedigree using
                   weighted constraint satisfaction techniques",
year = "2005",
}


@conference{Petit2000,
author = "T. Petit and J.C. R{\'e}gin and C. Bessi{\`e}re",
address = "Vancouver, BC, Canada",
booktitle = "Proceedings of IEEE ICTAI'2000",
pages = "358--365",
title = "{M}eta constraints on violations for over constrained
                   problems",
year = "2000",
}


@conference{dechter97minibuckets,
author = "Rina Dechter",
booktitle = "IJCAI",
pages = "1297-1303",
title = "{M}ini-{B}uckets: {A} {G}eneral {S}cheme for {G}enerating
                   {A}pproximations in {A}utomated {R}easoning",
year = "1997",
}


@conference{HLO07,
author = "Federico Heras and Javier Larrosa and Albert Oliveras",
address = "Lisbon, Portugal",
booktitle = "Proc. of SAT'2007",
month = "may",
number = "4501",
pages = "41-55",
series = "LNCS",
title = "{M}ini{M}ax{S}at: {A} {N}ew {W}eighted {M}ax-{SAT}
                   {S}olver",
year = "2007",
}


@article{Minton92,
author = "Steven Minton and Mark D. Johnston and Andrew B. Philips and Philip Laird",
journal = "ai",
keywords = "CSP, satisfaction, heuristiques, scheduling,
                   applications",
month = "dec",
pages = "160-205",
title = "{M}inimizing conflicts: a heuristic repair method for
                   constraint satisfaction and scheduling problems",
volume = "58",
year = "1992",
}


@conference{Schiex96b,
author = "H. Fargier and J. Lang and T. Schiex",
address = "aaai96l",
booktitle = "aaai96p",
month = "aug",
publisher = "AAAI Press",
title = "{M}ixed {C}onstraint {S}atisfaction: a framework for
                   decision problems under incomplete knowledge",
year = "1996",
}


@conference{Freuder96a,
author = "Eugene C. Freuder and Charles D. Elfe",
address = "aaai96l",
booktitle = "aaai96p",
month = "aug",
title = "{N}eighborhood {I}nverse {C}onsistency {P}reprocessing",
year = "1996",
}


@incollection{Dechter88d,
author = "Rina Dechter and Judea Pearl",
booktitle = "Search in Artificial Intelligence",
chapter = "11",
editor = "L. Kanal and V. Kumar",
keywords = "CSP, satisfaction, heuristiques, polynomialite,
                   acyclicite",
pages = "370-425",
publisher = "Springer-Verlag",
title = "{N}etwork-{B}ased {H}euristics for {C}onstraint {S}atisfaction
                   {P}roblems",
year = "1988",
}


@article{KCC08,
author = "Dvijotham Krishnamurthy and Soumen Chakrabarti and Subhasis Chaudhuri",
journal = "Machine Learning",
number = "3",
pages = "205-229",
title = "{N}ew closed-form bounds on the partition function",
url = "http://www.springerlink.com/index/10.1007/s10994-008-5072-8",
volume = "72",
year = "2008",
}


@conference{heras06,
author = "F. Heras and J. Larrosa",
booktitle = "Proc. of the National Conference on Artificial
                   Intelligence, AAAI-2006",
title = "{N}ew {I}nference {R}ules for {E}fficient {M}ax-{SAT}
                   {S}olving",
year = "2006",
}


@conference{JRTP+01,
author = "J-C. R{\'e}gin and T. Petit and C. Bessi{\`e}re and J-F. Puget",
address = "Paphos, Cyprus",
booktitle = "Proc. of CP'2001",
month = "dec",
number = "2239",
pages = "332-345",
series = "LNCS",
title = "{N}ew {L}ower {B}ounds of {C}onstraint {V}iolations for
                   {O}ver-{C}onstrained {P}roblems",
year = "2001",
}


@techreport{Gramm00b,
author = "J. Gramm and E. A. Hirsch and R. Niedermeier and P. Rossmanith",
institution = " Electronic Colloquium on Computational Complexity",
number = "TR00-037",
title = "{N}ew {W}orst-{C}ase {U}pper {B}ounds for {MAX}-2-{SAT} with
                   {A}pplication to {MAX}-{CUT}",
year = "2000",
}


@conference{Dago96a,
author = "P. Dago and G. Verfaillie",
address = "Toulouse, France",
booktitle = "Proc. of ICTAI'96",
title = "{N}ogood {R}ecording for {V}alued {C}onstraint {S}atisfaction
                   {P}roblems",
year = "1996",
}


@book{Bertele72,
author = "Umberto Bertel{\'e} and Francesco Brioshi",
publisher = "Academic Press",
title = "{N}onserial {D}ynamic {P}rogramming",
year = "1972",
}


@conference{Larrosa2002,
author = "J. Larrosa",
address = "Edmondton, (CA)",
booktitle = "Proc. AAAI'02",
pages = "48-53",
title = "{O}n {A}rc and {N}ode {C}onsistency in weighted {CSP}",
year = "2002",
}


@misc{Cooper94b,
author = "M C. Cooper",
note = "{\'E}cole d'{\'e}t{\'e} sur les probl{\`e}mes de
                   satisfaction de contraintes",
title = "{O}n the complexity of fuzzy constraint satisfaction
                   problems",
year = "1994",
}


@article{Beeri83,
author = "C. Beeri and R. Fagin and D. Maier and  M.Yannakakis",
journal = "Journal of the ACM",
keywords = "bases de donnees, arbres, acyclicite",
pages = "479-513",
title = "{O}n the desirability of acyclic database schemes",
volume = "30",
year = "1983",
}


@misc{Larrosa00b,
author = "J. Larrosa and R. Dechter",
howpublished = "CP'2000 Workshop on Soft Constraints",
month = "oct",
title = "{O}n the {D}ual {R}epresentation of non-{B}inary
                   {S}emiring-based {CSP}s",
year = "2000",
}


@article{Coo07,
author = "M C. Cooper",
journal = "Constraints",
note = "To appear.",
title = "{O}n the minimization of locally-defined submodular
                   functions",
year = "2007",
}


@conference{Bayardo95,
author = "Roberto Bayardo and Daniel Miranker",
address = "ijcai95l",
booktitle = "ijcai95p",
pages = "558-562",
title = "{O}n the {S}pace-{T}ime {T}rade-off in {S}olving {C}onstraint
                   {S}atisfaction {P}roblems",
year = "1995",
}


@article{DIPS02,
author = "J-Ch Angles D Auriac and F Igloi and M Preissmann and A Sebo",
pages = "18",
title = "{O}ptimal {C}ooperation and {S}ubmodularity for {C}omputing {P}otts {P}artition {F}unctions with a {L}arge {N}umber of {S}tate",
url = "http://arxiv.org/abs/cond-mat/0204055",
year = "2002",
}


@conference{CdG07,
author = "M C. Cooper and de Givry, S. and T. Schiex",
address = "Hyderabad, India",
booktitle = "Proc. of IJCAI'2007",
month = "jan",
pages = "68-73",
title = "{O}ptimal soft arc consistency",
year = "2007",
}


@incollection{Dechter90a,
author = "R. Dechter and A. Dechter and J. Pearl",
booktitle = "Influence Diagrams, Belief Nets and Decision Analysis",
chapter = "18",
editor = "R.M Oliver and J.Q. Smith",
pages = "411-425",
publisher = "John Wiley {\&} Sons Ltd.",
title = "{O}ptimization in {C}onstraint {N}etworks",
year = "1990",
}


@conference{Freuder89,
author = "Eugene C. Freuder",
address = "ijcai89l",
booktitle = "ijcai89p",
keywords = "CSP, satisfaction partielle, preferences, optimisation",
pages = "278-283",
title = "{P}artial {C}onstraint {S}atisfaction",
year = "1989",
}


@article{Freuder92,
author = "E.C. Freuder and R.J. Wallace",
journal = "ai",
keywords = "CSP, satisfaction partielle, optimisation,preferences,
                   additif",
month = "dec",
pages = "21-70",
title = "{P}artial {C}onstraint {S}atisfaction",
volume = "58",
year = "1992",
}


@conference{Ghedira94,
author = "Khaled Ghedira",
address = "Paris, France",
booktitle = "Proc. of the 14$^th$ international Avignon workshop",
title = "{P}artial {C}onstraint {S}atisfaction by a {M}ulti-{A}gent
                   approach combined with {S}imulated {A}nnealing process",
year = "1994",
}


@conference{Larrosa98,
author = "J. Larrosa and P. Meseguer",
address = "ecai98l",
booktitle = "ecai98p",
pages = "229--233",
title = "{P}artial {L}azy {F}orward {C}hecking for {MAX}-{CSP}",
year = "1998",
}


@conference{Larrosa99,
author = "J. Larrosa and P. Meseguer",
booktitle = "Proc. of the 5$^th$ International Conference on
                   Principles and Practice of Constraint Programming
                   (CP-99)",
pages = "303-315",
title = "{P}artition-{B}ased {L}ower {B}ound for {M}ax-{CSP}",
year = "1999",
}


@conference{Aloul02b,
author = "F. Aloul and A. Ramani and I. Markov and K. Sakallah",
address = "Cincinnati, (OH)",
booktitle = "Symposium on the Theory and Applications of
                   Satisfiability Testing (SAT)",
pages = "346-353",
title = "{PBS}: {A} {B}acktrack-{S}earch {P}seudo-{B}oolean {S}olver and
                   {O}ptimizer",
year = "2002",
}


@conference{Dupin94,
author = "de Saint Cyr, Florence Dupin and J{\'e}r{\^o}me Lang and Thomas Schiex",
booktitle = "Proc. of the 10$^th$ International Conference on
                   Uncertainty in Artificial Intelligence",
title = "{P}enalty logic and its link with {D}empster-{S}hafer theory",
year = "1994",
}


@conference{Montanari91a,
author = "Ugo Montanari and Francesca Rossi",
booktitle = "Proc. of the $8^th$ international conference on
                   Logic Programming",
editor = "Koichi Furukawa",
keywords = "CSP, PLC, coherence locale, coherence globale",
pages = "223-237",
publisher = "The MIT Press",
title = "{P}erfect {R}elaxation in {C}onstraint {L}ogic {P}rogramming",
year = "1991",
}


@conference{AFW94,
author = "N. Alon and A. D. Frieze and D. Welsh",
booktitle = "35th Annual Symposium on Foundations of Computer Science",
title = "{P}olynomial time randomised approximation schemes for the {T}utte polynomial of dense graphs",
year = "1994",
}


@article{JS93,
author = "M. Jerrum and A. Sinclair",
journal = "SIAM Journal on Computing",
pages = "1087-1116",
title = "{P}olynomial-time {A}pproximation {A}lgorithms for the {I}sing {M}odel",
url = "http://www.cs.berkeley.edu/~sinclair/",
volume = "22",
year = "1993",
}


@conference{Schiex92,
author = "T. Schiex",
address = "Stanford, CA",
booktitle = "Proc. of the 8$^th$ Int. Conf. on Uncertainty in
                   Artificial Intelligence",
keywords = "CSP, preferences, optimisation, satisfaction
                   partielle,flou",
month = "jul",
pages = "269--275",
title = "{P}ossibilistic {C}onstraint {S}atisfaction {P}roblems or
                   ``{H}ow to handle soft constraints~?''",
year = "1992",
}


@conference{Lang91,
author = "J{\'e}r{\^o}me Lang",
booktitle = "FAIR'91",
keywords = "logique propositionnelle, preferences, flou,
                   contraintes, optimisation, satisfaction partielle",
title = "{P}ossibilistic {L}ogic as a {L}ogical {F}ramework for {M}in-{M}ax
                   {D}iscrete {O}ptimisation {P}roblems and {P}rioritized
                   {C}onstraints",
year = "1991",
}


@techreport{Schiex94d,
author = "T. Schiex",
institution = "CERT",
number = "2/7899 DER",
title = "{P}r{\'e}f{\'e}rences et incertitudes dans les
                   probl{\`e}mes de satisfaction de {C}ontraintes",
year = "1994",
}


@book{Pearl88,
author = "Judea Pearl",
address = "Palo Alto",
publisher = "Morgan Kaufmann",
title = "{P}robabilistic {R}easoning in {I}ntelligent {S}ystems,
                   {N}etworks of {P}lausible {I}nference",
year = "1988",
}


@article{Fargier95,
author = "H. Fargier and D. Dubois and H. Prade",
journal = "Revue d'Intelligence Artificielle",
number = "3",
pages = "311--354",
title = "{P}robl{\`e}mes de satisfaction de contraintes
                   flexibles: une approche {\'e}galitariste",
volume = "9",
year = "1995",
}


@article{Schiex97,
author = "T. Schiex and H. Fargier and G. Verfaillie",
journal = "Revue d'Intelligence Artificielle",
number = "3",
pages = "339--373",
title = "{P}robl{\`e}mes de satisfaction de contraintes
                   valu{\'e}s",
volume = "9",
year = "1997",
}


@phdthesis{Fargier94,
author = "H{\'e}l{\`e}ne Fargier",
address = "Toulouse, France",
month = "jun",
school = "Institut de Recherche en Informatique de Toulouse
                   (Universit{\'e} Paul Sabatier)",
title = "{P}robl{\`e}mes de satisfaction de contraintes flexibles
                   et application {\`a} l'ordonnancement de production",
type = "Th{\`e}se de doctorat",
year = "1994",
}


@incollection{Fargier93,
author = "Didier Dubois and H{\'e}l{\`e}ne Fargier and Henri Prade",
booktitle = "Fuzzy Sets, Neural Networks and Soft Computing",
editor = "Yager R.R. and Zadeh L.A.",
pages = "166-187",
publisher = "Kluwer Acad.",
title = "{P}ropagation and {S}atisfaction of fuzzy constraints",
year = "1993",
}


@article{boros02,
author = "E. Boros and P. Hammer",
journal = "Discrete Appl. Math.",
pages = "155-225",
title = "{P}seudo-{B}oolean {O}ptimization",
volume = "123",
year = "2002",
}


@article{cabon.ea99,
author = "B. Cabon and S. de Givry and L. Lobjois and T. Schiex and J.P. Warners",
journal = "Constraints",
pages = "79-89",
title = "{R}adio {L}ink {F}requency {A}ssignment",
volume = "4",
year = "1999",
}


@article{Lecoutre09,
author = "C. Lecoutre and L Sa{\"i}s and S. Tabary and V. Vidal",
journal = "ai",
pages = "1592,1614",
title = "{R}easoning from last conflict(s) in constraint programming",
volume = "173",
year = "2009",
}


@conference{JJ96,
author = "T. Jaakkola and M. Jordan",
booktitle = "Advances in Neural Information Processing Systems (NIPS 9)",
pages = "487-493",
title = "{R}ecursive algorithms for approximating probabilities in graphical models",
url = "http://people.csail.mit.edu/tommi/ml.html",
year = "1996",
}


@article{CooperFCSP,
author = "M C. Cooper",
journal = "Fuzzy Sets and Systems",
number = "3",
pages = "311-342",
title = "{R}eduction operations in fuzzy or valued constraint
                   satisfaction",
volume = "134",
year = "2003",
}


@article{Fargier94d,
author = "Didier Dubois and H{\'e}l{\`e}ne Fargier and Henri Prade",
journal = "Fuzzy sets and systems",
title = "{R}efinements of the min-max approach to decision making
                   in fuzzy environments",
year = "1994",
}


@conference{Hertzberg88,
author = "J. Hertzberg and H.W. Guesgen and A. Voss and M. Fidelak and H. Voss",
address = "Eringerfeld, Germany",
booktitle = "GWAI'88",
pages = "61--65",
title = "{R}elaxing {C}onstraint {N}etworks to {R}esolve
                   {I}nconsistencies",
year = "1988",
}


@conference{Heras2005,
author = "J. Larrosa and F. Heras",
address = "ijcai05l",
booktitle = "ijcai05p",
pages = "193-198",
title = "{R}esolution in {M}ax-{SAT} and its relation to local
                   consistency in weighted {CSP}s",
year = "2005",
}


@conference{Schiex98,
author = "J. Larrosa and P. Meseguer and T. Schiex and G. Verfaillie",
address = "aaai98l",
booktitle = "aaai98p",
month = "jul",
title = "{R}eversible {DAC} and {O}ther {I}mprovements for {S}olving
                   {M}ax-{CSP}",
year = "1998",
}


@article{HHS84,
author = "P.L. Hammer and P. Hansen and B. Simeone",
journal = "Math. Programming",
pages = "121--155",
title = "{R}oof duality, complementation and persistency in
                   quadratic 0-1 optimization",
volume = "28",
year = "1984",
}


@conference{Verfaillie96,
author = "G. Verfaillie and M. Lema^itre and T. Schiex",
address = "aaai96l",
booktitle = "aaai96p",
pages = "181-187",
title = "{R}ussian {D}oll {S}earch",
year = "1996",
}


@conference{Sanchez09,
author = "M. Sanchez and D. Allouche and S. de Givry and T. Schiex",
address = "San Diego (CA), USA",
booktitle = "Proc. IJCAI'09",
pages = "603-608",
title = "{R}ussian {D}oll {S}earch with {T}ree {D}ecomposition",
url = "http://www.inra.fr/mia/T/schiex/Export/Soft08.pdf",
year = "2009",
}


@conference{Schiex92d,
author = "H{\'e}l{\`e}ne Fargier and Roger Martin-Clouaire and Thomas Schiex",
address = "N{\^i}mes, France",
booktitle = "Journ{\'e}es nationales << Les applications des
                   ensembles flous >>",
keywords = "CSP, preferences, optimisation, flou",
month = "oct",
pages = "183-191",
title = "{S}atisfaction de contraintes souples",
year = "1992",
}


@conference{Beringer93,
author = "Henri Beringer and de Backer, Bruno",
address = "ijcai93l",
booktitle = "ijcai93p",
keywords = "contraintes lin{\'e}aires, simplex, disjonctions",
month = "aug",
pages = "296--301",
title = "{S}atisfiability of {B}oolean formulas over linear
                   constraints",
year = "1993",
}


@article{Rosenfeld76,
author = "A. Rosenfeld and R. Hummel and S. Zucker",
journal = "IEEE Trans. on Systems, Man, and Cybernetics",
keywords = "CSP, flou, probabilites,vision, applications",
number = "6",
pages = "173-184",
title = "{S}cene {L}abeling by {R}elaxation {O}perations",
volume = "6",
year = "1976",
}


@conference{Schiex93c,
author = "H. Fargier and J. Lang and T. Schiex",
booktitle = "Proc. of the 1$^st$ European Congress on Fuzzy and
                   Intelligent Technologies",
keywords = "CSP, Lexico, preferences, optimisation, flou",
title = "{S}electing preferred solutions in {F}uzzy {C}onstraint
                   {S}atisfaction {P}roblems",
year = "1993",
}


@article{Bistarelli97,
author = "S. Bistarelli and U. Montanari and F. Rossi",
journal = "Journal of the ACM",
number = "2",
pages = "201--236",
title = "{S}emiring based constraint solving and {O}ptimization",
volume = "44",
year = "1997",
}


@incollection{Bistarelli96,
author = "S. Bistarelli and H. Fargier and U. Montanari and F. Rossi and T. Schiex and G. Verfaillie",
booktitle = "Over-Constrained Systems",
editor = "M. Jampel and E. Freuder and M. Maher",
number = "1106",
pages = "111-150",
publisher = "Springer Verlag",
series = "LNCS",
title = "{S}emiring-based {CSP}s and {V}alued {CSP}s: {B}asic {P}roperties
                   and {C}omparison",
year = "1996",
}


@article{Bistarelli99,
author = "S. Bistarelli and H. Fargier and U. Montanari and F. Rossi and T. Schiex and G. Verfaillie",
journal = "Constraints",
pages = "199-240",
title = "{S}emiring-based {CSP}s and {V}alued {CSP}s: {F}rameworks,
                   {P}roperties and {C}omparison",
volume = "4",
year = "1999",
}


@article{Tarjan84,
author = "R. Tarjan and M. Yannakakis",
journal = "SIAM J. Comput.",
number = "3",
pages = "566-579",
title = "{S}imple linear-time algorithms to test chordality of
                   graphs, test acyclicity of hypergraphs and selectively
                   reduce acyclic hypergraphs",
volume = "13",
year = "1984",
}


@conference{givry04,
author = "de Givry, S.",
address = "Toronto, Canada",
booktitle = "CP-04 Workshop on Preferences and Soft
                   Constraints",
title = "{S}ingleton consistency and dominance rules in weighted
                   {CSP}s",
year = "2004",
}


@article{Sch76,
author = "M.I. Schlesinger",
journal = "Kibernetika",
pages = "113--130",
title = "{S}intaksicheskiy analiz dvumernykh zritelnikh signalov
                   v usloviyakh pomekh ({S}yntactic analysis of
                   two-dimensional visual signals in noisy conditions)",
volume = "4",
year = "1976",
}


@conference{cooper06,
author = "M. Cooper and S. Cussat-Blanc and M. De Roquemaurel and P. R{\'e}gnier",
address = "Nantes, France",
booktitle = "Proc. of CP'06",
number = "4204",
pages = "680-684",
publisher = "Springer",
series = "LNCS",
title = "{S}oft arc consistency applied to optimal planning",
year = "2006",
}


@incollection{Soft06,
author = "P. Meseguer and F. Rossi and T. Schiex",
booktitle = " Handbook of Constraint Programming ",
chapter = " 9 ",
editor = " Rossi, F. and van Beek, P. and Walsh, T. ",
publisher = " Elsevier ",
title = "{S}oft {C}onstraints {P}rocessing",
url = "http://www.elsevier.com/wps/find/bookdescription.cws_home/708863/description#description",
year = "2006",
}


@techreport{Koster99,
author = "A.M.C.A Koster and van Hoesel, S.P.M and A.W.J. Kolen",
address = "Maastricht, The Netherlands",
institution = "Universiteit Maastricht",
number = "RM/99/011",
title = "{S}olving {F}requency {A}ssignment {P}roblems via
                   {T}ree-{D}ecomposition",
year = "1999",
}


@conference{deGivry2003,
author = "Simon de Givry and Javier Larrosa and Pedro Meseguer and Thomas Schiex",
address = "Kinsale, Ireland",
booktitle = "Proc. of the Ninth International Conference on
                   Principles and Practice of Constraint Programming",
month = "oct",
publisher = "Springer Verlag",
series = "LNCS",
title = "{S}olving {M}ax-{S}at as weighted {CSP}",
year = "2003",
}


@conference{Jegou95,
author = "Philippe J{\'e}gou and Fabrice Bouquet",
address = "Cassis, France",
booktitle = "Proceedings of the CP'95 Workshop on Over-Constrained
                   Systems",
month = "sep",
title = "{S}olving {O}ver-constrained {CSP} using weighted {OBDD}",
year = "1995",
}


@conference{jiang95,
author = "Y. Jiang and H. Kautz and B. Selman",
booktitle = "Proceedings of the 1st Workshop on Artificial
                   Intellignce and Operations Research.",
title = "{S}olving {P}roblems with {H}ard and {S}oft {C}onstraints {U}sing
                   a {S}tochastic {A}lgorithm for {MAX}-{SAT}",
year = "1995",
}


@conference{Zabih90,
author = "Ramin Zabih",
address = "aaai90l",
booktitle = "aaai90p",
keywords = "graphes, CSP",
pages = "46-51",
title = "{S}ome {A}pplications of {G}raph {B}andwidth to {C}onstraint
                   {S}atisfaction {P}roblems",
year = "1990",
}


@article{VanEmden86,
author = "van Emden, M.H. and M. Okhi and A. Takeuchi",
journal = "New Generation Computing",
keywords = "programmation logique",
number = "4",
title = "{S}peadsheets with {I}ncremental {Q}ueries as {U}ser {I}nterface
                   for {L}ogic {P}rogramming",
year = "1986",
}


@article{PG97,
author = "G. Potamianos and J. Goutsias",
journal = "IEEE Transactions on Information Theory",
number = "6",
pages = "1948-1965",
title = "{S}tochastic approximation algorithms for partition function estimation of {G}ibbs random fields",
url = "http://www.stat.duke.edu/~scs/Courses/Stat376/Papers/NormConstants/PotamianosGoutsiasIEEE1997.pdf",
volume = "43",
year = "1997",
}


@article{Shapiro81,
author = "L. Shapiro and R. Haralick",
journal = "IEEE Transactions on Pattern Analysis and Machine
                   Intelligence",
pages = "504-519",
title = "{S}tructural descriptions and inexact matching",
volume = "3",
year = "1981",
}


@conference{SMFR08,
author = "M. Schmidt and  Murphy K. and G. Fung and Rosales R.",
booktitle = "CVPR'08",
title = "{S}tructure {L}earning in {R}andom {F}ields for {H}eart {M}otion {A}bnormality {D}etection",
year = "2008",
}


@article{Minoux76,
author = "M. Minoux",
journal = "Recherche op{\'e}rationnelle",
number = "6",
pages = "33-62",
title = "{S}tructures alg{\'e}briques g{\'e}n{\'e}ralis{\'e}es
                   des probl{\`e}mes de cheminement dans les graphes",
volume = "10",
year = "1976",
}


@conference{Xu02,
author = "H. Xu and R. A. Rutenbar and K. Sakallah",
address = "San Diego (CA)",
booktitle = "Proc. Int. Symp. on Physical Design",
month = "apr",
title = "{S}ub-{SAT}: {A} {F}ormulation for {R}elaxed {B}oolean
                   {S}atisfiability with {A}pplications in {R}outing",
year = "2002",
}


@phdthesis{M07,
author = "M. Molkaraie",
title = "{S}ubtree-based bounds and simulation-based estimations for the partition function.",
year = "2007",
}


@conference{galinier97,
author = "Philippe Galinier and Jin-Kao Hao",
booktitle = "Principles and Practice of Constraint Programming -
                   CP'97",
number = "1330",
pages = "196-208",
series = "LNCS",
title = "{T}abu {S}earch for {M}aximal {C}onstraint {S}atisfaction
                   {P}roblems",
year = "1997",
}


@article{Z96,
author = "J. Zhang",
journal = "IEEE Transactions on Image Processing",
number = "7",
pages = "1208-1214",
title = "{T}he application of the {G}ibbs-{B}ogoliubov-{F}eynman inequality
               in mean field calculations for {M}arkov random fields",
volume = "5",
year = "1996",
}


@conference{Fargier93a,
author = "D. Dubois and H. Fargier and H. Prade",
address = "San Francisco, CA",
booktitle = "Proc. 2$^nd$ IEEE Conference on Fuzzy Systems",
month = "mar",
title = "{T}he calculus of fuzzy restrictions as a basis for
                   flexible constraint satisfaction",
year = "1993",
}


@article{Krentel88,
author = "M. Krentel",
journal = "Journal of Computer and System Sciences",
pages = "490-509",
title = "{T}he {C}omplexity of {O}ptimization {P}roblems",
volume = "36",
year = "1988",
}


@techreport{Pothen88,
author = "A. Pothen",
institution = "Pennsylvania State University",
number = "CS-88-13",
title = "{T}he complexity of optinal elimination trees",
year = "1988",
}


@article{CCJ+06,
author = "D A. Cohen and M C. Cooper and P G. Jeavons and A A. Krokhin",
journal = "Artificial Intelligence",
month = "aug",
number = "11",
pages = "983 - 1016",
title = "{T}he complexity of soft constraint satisfaction",
volume = "170",
year = "2006",
}


@conference{Dechter87,
author = "Rina Dechter and Judea Pearl",
address = "Orlando FL",
booktitle = "Proc. of the 3rd IEEE Conference on AI Applications",
keywords = "CSP, decomposition, coupe-cycle, cycle cutset",
pages = "224-230",
title = "{T}he {C}ycle-{C}utset {M}ethod for {I}mproving {S}earch
                   {P}erformance in {AI}",
year = "1987",
}


@article{Liu92,
author = "J. W. H. Liu",
journal = "SIAM Review",
note = "First papers on the multifrontal technique go back to
                   1983",
pages = "82-109",
title = "{T}he multifrontal method for sparse matrix solution:
                   {T}heory and practice",
volume = "34",
year = "1992",
}


@article{Papadimitriou76,
author = "C.H. Papadimitriou",
journal = "Computing",
pages = "263-270",
title = "{T}he {NP}-completeness of the bandwidth minimization
                   problem",
volume = "16",
year = "1976",
}


@article{Liu90,
author = "J. W. H. Liu",
journal = "SIAM Journal on Matrix Analysis and Applications",
pages = "134-172",
title = "{T}he role of elimination tree in sparse factorization",
volume = "11",
year = "1990",
}


@misc{softcsp,
author = "S. de Givry and F. Heras and J. Jarrosa and E. Rollon and T. Schiex",
howpublished = "textsfcarlit.toulouse.inra.fr/cgi-bin/awki.cgi/softcsp",
title = "{T}he {S}oft{CSP} and {M}ax-{SAT} benchmarks and
                   algorithm web site.",
year = "2003",
}


@conference{Dechter96,
author = "Rina Dechter",
address = "Fort Lauderdale, Florida",
booktitle = "Prec. of the 4$^th$ international symposium on
                   Artificial Intelligence and Mathematics",
month = "jan",
pages = "46-51",
title = "{T}opological parameters for time-space tradeoff",
year = "1996",
}


@conference{Boutilier94,
author = "C. Boutilier",
booktitle = "Proc. of KR'94",
pages = "75-86",
title = "{T}owards alogic for qualitative decision theory",
year = "1994",
}


@conference{OttenDechter10,
author = "L. Otten and R. Dechter",
address = "Fort Lauderdale (FL), USA",
booktitle = "Proc. of ISAIM'2010",
title = "{T}owards {P}arallel {S}earch for {O}ptimization in {G}raphical {M}odels",
year = "2010",
}


@article{Fargier96,
author = "H{\'e}l{\`e}ne Fargier and J{\'e}r{\^o}me Lang and Roger Martin-Clouaire and Thomas Schiex",
journal = "Revue d'Intelligence Artificielle",
number = "3",
pages = "375--398",
title = "{T}raitement de probl{\`e}mes de d{\'e}cision sous
                   incertitude par des probl{\`e}mes de satisfaction de
                   contraintes",
volume = "11",
year = "1997",
}


@conference{Wah99,
author = "Zhe Wu and Benjamin W. Wah",
address = "aaai99l",
booktitle = "aaai99p",
pages = "673--678",
title = "{T}rap {E}scaping {S}trategies in {D}iscrete {L}agrangian
                   {M}ethods for {S}olving {H}ard {S}atisfiability and {M}aximum
                   {S}atisfiability {P}roblems",
year = "1999",
}


@article{Dechter89a,
author = "Rina Dechter and Judea Pearl",
journal = "ai",
keywords = "CSP, decomposition, tree-clustering, regroupement en
                   hyper-arbre",
pages = "353-366",
title = "{T}ree {C}lustering for {C}onstraint {N}etworks",
volume = "38",
year = "1989",
}


@conference{Dechter88a,
author = "Rina Dechter and Judea Pearl",
address = "aaai88l",
booktitle = "aaai88p",
keywords = "CSP, decomposition, tree-clustering, regroupement en
                   hyper-arbre",
pages = "150-154",
title = "{T}ree {C}lustering {S}chemes for {C}onstraint {P}rocessing",
year = "1988",
}


@conference{Meiri90,
author = "Itay Meiri and Rina Dechter and Judea Pearl",
address = "aaai90l",
booktitle = "aaai90p",
keywords = "CSP, acyclicite, polynomialite, reduction",
pages = "10-16",
title = "{T}ree {D}ecomposition with {A}pplications to {C}onstraint
                   {P}rocessing",
year = "1990",
}


@conference{Fargier-uncertainty,
author = "H{\'e}l{\`e}ne Fargier and J{\'e}r{\^o}me Lang and Roger Martin-Clouaire and Jean-Pierre Rellier",
address = "Amsterdam",
booktitle = "Proceedings ECAI'94 Workshop on Constraint
                   Satisfaction Issues raised by Practical Applications",
editor = "Thomas Schiex and Christian Bessi{\`e}re",
month = "aug",
title = "{U}ncertainty and {F}lexibility in {C}onstraint
                   {S}atisfaction: {A} {C}ase {S}tudy",
year = "1994",
}


@conference{Fargier93c,
author = "H. Fargier and J. Lang",
address = "Grenade, Spain",
booktitle = "Proc. of ECSQARU '93",
month = "nov",
pages = "97-104",
series = "LNCS",
title = "{U}ncertainty in constraint satisfaction problems: a
                   probabilistic approach",
volume = "747",
year = "1993",
}


@article{KKRD+05,
author = "K. Kask and R. Dechter and J. Larrosa and A. Dechter",
journal = "Artificial Intelligence",
number = "1-2",
pages = "165-193",
title = "{U}nifying {C}luster-{T}ree {D}ecompositions for
                   {R}easoning in {G}raphical models",
volume = "166",
year = "2005",
}


@conference{Fargier93b,
author = "Didier Dubois and H{\'e}l{\`e}ne Fargier and Henri Prade",
address = "Chambery, France",
booktitle = "Proc. of IJCAI-93/SIGMAN Workshop on Knowledge-based
                   Production Planning, Scheduling and Control",
month = "aug",
title = "{U}sing fuzzy constraints in job-shop scheduling",
year = "1993",
}


@incollection{Shenoy91,
author = "P. Shenoy",
booktitle = "Uncertainty in AI",
editor = "Bonissone and Henrion and Kanal and Lemmer",
publisher = "North-Holland Publishers",
title = "{V}aluation-based systems for discrete optimization",
year = "1991",
}


@conference{Schiex95a,
author = "T. Schiex and H. Fargier and G. Verfaillie",
address = "ijcai95l",
booktitle = "ijcai95p",
month = "aug",
pages = "631-637",
title = "{V}alued {C}onstraint {S}atisfaction {P}roblems: hard and easy
                   problems",
year = "1995",
}