# Optimization problem to find an optimal matrix

I need to find a $n\times m$ matrix $N$ with binary values $(0,1)$ which will maximize an objective function. N(i,j)=0 or 1 indicates whether jth offer is made to ith customer

• $m$ represents number of offers
• $n$ represents number of customers

I am trying to figure out best combination of offers to customers that will maximize expected profit.

Making an offer j has cost $C(j)$, and customers respond to different offers with different probabilities (represented by an $n\times m$ matrix $P$)

Constraint - Each individual gets at most one offer. ie Max[sum(N(i))]=1

I think the expected revenue would be P(i,j) x N(i,j) x [R(j)-C(j)] where R(j) represents revenue from j th offer.

• Here's a question to get started: given some $N$ of binary values, how do you find the expected profit? Commented Aug 3, 2013 at 2:54
• I am not so sure but I am thinking that, since I have probability matrix P, I can multiply it with (Revenue-Cost) and matrix N to find the expected profit. Commented Aug 3, 2013 at 2:57
• That doesn't seem right, notice that revenue depends on the probabilities, but the cost just depends on the number of non-zero entries in $N$. Commented Aug 3, 2013 at 3:00
• I think that, for i th person with j the offer, whenever N(i,j)=1 then the person will have have expected profit of P(i,j) x N(i,j)x (R(j)-C(j)). Do you have any suggestions?? Commented Aug 3, 2013 at 3:07
• I'll have something substantial as an answer shortly. Is the constraint that each customer gets exactly one offer or at most one offer? Commented Aug 3, 2013 at 3:08

## Initial Attempts:

Let's get the mathematical framework down. Suppose we have a matrix $N$. Our expected profit will always be $$(\text{total expected revenue from customers})-(\text{total cost of offers})$$ The expected cost will be given by $$\text{Cost} = \begin{bmatrix} 1&1&\cdots&1 \end{bmatrix} N \begin{bmatrix} C_1\\ C_2\\ \vdots\\ C_j \end{bmatrix}$$

(Why)? To find the expected revenue from a single customer $i$ from a choice of promotion $j$, we have $$R_{i,j}=N_{i,j}P_{i,j}R_j$$ Where $R_j$ is the revenue associated with a successful promotion $j$.

With that in mind, the total expected revenue is $$R=\sum_{i=1}^n\sum_{j=1}^m N_{i,j}P_{i,j}R_j$$ We find $$\text{Revenue} = \begin{bmatrix} 1&1&\cdots&1 \end{bmatrix} \begin{bmatrix} N_{11}P_{11} & N_{12}P_{12} & \cdots\\ N_{21}P_{21} & N_{22}P_{22} & \cdots\\ \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} R_1\\ R_2\\ \vdots\\ R_j \end{bmatrix}$$ So far, I have not used the constraint. I am fairly sure that simplifies things here somehow

## Solution:

I've been making the problem far more complicated than it needs to be. All we have to do is find the choice that maximizes the profit from each customer, one customer at a time. That is, we have the following algorithm:

Initializations:

P as nxm matrix of probabilities
R = [R1,R2,...,Rm]
C = [C1,C2,...,Cm]

N as nxm matrix of zeros

Iteration:

for i = 1 to n
maxProfit = 0
maxIndex = 0
for j = 1 to n
if P(i,j)*R(j)-C(j) > maxProfit
maxProfit = P(i,j)*R(j)-C(j)
maxIndex = j
if maxIndex > 0
N(i,maxIndex) = 1


I can't think of any faster or more mathematically concise way to solve this problem.