Finding the optimal selections of x number per column and y numbers per row of an NxM array

37 views Asked by At

Given an NxM array of positive integers, how would one go about selecting integers so that the maximum sum of values is achieved where there is a maximum of x selections in each row and y selections in each column. This is an abstraction of a problem I am trying to face in making NCAA swimming lineups. Each swimmer has a time in every event that can be converted to an integer using the USA Swimming Power Points Calculator the higher the better. Once you convert those times, I want to assign no more than 3 swimmers per event, and no more than 3 races per swimmer such that the total sum of power scores is maximized. I think this is similar to the Weapon-targeting assignment problem but that problem allows a weapon type to attack the same target more than once (in my case allowing a single swimmer to race the same event twice) and that does not work for my use case. Does anybody know what this variation on the wta problem is called, and if so do you know of any solutions or resources I could look to?

1

There are 1 answers

0
Erwin Kalvelagen On

Here is a mathematical model:

Data

Let a[i,j] be the data matrix
and   
    x: max number of selected cells in each row 
    y: max number of selected cells in each column 

(Note: this is a bit unusual: we normally reserve the names x and y for variables. These conventions can help with readability).

Variables

 δ[i,j] ∈ {0,1} are binary variables indicating if cell (i,j) is selected.

Optimization Model

 max sum((i,j),  a[i,j]*δ[i,j])
 sum(j,δ[i,j]) ≤ x   ∀i
 sum(i,δ[i,j]) ≤ y   ∀j
 δ[i,j] ∈ {0,1}

This can be fed into any MIP solver.