MATLAB linear assignment problems.

MATLAB Linear Assignment Problems:

Today we’ll take a look at how to solve some linear assignment problems for the matrix with rows and columns. For example for M = match pairs(Cost, costUnmatched) will be the solution for the matrix Cost. Here each row will be linked to a column in a way that resulting cost will be minimized. The second variable cost unmatched specifies the cost per row of not linking each row and also cost per column for each of them which is not having a row linked to each column.

[M,uR,uC] = match pairs(Cost,costUnmatched) also gives indexes for unmatched rows to uR and gives indexes for unmatched columns to uC.

[___] = matchpairs(Cost,costUnmatched,goal) defines the goal of the optimization using any of the output argument variations in previous syntaxes. Variable goal here can be 'min' or 'max' to make matches that will minimize or maximize the total cost.

Examples of usage:

Let’s see a few examples here, first one will be something like to find flights with minimal cost. Let’s assume that we have like four people and we want them to visit four main cities in our country. These flights must be booked in advance but also there is a need to spend as little as only possible. The company is big and that salespeople located in different parts of the country so it’s different for them to visit each city in money for the flight. Here is the table below which will show how much it will cost for each person to fly to a certain city.

And each visit to the city is a sort of big sale opportunity. If the city is missed then the company will lose something like $2000 revenue on average.

So we create matrix C to represent all these costs of flying to each city for each person here.

C = [600 670 960 560
     900 280 970 540
     310 350 950 820
     325 290 600 540];

And then we will use our function match pair to link all that salespeople to each city with minimal cost. Unassigned case there will be 1000 instead of 2000 cause it will be unmatching for both row and column, see my point? It’s an important thing to notice here.

M = matchpairs(C,1000)
 M = 4×2      
3     1      
2     2
4     3      
1     4 

So that function match pairs have calculated the least expensive way to deliver a salesperson to each city there.

Another Example:

Another example would be linked taxi drivers to routes in order to maximize profits this time. Some taxi company have been given several requests to ride across the city. It has only 3 cabs and can’t fulfill all requests but want to make most of the money from what is given obviously. Let’s build a table for each cab and each request, we got 5 requests, but only 3 can be filled.

Then let’s create profit matrix P to put all that numbers in it

P = [5.7 6.3 3.1 4.8 3.5
     5.8 6.4 3.3 4.7 3.2
     5.7 6.3 3.2 4.9 3.4];

Now let’s use match pairs to get taxis to most profitable destinations. We need to select 3 outputs to get in return all nonmatched columns and rows and ‘max’ option to get a max of the profits. Define unlinked rides as 0 since there is no profit of unfulfilled request or empty taxi

costUnmatched = 0;
[M,uR,uC] = matchpairs(P,costUnmatched,'max')

M = 3×2

     1     1
     2     2
     3     4

uR =

  0x1 empty double column vector

uC = 2×1

     3
     5

So it has calculated it all in the end really. Let’s make our table with answers once again.

There are probably left example with unmatched rows and columns and their indexes, but that is way too much for now;)