Device and user licences: calculating the best allocation

To optimise, we must find the minimum cost subset of the nodes that covers all the arcs (in the figure, the nodes in blue can cover everything).

This is a well-known mathematical problem known as "minimum weighted vertex coverage" which, unfortunately, is an NP-difficult problem. That is, it takes a long time to calculate its solution (hours, days, weeks).

And perhaps this is why we have not found a tool that natively implements this function.

We keep calm and use heuristics

In computer science, there is a technique designed to solve a problem faster than classical methods and it is done by prioritising speed over optimality, completeness, accuracy and precision. This technique is known as heuristics.

Luckily for us, this type of problem has an extensive study in the literature, so we had a wide range of heuristics available to choose from and began our "heuristic selection". What did we do?

• We created a real scenario with a relatively small number of users and devices (around 500). Thus, we were able to calculate the "real" minimum licence cost using a brute-force approach (basically, we tested all possible allocations and found the best one).

• Next, we tested various types of heuristics whose aim is to reach the optimal solution for a given problem • We found a Greedy algorithm (an algorithm that performs problem-solving heuristics by making the best choice for each step) that was able to calculate a good user/device licence assignment combination within seconds.

What does the algorithm look like?

The algorithm we have chosen works in this way:

1. A queue of users must be created (sorted according to the number of devices used)
2. A queue of Devices is to be created (ordered by the number of users)
3. Until both queues are empty, the algorithm proceeds as follows:
- Chooses from the top of both queues the user/device that saves the most money
- Assigns a licence to that user/device
- Removes that item from its queue
- Removes all related items from the other queue

Result

Applying this algorithm, we obtain a combination of user/device licences with a cost equal to the optimal solution, which we usually use to feed the SAM tool.

With this combination, we can periodically (quarterly) optimise the allocation of licences with zero manual effort.

By taking advantage of the algorithm's low calculation time, it is possible to keep abreast of the current situation of device usage by users and always choose the allocation that best suits the organisation's needs.

*An article co-written by Jary Busato (SAM/ITAM Consultant), Claudio Guarisco (Lead Developer) and Camilla Bottin (Marketing Specialist) of WEGG.