Problem 45464. Design a minimum-cost cable network for a power grid

Created by Karl Ezra Pilario

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are given the 2-D point locations (</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>xi</w:t></w:r><w:r><w:t> ,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>yi</w:t></w:r><w:r><w:t> ) of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>components</w:t></w:r><w:r><w:t> of a power grid. These</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>components</w:t></w:r><w:r><w:t> include power sources (power plants, wind farms, solar farms, etc.), loads (residential, commercial, etc.), storage stations, and substations. However, the cables between them are not yet installed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your task is to design a</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>complete</w:t></w:r><w:r><w:t> cable network by installing cables between pairs of components. A network is considered</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>complete</w:t></w:r><w:r><w:t> if and only if a path exists from any component</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>A</w:t></w:r><w:r><w:t> to any other component</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>B</w:t></w:r><w:r><w:t>. A</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>completed</w:t></w:r><w:r><w:t> network of cables is enough to deliver power from any source to any load or vice versa (excess power can be sent back to the grid). After all, cables can carry power in both directions.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>However, the cost of installing a cable between components</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>A</w:t></w:r><w:r><w:t> &amp;</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>B</w:t></w:r><w:r><w:t> is</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>D</w:t></w:r><w:r><w:t> dollars per unit straight-line distance between their point locations. This means that we don't want to install too many cables; we only need to install enough to make the network</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>complete</w:t></w:r><w:r><w:t>. Knowing the locations of all</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> components, can you design a</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>complete</w:t></w:r><w:r><w:t> cable network whose total installation cost is minimium?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write a function that accepts variables</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>D</w:t></w:r><w:r><w:t>. Variable</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t> is an</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t>-by-2 matrix where each row is a location (</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>xi</w:t></w:r><w:r><w:t> ,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>yi</w:t></w:r><w:r><w:t> ). Output the required minimum total installation cost, rounded to 2 decimal places. You are ensured that:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>2 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> &lt;= 100</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>100 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>D</w:t></w:r><w:r><w:t> &lt;= 1000 and 1 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>xi</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>yi</w:t></w:r><w:r><w:t> &lt;= 100</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>D</w:t></w:r><w:r><w:t> and all elements of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>P</w:t></w:r><w:r><w:t> are integers</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>All point locations in a test case are distinct</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A sample test case is given below.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[>> P = [11 15; 4 14; 9 13; 13 12; 3 11; 6 11; 1 10; 9 9; ...\n 5 7; 13 7; 7 6; 10 5; 3 4; 6 2; 11 1];\n>> connect_grid(P,400)\nans = \n 18394.83]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A visualization of this case is given here:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://drive.google.com/open?id=1wqnH0j6aihbD_Jm5pxrW7dhTm3VxrEAI\"><w:r><w:t>&lt;https://drive.google.com/open?id=1wqnH0j6aihbD_Jm5pxrW7dhTm3VxrEAI</w:t></w:r></w:hyperlink><w:r><w:t>&gt;</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

You are given the 2-D point locations ( xi , yi ) of N components of a power grid. These components include power sources (power plants, wind farms, solar farms, etc.), loads (residential, commercial, etc.), storage stations, and substations. However, the cables between them are not yet installed.Your task is to design a complete cable network by installing cables between pairs of components. A network is considered complete if and only if a path exists from any component A to any other component B. A completed network of cables is enough to deliver power from any source to any load or vice versa (excess power can be sent back to the grid). After all, cables can carry power in both directions.However, the cost of installing a cable between components A & B is D dollars per unit straight-line distance between their point locations. This means that we don't want to install too many cables; we only need to install enough to make the network complete. Knowing the locations of all N components, can you design a complete cable network whose total installation cost is minimium?Write a function that accepts variables P and D. Variable P is an N-by-2 matrix where each row is a location ( xi , yi ). Output the required minimum total installation cost, rounded to 2 decimal places. You are ensured that:<ul><li>2 &lt;= N &lt;= 100</li><li>100 &lt;= D &lt;= 1000 and 1 &lt;= xi, yi &lt;= 100</li><li>D and all elements of P are integers</li><li>All point locations in a test case are distinct</li></ul>A sample test case is given below.<pre class="language-matlab">&gt;&gt; P = [11 15; 4 14; 9 13; 13 12; 3 11; 6 11; 1 10; 9 9; ...
 5 7; 13 7; 7 6; 10 5; 3 4; 6 2; 11 1];
&gt;&gt; connect_grid(P,400)
ans = 
 18394.83
</pre>A visualization of this case is given here: <a href = "https://drive.google.com/open?id=1wqnH0j6aihbD_Jm5pxrW7dhTm3VxrEAI">https://drive.google.com/open?id=1wqnH0j6aihbD_Jm5pxrW7dhTm3VxrEAI</a>

Solve

Solution Stats

7 Solutions
5 Solvers

Last Solution submitted on Jul 30, 2020

Last 200 Solutions

Problem Recent Solvers5

Problem Tags

chemical engineering power grid spanning tree

Problem 45464. Design a minimum-cost cable network for a power grid

Solution Stats

Last 200 Solutions

Problem Recent Solvers5

Suggested Problems

More from this Author19

Problem Tags

Problem 45464. Design a minimum-cost cable network for a power grid

Solution Stats

Last 200 Solutions

Problem Recent Solvers5

Suggested Problems

More from this Author19

Problem Tags

Players