Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h2>Mathematica Integer Linear Programming using branch-and-bound</h2> <p>As it has already been mentioned, this problem can be solved using integer linear programming (which is <a href="http://en.wikipedia.org/wiki/NP-hard" rel="nofollow noreferrer">NP-Hard</a>). Mathematica already has ILP built in. <code>"To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method."</code> [see <a href="https://docs.google.com/file/d/1v0cT254BBC9EolkzdmDj-bOwFW8IzTtDWf8pN7Dl9EAd0kdMhbzc_0ii10sH/edit" rel="nofollow noreferrer">Constrained Optimization</a> Tutorial in Mathematica.. ]</p> <p>I've written the following code that utilizes ILP libraries of Mathematica. It is surprisingly fast. </p> <pre><code>solveMatrixBombProblem[problem_, r_, c_] := Module[{}, bombEffect[x_, y_, m_, n_] := Table[If[(i == x || i == x - 1 || i == x + 1) &amp;&amp; (j == y || j == y - 1 || j == y + 1), 1, 0], {i, 1, m}, {j, 1, n}]; bombMatrix[m_, n_] := Transpose[ Table[Table[ Part[bombEffect[(i - Mod[i, n])/n + 1, Mod[i, n] + 1, m, n], (j - Mod[j, n])/n + 1, Mod[j, n] + 1], {j, 0, m*n - 1}], {i, 0, m*n - 1}]]; X := x /@ Range[c*r]; sol = Minimize[{Total[X], And @@ Thread[bombMatrix[r, c].X &gt;= problem] &amp;&amp; And @@ Thread[X &gt;= 0] &amp;&amp; Total[X] &lt;= 10^100 &amp;&amp; Element[X, Integers]}, X]; Print["Minimum required bombs = ", sol[[1]]]; Print["A possible solution = ", MatrixForm[ Table[x[c*i + j + 1] /. sol[[2]], {i, 0, r - 1}, {j, 0, c - 1}]]];] </code></pre> <p>For the example provided in the problem:</p> <pre><code>solveMatrixBombProblem[{2, 3, 4, 7, 1, 1, 5, 2, 6, 2, 4, 3, 4, 2, 1, 2, 1, 2, 4, 1, 3, 1, 3, 4, 1, 2, 1, 4, 3, 2, 6, 9, 1, 6, 4}, 7, 5] </code></pre> <p>Outputs</p> <p><img src="https://i.stack.imgur.com/LhGT9.png" alt="enter image description here"></p> <h2>For anyone reading this with a greedy algorithm</h2> <p>Try your code on the following 10x10 problem:</p> <pre><code>5 20 7 1 9 8 19 16 11 3 17 8 15 17 12 4 5 16 8 18 4 19 12 11 9 7 4 15 14 6 17 20 4 9 19 8 17 2 10 8 3 9 10 13 8 9 12 12 6 18 16 16 2 10 7 12 17 11 4 15 11 1 15 1 5 11 3 12 8 3 7 11 16 19 17 11 20 2 5 19 5 18 2 17 7 14 19 11 1 6 13 20 8 4 15 10 19 5 11 12 </code></pre> <p>Here it is comma-seperated: </p> <pre><code>5, 20, 7, 1, 9, 8, 19, 16, 11, 3, 17, 8, 15, 17, 12, 4, 5, 16, 8, 18, 4, 19, 12, 11, 9, 7, 4, 15, 14, 6, 17, 20, 4, 9, 19, 8, 17, 2, 10, 8, 3, 9, 10, 13, 8, 9, 12, 12, 6, 18, 16, 16, 2, 10, 7, 12, 17, 11, 4, 15, 11, 1, 15, 1, 5, 11, 3, 12, 8, 3, 7, 11, 16, 19, 17, 11, 20, 2, 5, 19, 5, 18, 2, 17, 7, 14, 19, 11, 1, 6, 13, 20, 8, 4, 15, 10, 19, 5, 11, 12 </code></pre> <p>For this problem, my solution contains <strong>208</strong> bombs. Here's a possible solution (I was able to solve this in about 12 seconds).</p> <p><img src="https://i.stack.imgur.com/cquS3.png" alt="enter image description here"></p> <p>As a way to test the results Mathematica is producing, see if your greedy algorithm can do any better.</p>
    singulars
    1. This table or related slice is empty.
    1. POBomb dropping algorithm
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USdarksky
    1. USdarksky
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI was able to do it in 219 with this answer: http://stackoverflow.com/questions/15300149/bomb-dropping-algorithm/15301559#15301559
      singulars
      1. PO
      1. USAnthony Queen
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload