# Combinatorial Optimization Problem (can I/how do I solve this with integer programming?)

Inputs:

1) A set of M x N matrices, {A,B,C...N} containing only integers.

2) A single 1 x N matrix of floats, W (weights).

I need to pull one row from each input matrix and sum values for each column, then take the dot product of the resulting 1 x N matrix with W, yielding a score K.

Ex:

A = [1 3 5 6], B = [3 4 5 6], W = [0.5 0.1 2.0 3.0]

In this case there is only one row in each input matrix so we pick the only rows from A and B, sum their columns to get [4 7 10 12] and dot that with W to yield 58.7, our value for K.

EDIT: In addition there is a constraint on one of the columns such that the corresponding weight from W drops by some amount when the sum for that column is greater than some fixed value, for example we might specify that 3 is the cap for the first column in the previous example, with the weight dropping to 0.2 after that has been exceeded. This would make the score for [4 7 10 12] = [(3 * 0.5) + (1 * 0.2) + (7 * 0.1) + (10 * 2.0) + (12 * 3.0) = 58.4

The goal is to find the global maximum K for all combinations of rows from the input matrices (where we take one row from each matrix).

If the set of input matrices is large and the number of rows is more than a couple, the number of row combinations blows up.

-
I don't think your edit has changed the fact that (as Noah Stein said) the greedy algorithm works. You can just try all the rows of each matrix and pick the best one for your given W, effect of the cap and all. There still doesn't seem to be any interaction between what you do with the first matrix and what you do with the second. – Ross Millikan Jan 27 '11 at 0:29
Given A = [10 0], B = [10 5, 0 10] and W = [(1 when < 10, else 0) 1], a greedy algorithm will pick the first row of B, resulting in K = 15 when picking the second row of B yields K = 20, clearly the optimal solution. The cap applies to the total, not per-row. – Daniel Coffman Jan 27 '11 at 0:53

Suppose that the input matrices are $A_1,\ldots, A_L$. Let $r_1, \ldots, r_L$ be a choice of one row from each of them. We want to maximize $(r_1 + \cdots + r_L ) \bullet W = r_1\bullet W + \cdots + r_L \bullet W$ over all such choices of $r_i$. The right hand side shows that we can use the greedy algorithm which chooses $r_i$ to be the row of $A_i$ which makes the biggest dot product with $W$: choosing $r_i$ in this way doesn't restrict our choices on the other $r_j$ in any way. The algorithm to compute all these dot products and choose the biggest one runs in linear time in the size of the input.

EDIT: The new version, formalized as a decision problem which asks whether we can pick a set of the rows to give objective value at least $M$, is NP-complete. To see that it is in NP, have the algorithm guess the optimal rows. To see that it is NP-hard, we reduce from set cover, which is a problem where we are given a set $\mathcal{S} = \{S_1,\ldots, S_M\}$ of subsets of the set $\{1,\ldots,N\}$ and we want to know whether there are $K$ sets in $\mathcal{S}$ whose union is all of $\{1,\ldots, N\}$.

We must turn these into an instance of your problem. Define the matrix $A$ by $A_{ij} = 1$ if $j\in S_i$ and zero otherwise. The $i^\text{th}$ row of $A$ is then the indicator function for the set $S_i$. Let $L = K$ all the matrices $A_1 = \cdots = A_L = A$. Have the objective $W$ put weight $1$ on each column until a value of $1$ is achieved in that column and weight $0$ afterwards. Then the objective value for a given choice of rows is the cardinality of the union of the corresponding subsets in $\mathcal{S}$. In particular the optimal objective value is $\geq N$ if and only if the set cover problem was solvable.

-
Thank you Noah! Can you maybe advise given my edit above? I seem to have left out a crucial part of the problem and don't think a greedy algorithm will work now. – Daniel Coffman Jan 26 '11 at 23:37