Clear Filters
Clear Filters

using matchpairs when objects have different capacities

8 views (last 30 days)
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?

Accepted Answer

Steven Lord
Steven Lord on 25 May 2023
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)))
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.

More Answers (1)

Matt J
Matt J on 25 May 2023
Edited: Matt J on 25 May 2023
Then you are not seeking pairings. Therefore, matchpairs will not apply. But you can probably use minL1intlin from this FEX download,
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,


Find more on Matrix Computations in Help Center and File Exchange



Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!