Discrete optimization for a function on a matrix

Question

This is an optimization question I've simplified from a more specific problem i'm having, but I'm not sure specifically where this problem is classified under, or the method to obtain a solution (brute force, simulated annealing, linear programming?). Any help or references are appreciated!

We have two MxN matrices M1 and M2, where each entry is either 1 or 0.

I'm trying to get from matrix M1 to matrix M2 in the least amount of time possible.

The goal is to minimize the total time, where time is defined by the following:

• 0 -> 1 transition = 1s
• 1 -> 0 transition = 0.1s

The only way the matrix can be changed is by selecting a set of rows and columns, and all the elements at the intersections of the picked rows and columns are switched to 0 / 1, with the entire transition taking the time specified above.

Example:

M1
1 1 1
1 1 0
1 0 0

M2
0 0 1
0 1 1
1 1 1

First iteration:

1. Select rows 2 and 3, and columns 2 and 3 of M1.

2. Convert all intersecting elements to 1

   • takes 1s

M1
1 1 1
1 1 1
1 1 1

Second iteration:

1. Select rows 1, and columns 1 and 2 of M1.

2. Convert all intersecting elements to 0

   • takes 0.1s

M1
0 0 1
1 1 1
1 1 1

Third iteration:

1. Select row 2 and column 1 of M1.

2. Convert the selected element to 0

   • takes 0.1s

M1
0 0 1
0 1 1
1 1 1

Here, the total time is 1.2s.

Answer 1

For the sizes given, this looks like it will be very hard even to approximate. Anyway, here are a couple of ideas.

When a cell needs to change from 0 to 1, I'll write +, when it needs to change in the other direction I'll write -, and when it needs to stay as-is, I'll write either 0 or 1 (i.e. whatever it currently is). So e.g. the problem instance in the OP's question looks like

- - - 1
- - 1 +
- 1 + +
1 + + +

Let's consider a slightly easier monotone version of the problem, in which we never change a cell twice.

• Generally requires many more moves, but gives a useful starting point and an upper bound.
• In this version of the problem, it doesn't matter in which order we perform the moves.
• Simple variations might be more effective as heuristics, e.g. performing a small number of initial 0->1 moves in which every + cell is changed to 1 and other cells are possibly changed too, followed by a series of 1->0 moves to change/fix all other cells.

Shrinking the problem safely

[EDIT 11/12/2014: Fixed the 3rd rule below. Unfortunately it's likely to apply much less often.]

The following tricks never cause a solution to become suboptimal, and may simplify the problem:

• Delete any rows or columns that contain no +-cell or --cell: no move will ever use them.
• If there are any identical rows or columns, collapse them: whatever you do to this single collapsed row or column, you can do to all rows or columns separately.
• If there is any row with just a single +-cell and no 1-cells, you can immediately fix all +-cells in the entire column containing it with a single 0->1 move, since in the monotone problem it's not possible to fix this cell in the same 0->1 move as any +-cell in a different column. Likewise with rows and columns swapped, and with a single --cell and no 0-cells.

Applying these rules multiple times may yield further simplification.

A very simple heuristic

You can correct an entire row or column of + or --cells in a single move. Therefore it is always possible to solve the problem with 2*min(width, height) moves (the 2 is there because we may need both 0->1 and 1->0 moves). A slightly better approach would be to greedily find the row or column with the most cells needing correction, and correct it in a single move, switching between rows and columns freely.

The best possible move

Suppose we have two +-cells (i, j) and (k, l), with i <= k and j <= l. They can be changed in the same 0->1 move exactly when both of their "opposite corners" (i, l) and (k, j) are either + or 1. Also notice that if either or both of (i, j) and (k, l) are 1 (instead of +), then they could still be included in the same move, even though that move would have no effect for one or both of them. So if we build a graph G in which we have a vertex for every cell and an edge between two vertices (i, j) and (k, l) whenever (i, j), (k, l), (i, l) and (k, j) are all either + or 1, a clique in this graph corresponds to a set of cells that can all be changed to (or left at) 1 in a single 0->1 move. To find the best possible move -- that is, the move that changes the most possible 0s to 1s -- we don't quite want the maximum-sized clique in the graph; what we actually want is the clique that contains the largest number of +-cell vertices. We can formulate an ILP that will find this, using a 0/1 variable x_i_j to represent whether vertex (i, j) is in the clique:

Maximise the sum over all variables x_i_j such that (i, j) is a `+`-cell
Subject to
    x_i_j + x_k_l <= 1 for all i, j, k, l s.t. there is no edge (i, j)-(k, l)
    x_i_j in {0, 1} for all i, j

The constraints prevent any pair of vertices from both being included if there is no edge between them, and the objective function tries to find as large a subset of +-cell vertices as possible that satisfies them.

Of course, the same procedure works for finding 1->0 moves.

(You will already run into problems simply constructing a graph this size: with N and M around 1000, there are around a million vertices, and up to a million million edges. And finding a maximum clique is an NP-hard problem, so it's slow even for graphs with hundreds of edges...)

The fewest possible moves

A similar approach can tell us the smallest number of 0->1 (or 1->0) moves required, and at the same time give us a representative cell from each move. This time we look for the largest independent set in the same graph G:

Maximise the sum over all variables x_i_j such that (i, j) is a `+`-cell
Subject to
    x_i_j + x_k_l <= 1 for all i, j, k, l s.t. there is an edge (i, j)-(k, l)
    x_i_j in {0, 1} for all i, j

All that changed in the problem was that "no edge" changed to "an edge". This now finds a (there may be more than one) maximum-sized set of +-cell vertices that share no edge between them. No pair of such cells can be changed by the same 0->1 move (without also changing a 0-cell or --cell to a 1, which we forbid in the monotone version of the problem, because it would then need to be changed a second time), so however many vertices are returned, at least that many separate 0->1 moves are required. And because we have asked for the maximum independent set, no more moves are needed (if more moves were needed, there would be a larger independent set having that many vertices in it).