{"id":10886,"date":"2020-11-11T10:35:41","date_gmt":"2020-11-11T09:35:41","guid":{"rendered":"https:\/\/complex-systems-ai.com\/?page_id=10886"},"modified":"2022-12-03T23:05:37","modified_gmt":"2022-12-03T22:05:37","slug":"projet-programmation-lineaire-the-truman-show","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/linear-programming-project-the-truman-show\/","title":{"rendered":"Linear Programming Project: The Truman Show"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"10886\" class=\"elementor elementor-10886\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-b44475a elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"b44475a\" 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-5a2e5ef\" data-id=\"5a2e5ef\" 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-296df28 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"296df28\" 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\/linear-programming-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\">Linear programming<\/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-99a30dd\" data-id=\"99a30dd\" 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-115a920 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"115a920\" 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-ba6d1ab\" data-id=\"ba6d1ab\" 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-a25fef6 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"a25fef6\" 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\/S%C3%A9paration_et_%C3%A9valuation\" 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-e9f3308 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"e9f3308\" 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-ad5a9e4\" data-id=\"ad5a9e4\" 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-810f53a elementor-widget elementor-widget-heading\" data-id=\"810f53a\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_83 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\/linear-programming-2\/linear-programming-project-the-truman-show\/#Projet-sur-la-programmation-lineaire-The-Truman-Show\" >Linear Programming Project: The Truman Show<\/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\/linear-programming-2\/linear-programming-project-the-truman-show\/#Debut-du-projet\" >Beginning of the project<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/linear-programming-project-the-truman-show\/#Notation\" >Rating<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Projet-sur-la-programmation-lineaire-The-Truman-Show\"><\/span>Linear Programming Project: The Truman Show<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-863836c elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"863836c\" 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-1f313f8\" data-id=\"1f313f8\" 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-f2851fb elementor-widget elementor-widget-text-editor\" data-id=\"f2851fb\" 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<p>This project requires knowledge of <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/\">linear programming<\/a> and combinatorial optimization algorithms, including Branch &amp; Bound.<\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-0ac2167 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0ac2167\" 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-f2e309e\" data-id=\"f2e309e\" 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-92a89c2 elementor-widget-divider--separator-type-pattern elementor-widget-divider--view-line elementor-widget elementor-widget-divider\" data-id=\"92a89c2\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"divider.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t<div class=\"elementor-divider\" style=\"--divider-pattern-url: url(&quot;data:image\/svg+xml,%3Csvg xmlns=&#039;http:\/\/www.w3.org\/2000\/svg&#039; preserveAspectRatio=&#039;none&#039; overflow=&#039;visible&#039; height=&#039;100%&#039; viewBox=&#039;0 0 20 16&#039; fill=&#039;none&#039; stroke=&#039;black&#039; stroke-width=&#039;1&#039; stroke-linecap=&#039;square&#039; stroke-miterlimit=&#039;10&#039;%3E%3Cg transform=&#039;translate(-12.000000, 0)&#039;%3E%3Cpath d=&#039;M28,0L10,18&#039;\/%3E%3Cpath d=&#039;M18,0L0,18&#039;\/%3E%3Cpath d=&#039;M48,0L30,18&#039;\/%3E%3Cpath d=&#039;M38,0L20,18&#039;\/%3E%3C\/g%3E%3C\/svg%3E&quot;);\">\n\t\t\t<span class=\"elementor-divider-separator\">\n\t\t\t\t\t\t<\/span>\n\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-936ae39 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"936ae39\" 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-15b0c18\" data-id=\"15b0c18\" 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-3d766bf elementor-widget elementor-widget-text-editor\" data-id=\"3d766bf\" 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<p><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-10900 size-large\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8-1-1024x576.png\" alt=\"project linear programming combinatorial optimization branch and bound\" width=\"1024\" height=\"576\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8-1-1024x576.png 1024w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8-1-300x169.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8-1-768x432.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8-1-1000x562.png 1000w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image8-1.png 1385w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/p><p><strong><b>\u201cWe&#039;ve become bored with watching actors give us phony emotions. We are tired of pyrotechnics and special effects. While the world he inhabits is, in some respects, counterfeit, there&#039;s nothing fake about Truman himself. No scripts, no cue cards. It isn&#039;t always Shakespeare, but it&#039;s genuine. It&#039;s a life. \u201d<\/b><\/strong><\/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<section class=\"elementor-section elementor-top-section elementor-element elementor-element-aca0d33 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"aca0d33\" 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-00ff1bb\" data-id=\"00ff1bb\" 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-b4d67b0 elementor-widget elementor-widget-heading\" data-id=\"b4d67b0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"heading.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t<h2 class=\"elementor-heading-title elementor-size-default\"><span class=\"ez-toc-section\" id=\"Debut-du-projet\"><\/span>Beginning of the project<span class=\"ez-toc-section-end\"><\/span><\/h2>\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-62418b5 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"62418b5\" 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-6f03335\" data-id=\"6f03335\" 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-8172f57 elementor-widget elementor-widget-image\" data-id=\"8172f57\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"image.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<img decoding=\"async\" width=\"1000\" height=\"673\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9-1.png\" class=\"attachment-large size-large wp-image-10901\" alt=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9-1.png 1000w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9-1-300x202.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image9-1-768x517.png 768w\" sizes=\"(max-width: 1000px) 100vw, 1000px\" title=\"\">\t\t\t\t\t\t\t\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-0c73e7b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"0c73e7b\" 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-709196a\" data-id=\"709196a\" 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-8c7a8d4 elementor-widget elementor-widget-text-editor\" data-id=\"8c7a8d4\" 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<p>Reality TV brings in billions of euros a year. But to make a difference, you have to always dare more. As a recent graduate of the famous film and audiovisual school Herr Guerard&#039;s Blinded Academy, you need to break into the profession as quickly as possible.<\/p><p>This is how you got the idea to make The Truman Show a reality. There is no shortage of ghost towns, but your budget is limited and you have to scratch the cash where you can. In order not to lose a drop of your reality TV, you must crisscross the city with your camera. The construction of the latter varies enormously from one point to another. Fortunately, you will remember the lessons of the eminent Professor Guerard on linear integer problems (ILP).<\/p><p>&quot; A <em><i>peak coverage<\/i><\/em>\u00a0Where <em><i>transverse<\/i><\/em>\u00a0of one <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> <em><i>G<\/i><\/em>\u00a0is a set <em><i>VS<\/i><\/em>\u00a0of vertices such that each edge of <em><i>G<\/i><\/em>\u00a0= (<em><i>V<\/i><\/em>, <em><i>E<\/i><\/em>) is incident at at least one vertex of <em><i>VS<\/i><\/em>v \u2208 S {\\ displaystyle v \\ in S}. &quot;<\/p><p>Concretely, this amounts to the following example: There are 6 lanes to control and the minimum number of 360 \u00b0 cameras must be placed so that each lane is seen by at least one camera. The minimum number is 2 and the two cameras form a coverage of the vertices.<\/p><p><img decoding=\"async\" class=\"alignnone wp-image-10904 size-medium\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image3-1-300x210.png\" alt=\"project linear programming combinatorial optimization branch and bound\" width=\"300\" height=\"210\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image3-1-300x210.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image3-1.png 315w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/p><p>The problem is written as follows:<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10903 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image2-1.png\" alt=\"project linear programming combinatorial optimization branch and bound\" width=\"627\" height=\"107\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image2-1.png 627w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image2-1-300x51.png 300w\" sizes=\"(max-width: 627px) 100vw, 627px\" \/><\/p><p>With <em><i>c (v)<\/i><\/em>\u00a0the cost of installing the camera at the top <em><i>v<\/i><\/em>. <em><i>x<\/i><\/em><em><sub><i>v<\/i><\/sub><\/em>\u00a0is worth 1 if we build a camera on the top <em><i>v<\/i><\/em>, otherwise it is 0. For each edge <em><i>(u, v)<\/i><\/em>, we set the following constraint <em><i>x<\/i><\/em><em><sub><i>u<\/i><\/sub><\/em><em><i>+ x<\/i><\/em><em><sub><i>v<\/i><\/sub><\/em><em><i>\u00a0less than 1<\/i><\/em>.<\/p><p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-10902 size-full\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1-1.png\" alt=\"project linear programming combinatorial optimization branch and bound\" width=\"1024\" height=\"516\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1-1.png 1024w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1-1-300x151.png 300w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1-1-768x387.png 768w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2020\/11\/Image1-1-1000x504.png 1000w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/p><p>Intersections and right angles are vertices, the road between two vertices is an edge. A roundabout counts as a single summit. Only roads are ridges (not parking lots, one-way lanes or unmarked roads). The cost of the cameras is equal to the number of lines of the demarcation lines of the adjacent roads (up to the next vertices).<\/p><h2><span class=\"ez-toc-section\" id=\"Notation\"><\/span><strong><b>Rating<\/b><\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2><ol><li>Build the corresponding graph <strong><b>(2 points)<\/b><\/strong><\/li><li>Making the ILP <strong><b>(3 points)<\/b><\/strong><\/li><li>Find a <a href=\"https:\/\/complex-systems-ai.com\/en\/linear-programming-2\/simplex-method-2\/\">basic fix<\/a> <strong><b>(5 points)<\/b><\/strong><\/li><li>Unroll the Branch &amp; Bound algorithm <strong><b>(10 points)<\/b><\/strong><\/li><\/ol><p>You have the right to use any simplex to solve PLs.<\/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>Linear Programming Wiki Home Page Linear Programming Project: The Truman Show This project requires linear programming concepts and algorithms \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":486,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-10886","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/10886","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=10886"}],"version-history":[{"count":3,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/10886\/revisions"}],"predecessor-version":[{"id":16675,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/10886\/revisions\/16675"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/486"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=10886"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}