Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm writing some software, and one part of the software needs to be able to solve this problem as well as possible. Consider a table of integers and goal, for example:

$$T = \begin{array} {c|c|c|c|c|c|c|c|} & A & B & C & D & E & F & G \\ \hline \text{Row 1} & 3 & & & -1 & & & \\ \hline \text{Row 2} & & & & & -1 & & \\ \hline \text{Row 3} & & 1 & & & & -1 & \\ \hline \text{Row 4} & & & 7 & -1 & & & \\ \hline \text{Row 5} & & 2 & & & -1 & & \\ \hline \text{Row 6} & 4 & & 4 & & & -1 & \\ \hline \text{Row 7} & & 2 & & & & & -2 \\ \hline \end{array}$$

$$G = \begin{array} {c|c|c|c|c|c|c|c|} & A & B & C & D & E & F & G \\ \hline \text{Goal} & 6 & 8 & 4 & -1 & -1 & -1 & -7 \\ \hline \end{array}$$

My problem is to assign an integer coefficient to each row of the table, so that the linear combination of the rows sums to at least the goal. "At least" means that every element in the sum is $\ge$ every element in the goal.

So if we choose Row 1 once, Row 5 once, Row 6 once, and Row 7 three times, the resultant sum is:

$$\begin{array} {c|c|c|c|c|c|c|c|} & A & B & C & D & E & F & G \\ \hline T_1 + T_5+T_6 + 3T_7 & 7 & 8 & 4 & -1 & -1 & -1 & -6 \\ \hline \end{array}$$

Since each element in the sum is $\ge$ each element in the goal, $\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 3 \end{bmatrix}$ is a solution for this example.

There is a further constraint on the problem which guarantees that it only has a finite number of solutions. Some subset of columns, $C$, are guaranteed to be "cost" columns. Let the cost of a row be given by:

$$Cost(r) = \sum_{c \in C} T_{r,c}$$

It is a constraint on $T$ that $\forall r\, Cost(r) < 0$. Since the cost of the final sum is finite, and increasing a coefficient decreases the cost of the final sum, there can only be a finite number of solutions. In the above example, $D\, E\, F\, G$ are the cost columns.

I doubt this problem is solvable in polynomial time without solving np completeness. I'm looking for the fastest heuristics to solve it. I would prefer to be able to enumerate all solutions (even if there are exponentially many of them), but even finding a few solutions would be a good start.

My questions for stackexchange is does anyone know of an algorithm or heuristic to solve this problem, or a similar algorithm that could be modified to solve it?

share|improve this question
    
Unless I'm missing something, it seems your constraints are all linear, so it's a standard integer linear program. en.wikipedia.org/wiki/Integer_programming –  p.s. Nov 25 '13 at 6:14
    
I just learned the term "integer programming" as I was searching the tags, and I've been reading about it on wikipedia since. I'm not completely sure though since I'm trying to enumerate, not maximize. –  DanielV Nov 25 '13 at 13:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.