5 Generalized Assignment Problem

5.1 Problem Statement

Formally, the Generalized Assignment Problem can be defined as follows:

Given:

A set of tasks, \(T = \{1, 2, ..., n\}\)
A set of agents, \(A = \{1, 2, ..., m\}\)
For each task \(i\) and agent \(j\), a cost or profit \(c_{ij}\) associated with assigning task \(i\) to agent \(j\)
For each task \(i\) and agent \(j\), a resource requirement \(r_{ij}\) specifying the amount of resource needed from agent \(j\) to complete task \(i\)
For each agent \(j\), a capacity \(b_j\) specifying the maximum amount of resource that agent \(j\) can contribute

The goal is to find an assignment of tasks to agents that minimizes the total cost or maximizes the total profit, while ensuring that each task is assigned to one or more agents, and the total resource requirement of each agent does not exceed its capacity.

Mathematically, the GAP can be formulated as an integer linear programming problem. One possible formulation is as follows:

\[ \begin{aligned} \text{min.} &\quad \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij} x_{ij} \label{gap-obj}\\ \text{s.t.} &\quad \sum_{j=1}^{m} x_{ij} = 1, \ \forall i = 1, 2, ..., n \label{gap-cons1}\\ &\quad \sum_{i=1}^{n} r_{ij} x_{ij} \leq b_j, \ \forall j = 1, 2, ..., m \label{gap-cons2}\\ &\quad x_{ij} \in \{0, 1\}, \ \forall i = 1, 2, ..., n, j = 1, 2, ..., m \label{gap-cons3} \end{aligned} \]

where \(x_{ij}\) is a binary decision variable that equals 1 if task \(i\) is assigned to agent \(j\), and 0 otherwise.

The first set of constraints ensures that each task is assigned to exactly one agent, and the second set of constraints ensures that the total resource requirement of each agent does not exceed its capacity.

Solving the GAP can be computationally challenging, especially for large instances, as it is a generalization of the classic assignment problem, which is known to be polynomial-time solvable. Various algorithms and heuristics, such as branch and bound, dynamic programming, and approximation algorithms, can be employed to find feasible or optimal solutions to the GAP.

5.2 Benchmarking Problems

There are benchmarking problems available here. Listing 5.1 shows one of the instance file with five instances in it.

Listing 5.1: GAP instance

gap1.txt

 5
 5 15
 17 21 22 18 24 15 20 18 19 18 16 22 24 24 16
 23 16 21 16 17 16 19 25 18 21 17 15 25 17 24
 16 20 16 25 24 16 17 19 19 18 20 16 17 21 24
 19 19 22 22 20 16 19 17 21 19 25 23 25 25 25
 18 19 15 15 21 25 16 16 23 15 22 17 19 22 24
 8 15 14 23 8 16 8 25 9 17 25 15 10 8 24
 15 7 23 22 11 11 12 10 17 16 7 16 10 18 22
 21 20 6 22 24 10 24 9 21 14 11 14 11 19 16
 20 11 8 14 9 5 6 19 19 7 6 6 13 9 18
 8 13 13 13 10 20 25 16 16 17 10 10 5 12 23
 36 34 38 27 33
 5 15
 19 23 24 20 20 25 16 21 24 15 17 17 20 20 20
 25 24 16 21 19 17 17 19 23 21 21 23 20 15 16
 16 21 25 22 24 24 16 17 15 18 15 17 18 24 18
 25 24 18 19 15 18 20 22 23 18 16 19 17 15 22
 25 19 21 22 20 15 20 19 18 18 17 23 17 25 25
 16 12 8 20 18 10 12 8 14 23 19 14 15 15 24
 16 18 19 22 13 20 9 7 25 10 20 13 11 15 16
 6 20 20 5 14 12 6 15 22 18 13 23 23 18 25
 18 23 25 17 25 13 23 23 13 20 20 23 17 19 24
 12 17 15 25 22 5 24 19 12 25 23 21 23 19 18
 36 37 38 48 44
 5 15
 22 21 16 17 21 15 17 22 22 25 18 20 24 15 22
 23 24 19 15 16 21 15 25 16 21 20 19 16 23 20
 21 20 21 25 21 20 21 19 17 16 25 19 15 15 15
 17 21 25 25 23 22 20 19 20 25 15 20 21 25 23
 15 25 23 19 17 17 25 24 24 17 24 19 18 19 16
 23 10 15 13 17 10 13 6 9 21 20 7 9 25 8
 17 13 8 23 11 18 7 22 13 5 24 24 15 10 22
 22 17 22 23 20 11 17 25 23 9 22 20 15 9 25
 5 19 25 16 15 10 18 9 11 20 7 21 15 8 25
 22 9 10 23 19 21 17 15 15 17 25 19 10 9 21
 32 37 44 35 40
 5 15
 15 25 20 18 19 21 18 22 24 15 25 17 17 15 22
 20 18 25 25 16 24 22 24 17 18 23 25 21 25 24
 25 19 18 18 23 18 15 22 23 16 25 22 22 15 16
 19 19 23 17 19 19 22 19 23 22 24 22 25 19 16
 25 24 17 19 25 19 23 19 25 15 19 21 18 19 22
 20 20 18 9 18 5 16 18 13 24 21 23 15 19 9
 5 12 18 8 22 19 19 11 7 19 20 17 21 25 5
 18 8 8 9 20 20 23 13 15 12 6 12 25 25 23
 17 19 24 9 16 22 10 17 12 17 15 21 16 18 6
 14 6 20 6 21 5 11 23 20 21 20 18 13 13 21
 39 36 37 38 37
 5 15
 25 25 18 24 20 19 25 24 23 15 18 18 25 15 22
 25 18 17 22 21 23 20 23 16 19 15 18 16 23 16
 18 16 19 15 15 18 15 20 19 24 22 20 25 16 21
 18 21 16 18 17 24 18 23 22 16 17 22 22 18 16
 17 18 15 21 23 21 24 23 20 22 19 15 22 22 25
 16 20 9 22 17 19 20 22 20 13 6 20 23 19 7
 12 22 18 18 6 13 17 17 17 14 20 12 17 14 22
 5 19 19 14 24 16 7 8 9 22 13 23 24 15 20
 20 8 6 9 5 17 23 18 14 12 14 17 15 23 21
 6 6 24 24 8 7 5 25 21 18 12 20 20 7 12
 40 38 38 35 34

Listing 5.2 contains the Java class to hold the content of an instance. The class contains a couple of key information:

numTasks: the total number of tasks in the instance.
numAgents: the total number of agents available to process the tasks.
costs: a two-dimensional array with costs[i][j] representing the cost of assigning task j to agent i.
resources: a two-dimensional array with resources[i][j] representing the resource requirement of assigning task j to agent i.
capacities: a one-dimensional array with capacities[i] representing the capacity of agent i.

Listing 5.2: GAP instance class

GapInstance.java

package com.voyager.opt.metaheuristics.gap;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;

@Data
@Builder
@AllArgsConstructor
public class GapInstance {
  /**
   * total number of tasks
   */
  private int numTasks;
  /**
   * total number of agents
   */
  private int numAgents;
  /**
   * costs of assigning tasks to agents
   * dimension: numAgents * numTasks
   */
  private int[][] costs;
  /**
   * resource consumption of assigning tasks to agents
   * dimension: numAgents * numTasks
   */
  private int[][] resources;
  /**
   * agent capacities
   * dimension: numAgents
   */
  private int[] capacities;
}

Listing 5.3 gives a Java class that reads the instance file and outputs a list of GapInstance objects.

Listing 5.3: GAP instance reader class

GapInstanceReader.java

package com.voyager.opt.metaheuristics.gap;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public final class GapInstanceReader {

  /**
   * read instance filePath and return all the contained instances
   * @param filePath instance filename
   * @return list of instances
   */
  public static List<GapInstance> read(String filePath) {
    List<GapInstance> instances = new ArrayList<>();
    try {
      BufferedReader reader = new BufferedReader(new FileReader(filePath));
      int numInstances = Integer.parseInt(reader.readLine().trim());

      for (int p = 0; p < numInstances; p++) {
        String[] mn = reader.readLine().trim().split(" ");
        int numAgents = Integer.parseInt(mn[0]); // Number of agents
        int numTasks = Integer.parseInt(mn[1]); // Number of tasks

        // Reading costs
        int[][] costs = new int[numAgents][numTasks];
        for (int i = 0; i < numAgents; i++) {
          String[] costsLine = reader.readLine().trim().split(" ");
          for (int j = 0; j < numTasks; j++) {
            costs[i][j] = Integer.parseInt(costsLine[j]);
          }
        }

        // Reading resources
        int[][] resources = new int[numAgents][numTasks];
        for (int i = 0; i < numAgents; i++) {
          String[] resourcesLine = reader.readLine().trim().split(" ");
          for (int j = 0; j < numTasks; j++) {
            resources[i][j] = Integer.parseInt(resourcesLine[j]);
          }
        }

        // Reading resource capacities
        int[] agentCapacities = new int[numAgents];
        String[] capacitiesLine = reader.readLine().trim().split(" ");
        for (int i = 0; i < numAgents; i++) {
          agentCapacities[i] = Integer.parseInt(capacitiesLine[i]);
        }

        GapInstance instance = GapInstance.builder()
          .numTasks(numTasks)
          .numAgents(numAgents)
          .costs(costs)
          .resources(resources)
          .capacities(agentCapacities)
          .build();
        instances.add(instance);
      }
      reader.close();
    } catch (IOException e) {
      e.printStackTrace();
    }
    return instances;
  }
}