linear programming optimization for matrix

I have a n x n matrix that contains cost for each element.

Each row and each column should satisfy the requirement while it can minimize the sum of activated elements. In this case, activated means its coefficient is 1.

A 4x4 matrix with costs $a_ij$ can look like this:

|100  -20  30  40 | = 2     
|10   20   10  20 | = 1     
|50   -40  20  10 | = 2     
|-10  -30  10  50 | = 1    
 1     2   1    2   = 6

So the first row can only have two elements to have coefficient of 1 and the first column can only have one element to. The objective is basically the summation of all elements that are non-zero.

The results can be:

|0  1  0  1 | = 2
|0  0  0  1 | = 1
|1  0  1  0 | = 2
|0  1  0  0 | = 1
 1  2  1  2   = 6

The objective is then: 1 * -20 + 1 * 40 + 1 * 20 + 1 * 50 + 1 * 20 + 1 * - 30 = 80

In SAS, there is netflow package but there is no similar packages R. I have tried to use pulp in python but it did not seem working. It also seems like we need to hard code each variable. Any suggestions on how else I might formulate the problem would be much appreciated! Thanks a lot!

Here's a start in pulp. You'll likely get better answers if you show what you have worked on so far...

A couple of notes:

• in pulp you can either make a couple of nested loops and declare the variables individually (many examples) or use the .dicts method and pass an index set. I like that because then you can use tuple indexing [i, j]
• if you want to be consistent in your indexing, you could flatten out costs to the same type of index or just declare variable within nested loop and do nested indexing throughout [i][j]

Try your constraints.... they should be a snap by looping over rows/cols as needed. Print the model after you make each one to make sure the math is correct.

Comment back if you are stuck.

import pulp

costs = [
	[100 , -20 , 30 , 40 ],     
	[10  , 20  , 10 , 20 ],     
	[50  , -40 , 20 , 10 ],     
	[-10 , -30 , 10 , 50 ],    
]

rows, cols = 4, 4
index_set = [(i, j) for i in range(rows) for j in range(cols)]

# set up the problem
prob = pulp.LpProblem('matrix_picker', sense=pulp.LpMaximize)

# variables
select = pulp.LpVariable.dicts('select', index_set, cat=pulp.LpBinary )

# objective
prob += sum(select[i, j] * costs[i][j] for i, j in index_set)

print(prob)