{"id":3045,"date":"2016-09-06T12:34:25","date_gmt":"2016-09-06T11:34:25","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=3045"},"modified":"2022-12-03T22:59:01","modified_gmt":"2022-12-03T21:59:01","slug":"generation-de-colonnes","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/generation-of-columns\/","title":{"rendered":"Column generation"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"3045\" class=\"elementor elementor-3045\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-902ec7b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"902ec7b\" 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-170734f\" data-id=\"170734f\" 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-1abb46c elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1abb46c\" 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-5648710\" data-id=\"5648710\" 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-50176df elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"50176df\" 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-e72a08d\" data-id=\"e72a08d\" 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-58524a7 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"58524a7\" 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\/G%C3%A9n%C3%A9ration_de_colonnes\" 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-4e8c9e60 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"4e8c9e60\" 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-4bd99c3e\" data-id=\"4bd99c3e\" 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-33701a01 elementor-widget elementor-widget-text-editor\" data-id=\"33701a01\" 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' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/generation-of-columns\/#Generation-de-colonnes\" >Column generation<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Generation-de-colonnes\"><\/span>Column generation<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>When a <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/\">linear program<\/a> has a lot of variables, it is not possible to solve it by a <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">simplex<\/a>. The generation of columns makes it possible to generate the useful variables progressively until an optimal solution is obtained. The objective of this method is to solve a reduced problem with a limited set of variables.<\/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 initial problem of a generation of columns is called the master problem, and the reduced problem is called the restricted problem.<\/div>\n\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">The restricted problem of a generation of columns is simpler to solve, but if the set of its variables does not contain those which give the optimal solution for the master problem, to reach the optimal solution of the master problem, it is necessary to add to the problem restricted to variables that can be used to improve the solution.<\/div>\n\n<p>The problem consisting in finding the best variable to add in the restricted problem is called sub-problem associated with the master problem (or oracle). Its objective is to find the variable (or column) of minimum reduced cost (ie the most promising to improve the solution).<\/p>\n\n<p>The reduced cost of the variables is calculated using the dual variables obtained after solving the restricted problem. The point of the dual thus used in the sub-problem is called the point of separation. Often this is an optimal solution of the dual of the restricted problem.<\/p>\n\n<p>We consider the following continuous linear program (LP):<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4736 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/09\/gencolonne1.png\" alt=\"Column generation\" width=\"301\" height=\"75\" title=\"\"><\/figure>\n<\/div>\n\n<p>We assume that the number of variables in T is too large for the problem (LP) to be solved in reasonable time, and that we want to solve it by generating columns. We therefore seek to solve the restricted problem associated with the master problem with a restricted set of variables denoted by R<sub>the<\/sub>. The restricted problem must be feasible. It is possible to use simple columns, for example random columns, or even those resulting from a feasible solution obtained from a <a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/\">heuristic<\/a>.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4744 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/09\/gencolonne2.png\" alt=\"Column generation\" width=\"301\" height=\"80\" title=\"\"><\/figure>\n<\/div>\n\n<p>The problem (RLP) is now small and will be easier to solve by a solver. This resolution will provide us with the optimal values of the dual variables v<sub>j<\/sub> associated with constraints. These values are passed to the sub-problem which allows us to obtain the column (s) to add to the set R<sub>the<\/sub>.<\/p>\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-4750 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/09\/gencolonne3.png\" alt=\"Column generation\" width=\"160\" height=\"75\" title=\"\"><\/figure>\n<\/div>\n\n<p>The calculation of the reduced cost allows us to know if a column decreased the value of the objective (and therefore improved it).<\/p>\n\n<p>Since (LP) is a problem of <a href=\"https:\/\/complex-systems-ai.com\/en\/language-theory\/minimization-dun-afd\/\">minimization<\/a>, the subproblem also seeks to minimize this reduced cost. If the minimum reduced cost is positive, then no columns can be added to the restricted problem (RLP) to improve the objective. The optimal solution of the restricted problem is therefore an optimal solution of the master problem (LP). Otherwise, we add one or more columns among those having a negative reduced cost by updating the set R<sub>the<\/sub> and we solve after the new restricted problem (RLP).<\/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 Home page Wiki Generation of columns When a linear program has many variables, it is not possible to solve it by a simplex. \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-3045","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3045","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=3045"}],"version-history":[{"count":4,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3045\/revisions"}],"predecessor-version":[{"id":17901,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/3045\/revisions\/17901"}],"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=3045"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}