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.");
 }

Classes
SimpleLinearSumAssignment