{"id":4255,"date":"2016-10-26T10:30:03","date_gmt":"2016-10-26T09:30:03","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=4255"},"modified":"2022-12-03T23:00:11","modified_gmt":"2022-12-03T22:00:11","slug":"programmation-par-contraintes-2","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/constraint-programming-2\/","title":{"rendered":"Constraint programming"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"4255\" class=\"elementor elementor-4255\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-1237a89 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"1237a89\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-71e60e9\" data-id=\"71e60e9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-482af51 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"482af51\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Combinatorial optimization<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-10fe52f\" data-id=\"10fe52f\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-b1073ea elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"b1073ea\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-1353f05\" data-id=\"1353f05\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-f08e62f elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"f08e62f\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Programmation_par_contraintes\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-2510f318 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"2510f318\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-18b26da2\" data-id=\"18b26da2\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-61f25901 elementor-widget elementor-widget-text-editor\" data-id=\"61f25901\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/constraint-programming-2\/#Programmation-par-contraintes\" >Constraint programming<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/constraint-programming-2\/#Definition\" >Definition<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/constraint-programming-2\/#Resolution-naive-Generate-Test\" >Naive resolution: Generate &amp; Test<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/constraint-programming-2\/#Resolution-par-backtrack\" >Backtrack resolution<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-1'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/constraint-programming-2\/#Resolution-par-propagation-de-contraintes\" >Resolution by stress propagation<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Programmation-par-contraintes\"><\/span>Constraint programming<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>The <a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/constraint-programming\/\">constraint programming<\/a> solves decision-making problems. An optimization problem is solved successively after several decision problems. For example to determine a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-path-search\/\">shortest way<\/a>, we will seek to find a path of less than 100 (possible), then less than 50 (impossible), then less than 75, etc. until the optimal solution is found. PPC has a broader field of action than exact methods or metaheuristics.<\/p>\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Definition\"><\/span>Definition<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n<p>PPC solves a constraint satisfaction problem (CSP).<\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">The latter is defined by a triplet with X the set of variables, D the set of domains and C the set of constraints. Domaine D<sub>i<\/sub> is the set of possible values for the variable X<sub>i<\/sub>. Each constraints C<sub>j<\/sub> is defined by its arity (the number of variables on which it relates), the list of these variables and the set of tuples which satisfy it.<\/div>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<p>Let&#039;s take an example of a triplet:<\/p>\n<ul style=\"text-align: justify;\">\n<li>variables: A, B, C, D<\/li>\n<li>areas :\n<ul>\n<li>D<sub>TO<\/sub> = {1,4,5,8}<\/li>\n<li>D<sub>B<\/sub> = {2,3,5,7,9}<\/li>\n<li>D<sub>VS<\/sub> = {4,8,9}<\/li>\n<li>D<sub>D<\/sub> = {1,4,5,7,9}<\/li>\n<\/ul>\n<\/li>\n<li>constraints:\n<ul>\n<li>VS<sub>1<\/sub>(A, C): {(1.7); (1.9); (5.9); (8.9)}<\/li>\n<li>VS<sub>2<\/sub>(A, D): (1.1); (1.5); (5.5); (5.9); (8.9)}<\/li>\n<li>VS<sub>3<\/sub>(C, D): {(4.1); (8.1); (9.7)}<\/li>\n<li>VS<sub>4<\/sub>(B, D): {(2.7); (2.9); (5.8); (7.9); (9.9)}<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n\n<p>It is possible to code the constraints in extension, by a set of tuples, or in intention, using operators whose semantics are known. An instantiation is a complete assignment of values to variables, for example {<a> ,<b> , , }. Instantiation is a valid solution if the values given to the variables of which such as all the constraints are verified.<\/p>\n\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">We speak of partial or total instantiation (whether it takes all the variables or not), and inconsistent or consistent (whether it validates the constraints or not). A valid solution is therefore a total and consistent instantiation.<\/div>\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Resolution-naive-Generate-Test\"><\/span>Naive resolution: Generate &amp; Test<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">We generate all the possible assignments. Then we check if they are consistent, as soon as an assignment is consistent we have a valid solution.<\/div>\n\n<p>If we have a problem with n variables, each can only take two values, the processor does 1,000,000,000 calculations per second. For 30 variables, the resolution take at most 1s, for 50 variables, we go to 11 days; for 70 variables it is necessary to wait 317 centuries.<\/p>\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Resolution-par-backtrack\"><\/span>Backtrack resolution<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">We generate the assignment tree and then <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/traversal-of-graphs\/\">in-depth journey<\/a>. If a partial assignment (during the traversal) is inconsistent, then the corresponding subtree is cut.<\/div>\n\n<p>It is akin to Branch &amp; Cut.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-5084 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc1.png\" alt=\"backtrack constraint programming\" width=\"682\" height=\"435\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc1.png 682w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc1-300x191.png 300w\" sizes=\"(max-width: 682px) 100vw, 682px\" \/><\/figure>\n<\/div>\n\n<p>This method does not generate the entire possibility tree unlike the naive method. On the other hand all the constraints are tested with each partial assignment and the convergence time also depends on the order of the variables.<\/p>\n\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Resolution-par-propagation-de-contraintes\"><\/span>Resolution by stress propagation<span class=\"ez-toc-section-end\"><\/span><\/h1>\n\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">This method consists in propagating the constraints in the domain of the variables.<\/div>\n\n<p>For example let us take x between 0 and 10 and y between 3 and 9; then with the constraint x&gt; y we can restrict the domain of X between 4 and 10.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"aligncenter wp-image-5093 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc2.png\" alt=\"constraint programming propagation\" width=\"490\" height=\"326\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc2.png 490w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc2-300x200.png 300w\" sizes=\"(max-width: 490px) 100vw, 490px\" \/><\/figure>\n<\/div>\n\n<p>There are three cases where information is propagated:<\/p>\n\n<ul class=\"wp-block-list\">\n<li>when a domain is reduced<\/li>\n<li>when one of the domain terminals is changed<\/li>\n<li>when a domain is a singleton.<\/li>\n<\/ul>\n\n<p>It is then possible to propagate the information once (node-consistency), twice (arc-consistency) or more.<\/p>\n\n<p>In the node-consistency, for each variable X<sub>i<\/sub> unaffected in A, we subtract from D<sub>Xi<\/sub> any value v such that the assignment A \u222a {(X<sub>i<\/sub>, v)} is inconsistent. The authorized values are propagated in depth.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"aligncenter wp-image-5104 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc3.png\" alt=\"constraint programming propagation\" width=\"502\" height=\"327\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc3.png 502w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc3-300x195.png 300w\" sizes=\"(max-width: 502px) 100vw, 502px\" \/><\/figure>\n<\/div>\n\n<p>In the arc-consistency, for each variable X<sub>i<\/sub> unaffected in A, we subtract from D<sub>Xi<\/sub> any value v such that there is a variable X<sub>j<\/sub> unassigned for which, for any value w of D<sub>Xj<\/sub>, the assignment A \u222a {(X<sub>i<\/sub>, v); (X<sub>j<\/sub>, w)} is inconsistent. The authorized values are propagated in depth.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-5112 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc4-300x142.png\" alt=\"constraint programming propagation\" width=\"300\" height=\"142\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc4-300x142.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/10\/ppc4.png 760w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/figure>\n<\/div>\n\n<p>The larger the comparison tuple, the greater the computation time to define the valid domain of the variables. Arc-consistency is less efficient than knot-consistency if the domains are large.<\/p>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Combinatorial optimization Wiki homepage Constraint programming Constraint programming is used to solve decision-making problems. An optimization problem is solved successively after \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":1770,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-4255","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4255","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=4255"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4255\/revisions"}],"predecessor-version":[{"id":16644,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/4255\/revisions\/16644"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1770"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=4255"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}