{"id":1770,"date":"2016-10-27T17:01:28","date_gmt":"2016-10-27T16:01:28","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=1770"},"modified":"2024-02-11T19:49:16","modified_gmt":"2024-02-11T18:49:16","slug":"optimisation-combinatoire","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/","title":{"rendered":"Combinatorial Optimization 101"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"1770\" class=\"elementor elementor-1770\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-af7b5e0 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"af7b5e0\" 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-aef2227\" data-id=\"aef2227\" 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-a9aa898 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a9aa898\" 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\/2020\/04\/03\/theories-and-algorithms-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\">Theories<\/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-240d7c7\" data-id=\"240d7c7\" 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-46b18bf elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"46b18bf\" 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-fa1b870\" data-id=\"fa1b870\" 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-673dfcd elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"673dfcd\" 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\/Optimisation_combinatoire\" 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-5fd9688 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5fd9688\" 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-d3b2db5\" data-id=\"d3b2db5\" 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-9724ce3 elementor-widget elementor-widget-toggle\" data-id=\"9724ce3\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"toggle.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle\">\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1581\" class=\"elementor-tab-title\" data-tab=\"1\" role=\"button\" aria-controls=\"elementor-tab-content-1581\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">I. Exact methods (combinatorial optimization)<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1581\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"1\" role=\"region\" aria-labelledby=\"elementor-tab-title-1581\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/cutting-plane\/\">Cutting-plane<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/branch-and-bound\/\">Branch &amp; bound<\/a><\/li>\n<li>Branch &amp; cut<\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/dynamic-programming\/\">Dynamic programming<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/constraint-programming\/\">Constraint programming<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/constraint-programming-2\/\">Constraint programming, Solving methods<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/generation-of-columns\/\">Column generation<\/a><\/li>\n<li>Branch and price<\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1582\" class=\"elementor-tab-title\" data-tab=\"2\" role=\"button\" aria-controls=\"elementor-tab-content-1582\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">II. Accuracy criteria<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1582\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"2\" role=\"region\" aria-labelledby=\"elementor-tab-title-1582\"><ul>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/No_free_lunch_in_search_and_optimization\" target=\"_blank\" rel=\"noopener\">No-Free-Lunch Theorem<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/heuristic-evaluation\/\">Heuristics evaluation<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1583\" class=\"elementor-tab-title\" data-tab=\"3\" role=\"button\" aria-controls=\"elementor-tab-content-1583\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">III. Heuristics and metaheuristics<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1583\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"3\" role=\"region\" aria-labelledby=\"elementor-tab-title-1583\"><ul>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/stochastic-algorithms-2\/\" target=\"_blank\" rel=\"noreferrer noopener\">Stochastic algorithms<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithms-devolution-2\/\" target=\"_blank\" rel=\"noreferrer noopener\">Evolution algorithms<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/physics-based-algorithms\/\">Physical algorithms<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/probabilistic-algorithms-2\/\">Probabilistic algorithms<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/algorithms-desaims\/\">Swarm algorithms<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/immune-algorithm\/\">Immune algorithms<\/a><\/li>\n<li><a href=\"https:\/\/complex-systems-ai.com\/en\/neural-algorithms-2\/\">Neural algorithms<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1584\" class=\"elementor-tab-title\" data-tab=\"4\" role=\"button\" aria-controls=\"elementor-tab-content-1584\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">IV. Nonlinear optimization without constraints<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1584\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"4\" role=\"region\" aria-labelledby=\"elementor-tab-title-1584\"><ul>\n<li><a title=\"Golden-section search\" href=\"https:\/\/en.wikipedia.org\/wiki\/Golden-section_search\" target=\"_blank\" rel=\"noopener\">Golden-section search<\/a><\/li>\n<li><a title=\"Powell&#039;s method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Powell%27s_method\" target=\"_blank\" rel=\"noopener\">Interpolation methods<\/a><\/li>\n<li><a title=\"line search\" href=\"https:\/\/en.wikipedia.org\/wiki\/Line_search\" target=\"_blank\" rel=\"noopener\">line search<\/a><\/li>\n<li><a title=\"Nelder\u2013Mead method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Nelder%E2%80%93Mead_method\" target=\"_blank\" rel=\"noopener\">Nelder\u2013Mead method<\/a><\/li>\n<li><a title=\"Successive parabolic interpolation\" href=\"https:\/\/en.wikipedia.org\/wiki\/Successive_parabolic_interpolation\" target=\"_blank\" rel=\"noopener\">Successive parabolic interpolation<\/a><\/li>\n<li><a title=\"Trust region\" href=\"https:\/\/en.wikipedia.org\/wiki\/Trust_region\" target=\"_blank\" rel=\"noopener\">Trust region<\/a><\/li>\n<li><a title=\"Terms and Conditions\" href=\"https:\/\/en.wikipedia.org\/wiki\/Wolfe_conditions\" target=\"_blank\" rel=\"noopener\">Terms and Conditions<\/a><\/li>\n<li><a title=\"Berndt\u2013Hall\u2013Hall\u2013Hausman algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Berndt%E2%80%93Hall%E2%80%93Hall%E2%80%93Hausman_algorithm\" target=\"_blank\" rel=\"noopener\">Berndt\u2013Hall\u2013Hall\u2013Hausman<\/a><\/li>\n<li><a title=\"Broyden\u2013Fletcher\u2013Goldfarb\u2013Shanno algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Broyden%E2%80%93Fletcher%E2%80%93Goldfarb%E2%80%93Shanno_algorithm\" target=\"_blank\" rel=\"noopener\">Broyden\u2013Fletcher\u2013Goldfarb\u2013Shanno<\/a>\u00a0and\u00a0<a title=\"Limited-memory BFGS\" href=\"https:\/\/en.wikipedia.org\/wiki\/Limited-memory_BFGS\" target=\"_blank\" rel=\"noopener\">L-BFGS<\/a><\/li>\n<li><a title=\"Davidon\u2013Fletcher\u2013Powell formula\" href=\"https:\/\/en.wikipedia.org\/wiki\/Davidon%E2%80%93Fletcher%E2%80%93Powell_formula\" target=\"_blank\" rel=\"noopener\">Davidon\u2013Fletcher\u2013Powell<\/a><\/li>\n<li><a title=\"Symmetric rank-one\" href=\"https:\/\/en.wikipedia.org\/wiki\/Symmetric_rank-one\" target=\"_blank\" rel=\"noopener\">Symmetric rank-one (SR1)<\/a><\/li>\n<li><a title=\"Nonlinear conjugate gradient method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Nonlinear_conjugate_gradient_method\" target=\"_blank\" rel=\"noopener\">Gradient conjugate<\/a><\/li>\n<li><a title=\"Gauss\u2013Newton algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Gauss%E2%80%93Newton_algorithm\" target=\"_blank\" rel=\"noopener\">Gauss\u2013Newton<\/a><\/li>\n<li><a title=\"Gradient descent\" href=\"https:\/\/en.wikipedia.org\/wiki\/Gradient_descent\" target=\"_blank\" rel=\"noopener\">gradient<\/a><\/li>\n<li><a title=\"mirror descent\" href=\"https:\/\/en.wikipedia.org\/wiki\/Mirror_descent\" target=\"_blank\" rel=\"noopener\">Mirror<\/a><\/li>\n<li><a title=\"Levenberg\u2013Marquardt algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Levenberg%E2%80%93Marquardt_algorithm\" target=\"_blank\" rel=\"noopener\">Levenberg\u2013Marquardt<\/a><\/li>\n<li><a title=\"Powell&#039;s dog leg method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Powell%27s_dog_leg_method\" target=\"_blank\" rel=\"noopener\">Powell&#039;s dog leg method<\/a><\/li>\n<li><a title=\"Truncated Newton method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Truncated_Newton_method\" target=\"_blank\" rel=\"noopener\">Truncated Newton<\/a><\/li>\n<li><a title=\"Newton&#039;s method in optimization\" href=\"https:\/\/en.wikipedia.org\/wiki\/Newton%27s_method_in_optimization\" target=\"_blank\" rel=\"noopener\">Newton&#039;s method<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1585\" class=\"elementor-tab-title\" data-tab=\"5\" role=\"button\" aria-controls=\"elementor-tab-content-1585\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">V. Nonlinear optimization with constraints<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1585\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"5\" role=\"region\" aria-labelledby=\"elementor-tab-title-1585\"><ul>\n<li><a title=\"Barrier function\" href=\"https:\/\/en.wikipedia.org\/wiki\/Barrier_function\" target=\"_blank\" rel=\"noopener\">Barrier methods<\/a><\/li>\n<li><a title=\"Penalty method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Penalty_method\" target=\"_blank\" rel=\"noopener\">Penalty methods<\/a><\/li>\n<li><a title=\"Augmented Lagrangian method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Augmented_Lagrangian_method\" target=\"_blank\" rel=\"noopener\">Augmented Lagrangian methods<\/a><\/li>\n<li><a title=\"Sequential quadratic programming\" href=\"https:\/\/en.wikipedia.org\/wiki\/Sequential_quadratic_programming\" target=\"_blank\" rel=\"noopener\">Sequential quadratic programming<\/a><\/li>\n<li><a title=\"Successive linear programming\" href=\"https:\/\/en.wikipedia.org\/wiki\/Successive_linear_programming\" target=\"_blank\" rel=\"noopener\">Successive linear programming<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t<div class=\"elementor-toggle-item\">\n\t\t\t\t\t<div id=\"elementor-tab-title-1586\" class=\"elementor-tab-title\" data-tab=\"6\" role=\"button\" aria-controls=\"elementor-tab-content-1586\" aria-expanded=\"false\">\n\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon elementor-toggle-icon-left\" aria-hidden=\"true\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-closed\"><i class=\"fas fa-caret-right\"><\/i><\/span>\n\t\t\t\t\t\t\t\t<span class=\"elementor-toggle-icon-opened\"><i class=\"elementor-toggle-icon-opened fas fa-caret-up\"><\/i><\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t\t<\/span>\n\t\t\t\t\t\t\t\t\t\t\t\t<a class=\"elementor-toggle-title\" tabindex=\"0\">VI. Convex optimization<\/a>\n\t\t\t\t\t<\/div>\n\n\t\t\t\t\t<div id=\"elementor-tab-content-1586\" class=\"elementor-tab-content elementor-clearfix\" data-tab=\"6\" role=\"region\" aria-labelledby=\"elementor-tab-title-1586\"><ul>\n<li><a title=\"Cutting-plane method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Cutting-plane_method\" target=\"_blank\" rel=\"noopener\">Cutting-plane method<\/a><\/li>\n<li><a title=\"Frank\u2013Wolfe algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Frank%E2%80%93Wolfe_algorithm\" target=\"_blank\" rel=\"noopener\">Reduced gradient (Frank\u2013Wolfe)<\/a><\/li>\n<li><a title=\"Subgradient method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Subgradient_method\" target=\"_blank\" rel=\"noopener\">Subgradient method<\/a><\/li>\n<li><a title=\"Affine scaling\" href=\"https:\/\/en.wikipedia.org\/wiki\/Affine_scaling\" target=\"_blank\" rel=\"noopener\">Affine scaling<\/a><\/li>\n<li><a title=\"Ellipsoid method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Ellipsoid_method\" target=\"_blank\" rel=\"noopener\">Ellipsoid algorithm of Khachiyan<\/a><\/li>\n<li><a title=\"Karmarkar&#039;s algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Karmarkar%27s_algorithm\" target=\"_blank\" rel=\"noopener\">Projective algorithm of Karmarkar<\/a><\/li>\n<li><a title=\"Simplex algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Simplex_algorithm\" target=\"_blank\" rel=\"noopener\">Simplex algorithm of Danzig<\/a><\/li>\n<li><a title=\"Revised simplex method\" href=\"https:\/\/en.wikipedia.org\/wiki\/Revised_simplex_method\" target=\"_blank\" rel=\"noopener\">Revised simplex algorithm<\/a><\/li>\n<li><a title=\"Criss-cross algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Criss-cross_algorithm\" target=\"_blank\" rel=\"noopener\">Criss-cross algorithm<\/a><\/li>\n<li><a title=\"Lemke&#039;s algorithm\" href=\"https:\/\/en.wikipedia.org\/wiki\/Lemke%27s_algorithm\" target=\"_blank\" rel=\"noopener\">Main pivoting algorithm of Lemke<\/a><\/li>\n<\/ul><\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\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-58fc4764 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"58fc4764\" 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-2f81a4fa\" data-id=\"2f81a4fa\" 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-43400546 elementor-widget elementor-widget-text-editor\" data-id=\"43400546\" 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_84 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\/#Optimisation-combinatoire\" >Combinatorial optimization<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/#Arbre-des-solutions\" >Solution tree<\/a><\/li><\/ul><\/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\/#Techniques-de-resolution\" >Solving techniques<\/a><ul class='ez-toc-list-level-2' ><li class='ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/#Exacte\" >Exact<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/#Heuristique\" >Heuristic<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/complex-systems-ai.com\/en\/combinatorial-optimization-2\/#Meta-heuristique\" >Meta-heuristic<\/a><\/li><\/ul><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Optimisation-combinatoire\"><\/span>Combinatorial optimization<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">THE&#039;<b>combinatorial optimization<\/b>, also called <b>discrete optimization<\/b>, is a branch of optimization in applied mathematics and computer science, also related to operations research, algorithms and complexity theory. Combinatorial optimization consists in finding in a set a subset containing the \u201cbest solutions\u201d.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Finding an optimal solution in a discrete and finite set is an easy problem in theory: you just have to try all the solutions, and compare their qualities to see the best. However, the combinatorial explosion of possible solutions of certain mathematical problems does not make it possible to obtain a solution in a &quot;human&quot; time.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Some combinatorial optimization problems can be solved (exactly) in polynomial time, for example by a <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/\">algorithm<\/a> dynamic programming or by showing that the problem can be formulated as a linear optimization problem in real variables. In most cases, the problem is Np-hard and, to solve it, suitable algorithms must be used.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">In practice, the physically acceptable complexity is often only polynomial. We are then satisfied with having a solution approximated at best, obtained by a heuristic or a meta-heuristic. It is important to note that some of these methods provide global optimals, the difference with the exact methods is the fact of not having a formal proof (mathematical or finality proof) of its global optimality.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-1812 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/combi.png\" alt=\"combinatorial optimization technique\" width=\"618\" height=\"301\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/combi.png 618w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/combi-300x146.png 300w\" sizes=\"(max-width: 618px) 100vw, 618px\" \/><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Arbre-des-solutions\"><\/span>Solution tree<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">That is <strong>E<\/strong> all the solutions to the problems. It is assumed to be discrete and finite. The enumeration of solutions is represented by <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/\">tree<\/a>. All elements of <strong>E<\/strong> are separated into <strong>not<\/strong> disjoint nonempty subset each containing a part of the set of solutions. For example, the set can be split into two in the backpack problem whether or not we take an element x<sub>k<\/sub> in the bag.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">The operation can be repeated for each subset until each set contains only one element. For the backpack example, each sub-assembly is separated until a decision is reached on the last element.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">The root of the tree is <strong>E<\/strong>, the wires are the sub-assemblies etc. as shown in the following diagram:<\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"aligncenter wp-image-2095 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/enumeration.png\" alt=\"enumeration optimization\" width=\"785\" height=\"230\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/enumeration.png 785w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/enumeration-300x88.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/enumeration-768x225.png 768w\" sizes=\"(max-width: 785px) 100vw, 785px\" \/><\/figure>\n<p><\/p>\n<h1 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Techniques-de-resolution\"><\/span>Solving techniques<span class=\"ez-toc-section-end\"><\/span><\/h1>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Exacte\"><\/span>Exact<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">These methods give a guarantee to find the optimal solution for an instance of finite size in a limited time and to prove its optimality.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Heuristique\"><\/span>Heuristic<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">When the complexity of a problem is exponential or presents a combinatorial explosion, the use of heuristics is recommended. This is a method that quickly provides a &quot;good&quot; solution to the problem. This approximate solution can then provide a starting point for using an exact method (such as the Northwest corner for the transport problem). All greedy and naive algorithms are heuristics.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">It should be noted that heuristics are built to solve a given problem, and cannot be used in other conditions unlike meta-heuristics. Heuristics are evaluated according to three criteria:<\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li>Quality of the result: the heuristic is confronted with the optimal results for a set of values of the given problem (we speak of benchmark). The quality of the solution can either be a distance to the optimal solution, or a probability of reaching it.<\/li>\n<li>Cost of heuristics: complexity in time and space.<\/li>\n<li>Field of application: the field of admissibility of all the variables.<\/li>\n<\/ol>\n<p><\/p>\n<p class=\"wp-block-paragraph\">The heuristics for a given problem are numerous, so it is important to provide a fast one and provide &quot;good&quot; results.<\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Meta-heuristique\"><\/span>Meta-heuristic<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Meta-heuristics have a higher level of abstraction than heuristics since it is a method that can adapt to a given problem. Thus, the methods can be applied to various problems (in the form of a black box) without modifying their operation. We also speak of generalist heuristics.<\/p>\n<p><\/p>\n<p class=\"wp-block-paragraph\">There are two kinds of meta-heuristics: population <em>(To)<\/em> or course <em>(b)<\/em>. Most algorithms do not have a determined population, so it is possible to use the algorithm for a route or a population.<\/p>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" class=\"aligncenter wp-image-1856 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/metaheuristic_parcours-population.png\" alt=\"population path metaheuristic\" width=\"640\" height=\"480\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/metaheuristic_parcours-population.png 640w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/metaheuristic_parcours-population-300x225.png 300w\" sizes=\"(max-width: 640px) 100vw, 640px\" \/><\/figure>\n<p><\/p>\n<p class=\"wp-block-paragraph\">Both kinds work with the same four-step process:<\/p>\n<p><\/p>\n<ol class=\"wp-block-list\">\n<li><em>Neighborhood <\/em>: the neighborhood of a solution is a subset of solutions that can be reached by a transformation of the initial solution (by permutation, by extension, by mutation, by ejection, etc.).<\/li>\n<li><em>Exploration<\/em> : exploration consists of collecting data on the entire neighborhood.<\/li>\n<li><em>Operation<\/em> : the operation uses the information collected to define the \u201cinteresting\u201d areas of the research area formed by the neighborhood.<\/li>\n<li><em>Memory<\/em> : the memory takes learning into account and makes it possible to determine the zones likely to have a global optimum. If the new solutions or the stopping criteria no longer allow the solution to be improved, the algorithm stops. Otherwise, return to step 1. Certain algorithms only work with stopping criteria, so we are talking about memoryless meta-heuristics.<\/li>\n<\/ol>\n<p><\/p>\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-1836 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/meta.png\" alt=\"optimization algorithm\" width=\"649\" height=\"591\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/meta.png 649w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/meta-300x273.png 300w\" sizes=\"(max-width: 649px) 100vw, 649px\" \/><\/figure>\n<p><\/p>\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>Theories Home page Wiki I. Exact methods (combinatorial optimization) Cutting-plane Branch &amp; bound Branch &amp; cut Dynamic programming Constraint programming Constraint programming, Methods \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1770","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1770","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=1770"}],"version-history":[{"count":32,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1770\/revisions"}],"predecessor-version":[{"id":20400,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/1770\/revisions\/20400"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=1770"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}