Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: assignment
Note: This documentation is automatically generated.
Simple interface to solve the linear sum assignment problem. It uses about twice as much memory as directly using the LinearSumAssignment class template, but it is as fast and presents a simpler interface. This is the class you should use in most situations.
The assignment problem: Given N "left" nodes and N "right" nodes, and a set of left->right arcs with integer costs, find a perfect matching (i.e., each "left" node is assigned to one "right" node) that minimizes the overall cost.
Example usage:
#include "ortools/graph/assignment.h"
SimpleLinearSumAssignment assignment;
for (int arc = 0; arc < num_arcs; ++arc) {
assignment.AddArcWithCost(head(arc), tail(arc), cost(arc));
}
if (assignment.Solve() == SimpleLinearSumAssignment::OPTIMAL) {
printf("A perfect matching exists.\n");
printf("The best possible cost is %d.\n", assignment.OptimalCost());
printf("An optimal assignment is:\n");
for (int node = 0; node < assignment.NumNodes(); ++node) {
printf("left node %d assigned to right node %d with cost %d.\n",
node,
assignment.RightMate(node),
assignment.AssignmentCost(node));
}
printf("Note that it may not be the unique optimal assignment.");
} else {
printf("There is an issue with the input or no perfect matching exists.");
}
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["The `SimpleLinearSumAssignment` class provides a simplified interface for solving the linear sum assignment problem, finding the minimum-cost perfect matching between two sets of nodes."],["This class uses about twice the memory of the `LinearSumAssignment` class template but offers comparable speed and easier usage."],["The assignment problem involves finding a one-to-one mapping between \"left\" and \"right\" nodes with the lowest total cost based on assigned arcs."],["Users can add arcs with associated costs, solve for the optimal assignment, and retrieve results such as the minimum cost and the specific node pairings."],["The provided example demonstrates how to use the `SimpleLinearSumAssignment` class to solve an assignment problem and check if an optimal solution exists."]]],["The `SimpleLinearSumAssignment` class solves the linear sum assignment problem, finding a minimum-cost perfect matching between N left and N right nodes connected by arcs with costs. Users add arcs with costs using `AddArcWithCost`, then call `Solve`. If `OPTIMAL`, a perfect matching exists; `OptimalCost` returns the minimum total cost. The `RightMate` function provides the assigned right node for each left node, and `AssignmentCost` the arc cost for that assignment.\n"]]
