UAPTasksAssigner is a header-only C++ library designed for solving unbalanced assignment problem.The library supports solving the unbalanced assignment problem where the number of tasks does not equal the number of agents (resources):
$$\text{min} \sum_{i=1}^{m} \sum_{j=1}^{n} C_{ij} X_{ij}$$
Subject to:
- Each resource can be assigned to at most one task
$$\sum_{j=0}^{n} X_{ij} \geq 1, \quad i = 0, 1, 2, \dots, m$$- Each task must be assigned to exactly one resource:
$$\sum_{i=0}^{m} X_{ij} = 1, \quad j = 0, 1, 2, \dots, n$$- The decision variables are binary:
$$X_{ij} \in \{0, 1\}$$where:
- $C_{ij}$ represents the cost of assigning task$i$ to resource$j$.
- $X_{ij}$ is a binary variable that is 1 if task$i$ is assigned to resource$j$, and 0 otherwise.
- C++17 or later
- Eigen (version 3.3 or later)
- CMake (version 3.10 or later)
- Clone the repository:
git clone https://github.com/dimianx/UAPTasksAssigner.gitcd UAPTasksAssigner
- Run CMake:
# Create temporary folder.mkdir tempcd tempcmake ..# Install the header file and CMake module.sudo make install
- Deinstallation
# In created temporary folder.sudo xargs rm< install_manifest.txt
To use the UAPTasksAssigner, include the header and create an instance of the class. Define a cost matrix and call theassign method to get the optimal assignments of tasks to resources.The cost matrix should be of size$N \times M$ , where$N$ is the number of agents (resources) and$M$ is the number of tasks. Theassign method returns astd::unordered_map<int, std::pair<int, std::vector<int>>> where:
- The key is the agent number.
- The value is a
std::pair consisting of:- The total cost for the agent as the first element.
- A vector of task numbers assigned to the agent as the second element.
#include<iostream>#include<Eigen/Core>#include"uap_ta/tasks_assigner.hpp"intmain() { Eigen::MatrixXicost_matrix(60,130);for (int i =0; i <60; ++i)for (int j =0; j <130; ++j)cost_matrix(i, j) = (i *130 + j +1) %30 +1; uap_ta::UAPTasksAssigner assigner;auto assignments = assigner.assign(cost_matrix);for (constauto& [agent, details] : assignments) {int total_cost = details.first;const std::vector<int>& tasks = details.second; std::cout <<"Agent" << agent <<": Total Cost =" << total_cost <<", Tasks = [";for (size_t i =0; i < tasks.size(); ++i) { std::cout << tasks[i];if (i < tasks.size() -1) std::cout <<","; } std::cout <<"]" << std::endl; }return0;}