<!doctype html public "-//w3c//dtd html 4.0 transitional//en"> <html> <head>    <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">    <meta name="GENERATOR" content="Mozilla/4.5 [fr] (WinNT; I) [Netscape]">    <meta name="Author" content="Christian Bessire, Laurent Henocque">    <title>JNPC2000 : 6emes journees Nationales de R&eacute;solution Pratique de Probl&egrave;mes NP Complets</title> </head> <body bgcolor="#FFFFFF">  <center><font size=-2><a href="mailto:henocque@esil.univ-mrs.fr">Derni&egrave;re modification le 29 mai 2000</a></font></center>  <p><br> <center> <h1> JNPC'2000</h1></center>  <center> <h2> 6&egrave;mes Journ&eacute;es Nationales sur la R&eacute;solution Pratique</h2></center>  <center> <h2> de Probl&egrave;mes NP-Complets</h2></center>  <center> <h3> Marseille - France</h3></center>  <center> <h3> 28-30 Juin 2000</h3></center>  <ul> <li> <a href="#objectifs">Objectifs</a></li>  <li> <a href="#themes">Th&egrave;mes</a></li>  <li> <a href="#comite">Comit&eacute; de Programme</a></li>  <li> <a href="#soumission">Soumission</a></li>  <li> <a href="#invites">Conf&eacute;rences Invit&eacute;es</a></li>  <li> <a href="#calendrier">Calendrier</a></li>  <li> <a href="#organisation">Organisation, Contact</a></li>  <li> <a href="http://www.esil.univ-mrs.fr/jnpc2000/sessindus.html">Session Industrielle</a></li>  <li> <a href="http://www.esil.univ-mrs.fr/jnpc2000/programme.html">Programme</a></li>  <li> <a href="http://www.esil.univ-mrs.fr/jnpc2000/inscription.html">Formulaire d'Inscription</a></li>  <li> <a href="http://www.esil.univ-mrs.fr/jnpc2000/participation.html">Appel &agrave; Participation</a></li>  <li> <a href="http://www.esil.univ-mrs.fr/jfplc2000/lieu.html">Informations Pratiques</a> (communes &agrave; <a href="http://www.esil.univ-mrs.fr/jfplc2000">JFPLC'2000</a>)</li> </ul>  <hr><a NAME="objectifs"></a> <h2> Objectifs</h2> Dans la continuit&eacute; des manifestations pr&eacute;c&eacute;dentes, organis&eacute;es &agrave; Montpellier (1994), Dijon (1996), Rennes (1997), Nantes (<a href="http://www.emn.fr/info/contraintes/liste-JNPC-98.html">1998</a>) et Lyon (<a href="http://www.cert.fr/fr/dcsd/CD/CDPUB/MEMBRES/verfaillie/JNPC99/programme.html">1999</a>), les 6&egrave;mes Journ&eacute;es Nationales sur la R&eacute;solution Pratique de Probl&egrave;mes NP-Complets, organis&eacute;es cette ann&eacute;e &agrave; Marseille, se veulent le lieu de rencontre, de discussion et d'&eacute;change pour la communaut&eacute; des chercheurs impliqu&eacute;s dans la r&eacute;solution pratique de probl&egrave;mes NP-complets: SAT (satisfiabilit&eacute; d'une expression bool&eacute;enne), CSP (probl&egrave;mes de satisfaction de contraintes), PLNE (programmation lin&eacute;aire en nombre entiers), probl&egrave;mes combinatoires apparaissant dans les applications, etc. Initi&eacute;es par le groupe RESSAC de l'ex PRC-Intelligence Artificielle, ces journ&eacute;es sont organis&eacute;es a l'initiative du Groupe de travail "<a href="http://www.lim.univ-mrs.fr/~gtalgo">Algorithmes</a>" du <a href="http://www-timc.imag.fr/I3/">GDR-I3</a>. <p>Des pr&eacute;sentations sont donc attendues sur des aspects aussi divers que la proposition de cadres g&eacute;n&eacute;riques de repr&eacute;sentation, d'extensions ou de restrictions des cadres existants, l'utilisation conjointe de plusieurs cadres de repr&eacute;sentation, la caract&eacute;risation des probl&egrave;mes (relations entre probl&egrave;mes, sous probl&egrave;mes polynomiaux, etc), la proposition de m&eacute;thodes de r&eacute;solution g&eacute;n&eacute;riques ou sp&eacute;cifiques, compl&egrave;tes ou incompl&egrave;tes, l'hybridation de m&eacute;thodes existantes, la pr&eacute;sentation de r&eacute;sultats th&eacute;oriques ou exp&eacute;rimentaux relatifs &agrave; la complexit&eacute;, des r&eacute;ponses aux probl&egrave;mes de mise en oeuvre dans des contextes particuliers (incertains, dynamiques, temporellement contraints, interruptibles, distribu&eacute;s, interactifs, etc.), la pr&eacute;sentation d'&eacute;tudes de cas et de bilans d'utilisation de m&eacute;thodes et d'outils, etc. <p>Ces journ&eacute;es sont aujourd'hui le lieu de rencontre annuel des chercheurs impliqu&eacute;s dans l'Axe Algorithmes du <a href="http://www-timc.imag.fr/I3/">GDR-I3</a>. Mais elles sont bien entendu ouvertes &agrave; toute personne d&eacute;sirant y pr&eacute;senter les r&eacute;sultats de ses travaux. <p>JNPC'2000 est organis&eacute; &agrave; l'Ecole Sup&eacute;rieure d'Ing&eacute;nieurs de Luminy (<a href="http://www.esil.univ-mrs.fr">ESIL</a>) sur le campus du <a href="http://www.agl.univ-mrs.fr">Parc Scientifique et Technologique de Marseille-Luminy</a> avec le soutien du Laboratoire d'Informatique de Marseille (<a href="http://www.lim.univ-mrs.fr">LIM</a>), de l'Universit&eacute; de la M&eacute;diterran&eacute;e (<a href="http://mediterranee.univ-aix.fr">U2</a>), de l'Universit&eacute; de Provence (<a href="http://www.up.univ-mrs.fr/">U1</a>) et de l'Universit&eacute; d'Aix -Marseille III (<a href="http://www.u-3mrs.fr/">U3</a>). <p>Comme l'ann&eacute;e pr&eacute;c&eacute;dente et pour tenir compte de la proximit&eacute; entre les deux communaut&eacute;s, JNPC'2000 est organis&eacute; en commun avec les Journ&eacute;es Francophones de Programmation Logique et de Programmation par Contraintes (<a href="http://www.esil.univ-mrs.fr/jfplc2000">JFPLC'2000</a>). Les deux manifestations se d&eacute;rouleront donc en m&ecirc;me temps et au m&ecirc;me endroit. Pour &eacute;viter que les meilleurs travaux de la communaut&eacute; fran&ccedil;aise ne soient pr&eacute;sent&eacute;s et discut&eacute;s qu'hors de France, dans les grandes conf&eacute;rences internationales d'Intelligence Artificielle et de Recherche Op&eacute;rationnelle, le Comit&eacute; de Programme de JNPC'2000 invite tout membre de la communaut&eacute; soumettant ses travaux &agrave; une conf&eacute;rence internationale, &agrave; les soumettre parall&egrave;lement &agrave; JNPC'2000. La seule condition &agrave; cette double soumission est que l'article, si accept&eacute; &agrave; JNPC'2000, soit &eacute;crit en fran&ccedil;ais (langue officielle des journ&eacute;es) pour la version finale. <p>Enfin, une <a href="http://www.esil.univ-mrs.fr/jnpc2000/sessindus.html">session industrielle</a> aura lieu le Jeudi apr&egrave;s midi 29 Juin, en commun avec la conf&eacute;rence JFPLC'2000. Cette session sera l'occasion pour les industriels de confronter leurs exp&eacute;riences, ou de s'initier aux technologies &eacute;mergentes. <br>&nbsp; <p> <hr><a NAME="themes"></a> <h2> Th&egrave;mes</h2> Cette liste est non limitative. <br>&nbsp; <table> <tr> <td> <li> Cadres g&eacute;n&eacute;riques de repr&eacute;sentation des probl&egrave;mes</li> </td> </tr>  <tr> <td> <li> Extensions ou restrictions des cadres existants&nbsp;</li> </td> </tr>  <tr> <td> <li> Utilisation de plusieurs cadres de repr&eacute;sentation&nbsp;</li> </td> </tr>  <tr> <td> <li> Caract&eacute;risation des probl&egrave;mes (relations entre probl&egrave;mes, sous-probl&egrave;mes polynomiaux, etc)&nbsp;</li> </td> </tr>  <tr> <td> <li> M&eacute;thodes de r&eacute;solution g&eacute;n&eacute;riques ou sp&eacute;cifiques, compl&egrave;tes ou incompl&egrave;tes&nbsp;</li> </td> </tr>  <tr> <td> <li> Hybridation entre m&eacute;thodes&nbsp;</li> </td> </tr>  <tr> <td> <li> R&eacute;sultats de complexit&eacute;, th&eacute;oriques ou exp&eacute;rimentaux</li> </td> </tr>  <tr> <td> <li> Ph&eacute;nom&egrave;nes de seuil&nbsp;</li> </td> </tr>  <tr> <td> <li> Mise en oeuvre dans des contextes incertains, dynamiques, temporellement contraints, interruptibles, distribu&eacute;s, interactifs, etc&nbsp;</li> </td> </tr>  <tr> <td> <li> Applications &agrave; des probl&egrave;mes de planification, d'ordonnancement, d'affectation, de reconnaissance, de vision, de diagnostic, de conception, de synth&egrave;se, de placement, de dimensionnement, etc&nbsp;</li> </td> </tr>  <tr> <td> <li> Etudes de cas, &eacute;tudes m&eacute;thodologiques&nbsp;</li> </td> </tr>  <tr> <td> <li> Bilans d'utilisation de m&eacute;thodes ou d'outils, publics ou commerciaux</li> </td> </tr> </table>  <p> <hr><a NAME="comite"></a> <h2> Comit&eacute; de Programme</h2> <i>Pr&eacute;sident:</i> <ul>Christian Bessi&egrave;re <br>LIRMM-CNRS <br>161, rue Ada <br>34392 Montpellier Cedex 5 <br>T&eacute;l: (+33) 467 41 85 85 <br>Fax: (+33) 467 41 85 00 <br>M&eacute;l: <a href="mailto:bessiere@lirmm.fr">bessiere@lirmm.fr</a></ul> <i>Membres:</i> <br>&nbsp; <table> <tr> <td>Olivier Bailleux&nbsp;</td>  <td>CRIL, Lens&nbsp;</td> </tr>  <tr> <td>Hachemi Bennaceur</td>  <td>LIPN, Villetaneuse&nbsp;</td> </tr>  <tr> <td>Christian Bliek&nbsp;</td>  <td>ILOG, Sophia Antipolis&nbsp;</td> </tr>  <tr> <td>Philippe David&nbsp;</td>  <td>Ecole des Mines, Nantes&nbsp;</td> </tr>  <tr> <td>Romuald Debruyne&nbsp;</td>  <td>Ecole des Mines, Nantes&nbsp;</td> </tr>  <tr> <td>Simon de Givry&nbsp;</td>  <td>THOMSON-CSF, Orsay&nbsp;</td> </tr>  <tr> <td>H&eacute;l&egrave;ne Fargier&nbsp;</td>  <td>IRIT, Toulouse&nbsp;</td> </tr>  <tr> <td>Jin-Kao Hao&nbsp;</td>  <td>LERIA, Angers&nbsp;</td> </tr>  <tr> <td>Olivier Lhomme&nbsp;</td>  <td>ILOG, Sophia Antipolis&nbsp;</td> </tr>  <tr> <td>Lionel Lobjois&nbsp;</td>  <td>Atos Int&eacute;gration, Toulouse&nbsp;</td> </tr>  <tr> <td>Pierre Marquis&nbsp;</td>  <td>CRIL, Lens&nbsp;</td> </tr>  <tr> <td>Bertrand Neveu&nbsp;</td>  <td>CERMICS, Sophia Antipolis&nbsp;</td> </tr>  <tr> <td>Antoine Rauzy&nbsp;</td>  <td>LABRI, Bordeaux&nbsp;</td> </tr>  <tr> <td>Thomas Schiex&nbsp;</td>  <td>INRA, Toulouse&nbsp;</td> </tr>  <tr> <td>G&eacute;rard Verfaillie&nbsp;</td>  <td>ONERA, Toulouse&nbsp;</td> </tr> </table>  <p> <hr><a NAME="soumission"></a> <h2> Soumission</h2> Les articles soumis doivent &ecirc;tre r&eacute;dig&eacute;s en fran&ccedil;ais ou anglais. Ils ne doivent pas exc&eacute;der 12 pages dans le style article Latex ou &eacute;quivalent (c&agrave;d. simple colonne de 12,2cm de large sur 19,3cm de haut, police de 10pts. <p>Ils doivent &ecirc;tre adress&eacute;s au Pr&eacute;sident du Comit&eacute; de Programme. Les soumissions &eacute;lectroniques sont fortement encourag&eacute;es, sous forme d'un fichier PostScript standard, non compress&eacute;, &agrave; envoyer &agrave; l'adresse <a href="mailto:bessiere@lirmm.fr">bessiere@lirmm.fr</a>. Dans le cas o&ugrave; un envoi &eacute;lectronique est impossible, quatre copies de l'article doivent &ecirc;tre envoy&eacute;es par la poste, dans les m&ecirc;mes d&eacute;lais. <p>Chaque soumission doit &ecirc;tre pr&eacute;c&eacute;d&eacute;e de l'envoi par l'auteur "contact" d'un message &eacute;lectronique d'annonce de soumission indiquant le titre de l'article, les noms des auteurs, le r&eacute;sum&eacute; et les mots-cl&eacute;s les plus pertinents (en fichier texte). Une notification de r&eacute;ception sera adress&eacute;e &agrave; l'auteur contact. <p>Chaque article sera examin&eacute; par au moins deux relecteurs, appartenant ou non au Comit&eacute; de Programme. Une notification d'acceptation ou de rejet sera ensuite adress&eacute;e &agrave; l'auteur contact. <p>Pour tout article accept&eacute;, une version d&eacute;finitive r&eacute;dig&eacute;e en fran&ccedil;ais sera r&eacute;clam&eacute;e et une pr&eacute;sentation du travail devra &ecirc;tre faite lors des journ&eacute;es. <p> <hr><a NAME="invites"></a> <h2> Conf&eacute;rences invit&eacute;es</h2>  <h3> <a href="http://www-bia.inra.fr/T/schiex">Thomas Schiex</a>, INRA Toulouse</h3> <b>CSP valu&eacute;s</b> <p>Une des limitations du formalisme des r&eacute;seaux de contraintes r&eacute;side dans l'absence de prise en compte d'un crit&egrave;re &agrave; optimiser. L'introduction de <br>m&eacute;canisme d'optimisation ad-hoc dans les langages de programmation (logique) par contraintes montre bien importance de cette limitation. Plusieurs <br>formalismes, plus ou moins g&eacute;n&eacute;raux, ont &eacute;t&eacute; propos&eacute;s dans le but de combler cette lacune : r&eacute;seaux de contraintes flous, partiels, avec semi-anneau, <br>valu&eacute;s... <p>Je pr&eacute;senterai le formalisme des r&eacute;seaux de contraintes valu&eacute;s en le motivant et en le situant vis-&agrave;-vis de quelques-uns des formalismes <br>existants. La d&eacute;finition du formalisme r&eacute;sulte d'un compromis entre g&eacute;n&eacute;ralit&eacute; et sp&eacute;cificit&eacute;. La g&eacute;n&eacute;ralit&eacute; vise &agrave; couvrir le maximum <br>d'extensions existantes, la sp&eacute;cificit&eacute; vise &agrave; accumuler suffisamment de propri&eacute;t&eacute;s pour pouvoir construire des algorithmes et des propri&eacute;t&eacute;s <br>g&eacute;n&eacute;riques. Je d&eacute;taillerai donc ces propri&eacute;t&eacute;s et ferai un &eacute;tat de l'art des algorithmes qui permettent de manipuler un r&eacute;seau de contraintes valu&eacute;es en <br>illustrant l'utilisation de ces algorithmes sur diff&eacute;rents probl&egrave;mes : affectation de fr&eacute;quences, gestion d'un satellite d'observation... <br>&nbsp; <h3> <a href="http://www-lipn.univ-paris13.fr/~balbiani/">Philippe Balbiani</a>, LIPN, Paris 13</h3> <b>Repr&eacute;sentation logique et traitement algorithmique du temps et de l'espace</b> <p>Notre capacit&eacute; de raisonner sur la relativit&eacute; des positions des &eacute;v&eacute;nements qui remplissent le temps comme sur celle des moments des objets qui occupent l'espace nous est tellement n&eacute;cessaire que nous n'avons pas le droit de nous &eacute;tonner de ce que le probl&egrave;me de la repr&eacute;sentation logique et du traitement algorithmique du temps et de l'espace prenne, en informatique, une importance si grande. Par "repr&eacute;sentation logique du temps et de l'espace'' nous concevons toute logique formelle dont les mod&egrave;les sont des mod&egrave;les math&eacute;matiques du temps ou de l'espace et dans lesquels nous ne pouvons conna&icirc;tre que les relations des &eacute;l&eacute;ments qui les composent. In&eacute;vitablement, la logique classique ainsi que la logique modale conviennent mieux que tout autre logique formelle &agrave; l'&eacute;laboration d'un langage de repr&eacute;sentation logique du temps et de l'espace permettant de formuler les propri&eacute;t&eacute;s de ces relations. J'examinerai certaines des solutions que les math&eacute;matiques et la logique ont apport&eacute;es au probl&egrave;me de l'analyse logique de notre perception du temps et de l'espace. En &eacute;crivant "traitement algorithmique du temps et de l'espace'' nous pensons &agrave; toute m&eacute;thode de d&eacute;cision capable d'imaginer en un temps raisonnable la d&eacute;monstration d'un certain nombre de th&eacute;or&egrave;mes parmi les th&eacute;or&egrave;mes des logiques formelles dont nous venons de parler. Je pr&eacute;senterai les points de vue de la d&eacute;duction automatique et de la satisfaction de contraintes sous lesquels le probl&egrave;me de la m&eacute;canisation du raisonnement sur le temps et sur l'espace a &eacute;t&eacute; abord&eacute;. <br> <hr><a NAME="calendrier"></a> <h2> Calendrier</h2>  <table> <tr> <td>Le plus t&ocirc;t possible avant le 15 Mars</td>  <td>Date limite de r&eacute;ception des messages d'annonce de soumission</td> </tr>  <tr> <td>Mercredi 15 Mars 2000&nbsp;</td>  <td>Date limite de r&eacute;ception des articles soumis&nbsp;</td> </tr>  <tr> <td>Lundi 17 Avril 2000&nbsp;</td>  <td>Notification d'acceptation ou de rejet &agrave; l'auteur contact&nbsp;</td> </tr>  <tr> <td>Jeudi 4 Mai 2000&nbsp;</td>  <td>Date limite de r&eacute;ception des versions d&eacute;finitives&nbsp;</td> </tr>  <tr> <td>Mercredi 28 - Vendredi 30 Juin 2000&nbsp;</td>  <td>Pr&eacute;sentations &agrave; JNPC'00&nbsp;</td> </tr> </table>  <p> <hr><a NAME="organisation"></a> <h2> <b><font size=+2>Comit&eacute; d' Organisation</font></b></h2> <i>Responsable:</i> <p>Laurent Henocque <br>Ecole Superieure d'Ingenieurs de Luminy, Departement ES2I <br>Luminy  Case 925 - 13288 Marseille Cedex 09 <br>tel :91 82 85 16 / fax 91 82 85 11 <br>Mel:<a href="mailto:henocque@esil.univ-mrs.fr">henocque@esil.univ-mrs.fr</a> <p><i>Membres:</i> <br>&nbsp; <table> <tr> <td HEIGHT="1%">Belaid Benhamou</td>  <td>LIM, Universit&eacute; de Provence</td> </tr>  <tr> <td>Philippe Jegou</td>  <td>LIM, Universit&eacute; d'Aix-Marseille III</td> </tr>  <tr> <td>&nbsp;</td>  <td>&nbsp;</td> </tr> </table>  <ul>&nbsp;</ul>  </body> </html> 
