using matchpairs when objects have different capacities

I am using the matchpairs function to determine the assignment of objects to people that minimizes the total cost.

It takes as input a matrix where element i,j indicates the cost of assigning object i to agent j.

However, the solution implies that each object can only be assigned to one person. What if object j can be asisgned to k persons?

Answer 1

[Steven Lord]

You could duplicate rows or columns in the matrix you pass to matchpairs to reflect that "multiple copies" of the object to be matched are available. Adapting the "Assign Flight with Minimal Cost" example on the matchpairs documentation page:

people = ["Fred"; "Beth"; "Sue"; "Greg"];
cities = ["Dallas"; "Chicago"; "New York City"; "St. Louis"];
C = [600 670 960 560
     900 280 970 540
     310 350 950 820
     325 290 600 540];
C(:, 5) = C(:, 2); % Two people can go to Chicago
cities(5) = cities(2);
M = matchpairs(C, 1000);
for n = 1:height(M)
    fprintf("Person %s is going to %s.\n", people(M(n, 1)), cities(M(n, 2)))
end

Person Sue is going to Dallas.
Person Beth is going to Chicago.
Person Fred is going to St. Louis.
Person Greg is going to Chicago.

No one is going to New York City, which makes sense since it has the most expensive flights. Greg is going to Chicago in this modified example, where in the original example Greg went to NYC.

Answer 2

[Matt J]

Then you are not seeking pairings. Therefore, matchpairs will not apply. But you can probably use minL1intlin from this FEX download,

https://www.mathworks.com/matlabcentral/fileexchange/52795-constrained-minimum-l1-norm-solutions-of-linear-equations?s_tid=srchtitle

to solve your more general problem. You can imitate what is done in "Example 2: Optimal Reordering of Points" under the examples tab. Except, though, you would drop the constraint,