## Mathematica Integer Linear Programming using branch-and-bound

As it has already been mentioned, this problem can be solved using integer linear programming (which is NP-Hard). Mathematica already has ILP built in. `"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."`

[see Constrained Optimization Tutorial in Mathematica.. ]

I've written the following code that utilizes ILP libraries of Mathematica. It is surprisingly fast.

```
solveMatrixBombProblem[problem_, r_, c_] :=
Module[{},
bombEffect[x_, y_, m_, n_] :=
Table[If[(i == x || i == x - 1 || i == x + 1) && (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 >= problem] &&
And @@ Thread[X >= 0] && Total[X] <= 10^100 &&
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}]]];]
```

For the example provided in the problem:

```
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]
```

Outputs

## For anyone reading this with a greedy algorithm

Try your code on the following 10x10 problem:

```
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
```

Here it is comma-seperated:

```
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
```

For this problem, my solution contains **208** bombs. Here's a possible solution (I was able to solve this in about 12 seconds).

As a way to test the results Mathematica is producing, see if your greedy algorithm can do any better.

Hint: under what circumstances is a bomb in one location just as good as a bomb in another, and maybe better? – Beta – 2013-03-08T17:56:23.010

2@beta, are you thinking greedy and drop on the biggest? Because that doesn't work. Take a 1x5 board with

`2 2 4 2 2`

. Only such locations I can think of are the corners, where you can put a bomb in the diagonal neighbor, but that doesn't solve much. – Shahbaz – 2013-03-08T17:58:19.3304Well I just find ot that some fields can be skipped like in example

2 3

1 5 Droping it on 2,3,1 is pointless, because dropping on them cause some subset damage which we can cause by dropping on 5. But can't find how to make it work globally (if it's correct way). Clearing 2 require use 2 bombs dropped on any of neighbour and 5 is containing other sets of damage. But then I don't know what to do later on since when you rewrite it (after decreasing), then you have two choice (there isn't one uber-set of damage). – abc – 2013-03-08T17:58:43.030

Great question. I have an idea I'm going to try before posting an answer. – Anthony Queen – 2013-03-08T18:00:07.107

23

Is this NP-hard by any chance? It looks to be a variant of the Maximum Coverage Problem.

– Mysticial – 2013-03-08T18:26:51.807I think you could try searching for the number that has the most 1's around it. When there are 2 numbers with equal number of 1's you could look for the one with the lowest numbers or fewer 0's and repeat. – Osukaa – 2013-03-08T18:32:44.133

1@Mysticial I suspect the OP is some malicious guy trying to decide if P = NP by work of others. Shame on you for trying to deceive us, Kostek! :P – brandizzi – 2013-03-08T18:32:52.283

1Can't be NP it's use on contest (4 task -> 5hours). Can give you link to content if you understand polish language as a proof. – abc – 2013-03-08T18:34:56.017

1@Kostek It could still be NP and doable. The problem size that you've given isn't very large. It's hard enough to produce a working answer - let alone one that runs in polynomial time. – Mysticial – 2013-03-08T18:36:15.757

I wonder how fast the simplex algorithm would run on this type of problem? – Peter de Rivaz – 2013-03-08T18:44:31.067

14+1 for giving me something interesting to think about – Nick Mitchinson – 2013-03-08T18:49:39.087

Are you wanting a Coded solution, a Mathmatical expression, or just the thought process? – Anthony Queen – 2013-03-08T19:07:59.267

2"A

bomb patternis a term I dreamed up just several weeks ago. It means nothing, but you'd be surprised at how rapidly it's caught on. Why, I've got all sorts of people convinced I think it's important for the bombs to explode close together and make a neat aerial photograph. There's one colonel in Pianosa who's hardly concerned any more with whether he hits the target or not." — General Peckem,Catch 22. – Colonel Panic – 2013-03-08T19:14:05.8673@Kostek, great problem! Please post the link. – Colonel Panic – 2013-03-08T19:29:53.707

@Shahbaz: No, I wasn't thinking of hit-the-highest (which doesn't fit my question). Yes, I was thinking of the corners, and actually it helps a lot. – Beta – 2013-03-08T19:34:47.237

3This looks a bit like Minesweeper, except that you could put bomb on a point more than once and the number only indicate the minimum number of bombs on and around a point instead of the exact number. – Lie Ryan – 2013-03-08T20:49:20.970

5perhaps you should clarify, you said the question is:

`what's the minimum amount of bombs required to clean the board?`

Does this means that it is not necessarily needed to find an actual bombing pattern, but just the minimal number of bombs? – Lie Ryan – 2013-03-08T21:25:35.447Is it problem from some online judge? I would try to check my solution. – RiaD – 2013-03-08T21:27:30.027

@LieRyan Maybe you're seeing something that I don't, but I'm fairly sure you can't find the minimal number of bombs required without essentially having computed the actual pattern... – us2012 – 2013-03-08T21:38:31.440

3@us2012: It is fairly easy to find a lower bound and upper bound for possible number of bombs, and if they matches than that must be the exact number of bombs needed, that can be found without calculating the actual pattern. But that situation probably would only happen once in a blue moon, if ever. – Lie Ryan – 2013-03-08T21:45:25.510

@LieRyan: Well, exactly. Even if you are thinking of more sophisticated bounds than the immediately obvious ones (sum of values/9, sum of values), they are hardly ever going to coincide. Unless your bounds are

muchmore sophisticated, in which case they might contribute to a solution and you should post an answer with details. – us2012 – 2013-03-08T21:49:01.873@us2012: I've added an answer that describes what I'm thinking of, it's a method to find a minimum bound without finding a solution. When combined with a greedy algorithm, it can be used to prove that the solution found by the greedy, in this particular case, is indeed an optimal solution. – Lie Ryan – 2013-03-08T23:00:28.033

If from a contest, what are the limits of the inputs? – Winston Ewert – 2013-03-08T23:33:23.230

@Kostek: Would be interested in seeing the original problem. – nneonneo – 2013-03-08T23:53:27.597

Also, if your

`m`

and`n`

and the numbers are all small enough, you can try doing full tree search, which indeed will give you optimal solution, however, it will take much time. – Sarge Borsch – 2013-03-09T09:16:40.1272.4k views in a single day? That's something uh? – asprin – 2013-03-09T15:02:21.327

1

Are you interested in the

– ESultanik – 2013-03-09T18:52:23.003decisionproblem (i.e., just knowing the minimum number of bombs required), or are you also interested in theoptimizationproblem (i.e., knowingwhichbombs are required, not just how many)?@ESultanik: that's not how decision/optimization are defined. Decision is "can you do it with less than

`k`

bombs", optimization is "how few bombs does it take". Neither require you to actually specify the full solution except as proof. – nneonneo – 2013-03-09T19:59:24.010@asprin some guy posts his homework and gets a ton of rep for it. :D – Meirion Hughes – 2013-03-09T20:46:31.587

@asprin 2.4k is nothing. I've seen over 100k in a day before. – Mysticial – 2013-03-09T21:36:18.940

For people to fiddle with: http://jsbin.com/ivaruj/2 (ignore the code please, thanks)

– mowwwalker – 2013-03-10T10:03:54.103So many answers... Iwill try repost as many as can. If I omitted someone recomment pls.

@Anthony Queen Anything. Target is that I have to understand that - why? Why some approach works, how to deal with similar problems and so on. – abc – 2013-03-10T13:48:43.727

2

@Colonel Panic here you go https://www.deadline24.pl/assets/Uploads/dl24.elim.A.2012.pdf It's polish tho. You can try some translation but effects are not guarantee.

– abc – 2013-03-10T13:49:00.277@RiaD I haven't found any test nor judge on the page above. But maybe just not search good enough. – abc – 2013-03-10T13:49:15.533

@Winston Ewert Board is up to 1000x1000 each field "health" as well 1000. No time limit given. – abc – 2013-03-10T13:49:42.833

@nneonneo Check 3 answers above – abc – 2013-03-10T13:50:57.247

@Sarge Borsch 4 tasks, 5 hours to do it. Limits were given 2 post above. Doubt I can fit with memory (32 bit machine I believe). – abc – 2013-03-10T13:52:26.073

@ESultanik I want to know singular integer number of bombs which are required to decrease all to 0. Number must be smallest possible. – abc – 2013-03-10T13:53:44.217

@Meirion Hughes Troll... It's just preparation to contest nothing to do with university. – abc – 2013-03-10T13:54:36.977

So many answers that I cannot follow to read them T.T – abc – 2013-03-10T13:56:36.160

Also as I said suboptimal is not an option. Answer must be exact, because notes were binary 1 (correct), 0(incorrect). – abc – 2013-03-10T14:01:04.330

2I give update to task forgot about one constraint sequnce in row would not be increasing so

`8 7 7 6 6 5 3 0`

is valid row`4 2 3 2 1 8 7 7`

is not valid row – abc – 2013-03-10T14:05:45.0531@Kostek, please leave the problem as it was since the general case is a lot more interesting. You can add the new constraint as part (b) or bonus, or just new section. For instance, ask: "Bonus: can you find an efficient algorithm if the rows are non-decreasing?" – darksky – 2013-03-10T14:56:25.223

@darsky Ok. I will do so. – abc – 2013-03-10T14:57:15.533

@nneonneo Sure, I was being a bit lax with definitions. It depends, though; often the certificate for a combinatorial optimization problem is the variable assignment, not just the value of the objective function. It sounds like the certificate for which Kostek is interested is simpler (and perhaps amenable to a less computationally complex algorithm) than what most of the answers below assume. – ESultanik – 2013-03-10T19:59:13.763

I do not understand the constrain. Can you explain it again please? The edit, I mean. ( The B Option? ) – Koray Tugay – 2013-03-11T11:48:03.530

for the B constrain, is that sequence must be decreasing for both horizontal and vertical or only horizontal? – Lie Ryan – 2013-03-11T15:57:09.720

@Kostek, I recommend removing the B option, its easy to solve as nneonneo showed and it is a distraction from the original question which generated a huge amount of interest and responses. I think you should revert the question to its original form and let this good conversation continue, even if it is not the conversation you wanted to start :). – Ben Haley – 2013-03-12T16:23:05.573

Any chance you work for Roomba and are creating a bomb-dropping drone for the air force? – Brian Webster – 2013-03-13T21:09:34.860

If a bomb decreases only horizontal and vertical neighbors and all weights are allowed (version A), then the problem is NP-hard, as proven in web.sau.edu/lilliskevinm/wirelessbib/ClarkColbournJohnson.pdf (Theorem 5.1), as you can easily convert their grid graphs to a matrix using 0 and 1 entries. Dropping a bomb is then equivalent to adding that vertex to the dominating set. I'm pretty sure you can prove the case with diagonal neighbors NP-hard in the same way with a few modifications. – Alex ten Brink – 2013-03-16T16:28:15.043