Generalized Assignment Problem (GAP) Example

Download Notebook

The Generalized Assignment Problem assigns each of n tasks to exactly one of m capacity-limited agents. Assigning a task to an agent consumes a resource and yields a profit; the goal is to maximize total profit while respecting each agent's resource capacity. It is NP-hard and models scheduling, logistics, and resource allocation.

import getpass
import os

import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.generalized_assignment_problem import (
    GapCollection,
    GapData,
    GapFormulation,
    GapInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Build an instance from explicit profit and resource matrices using the from_matrices factory.

data = GapData.from_matrices(
    profit_matrix=np.array(
        [
            [10.0, 6.0, 1.0],
            [5.0, 9.0, 2.0],
            [4.0, 3.0, 8.0],
            [7.0, 2.0, 6.0],
        ]
    ),
    resource_matrix=np.array(
        [
            [4.0, 3.0, 2.0],
            [2.0, 5.0, 3.0],
            [3.0, 2.0, 4.0],
            [4.0, 3.0, 2.0],
        ]
    ),
    capacities=[7.0, 8.0, 6.0],
)
print(data.to_string())

Generalized Assignment Problem Data:
  Tasks: 4
  Agents: 3
  Capacities: ['7.0', '8.0', '6.0']
  Profit range: [1.0, 10.0]

Plot Data

Visualize the profit matrix as a heatmap.

data.plot()

<Axes: title={'center': 'GAP — 4 tasks, 3 agents'}, xlabel='Agent', ylabel='Task'>

Create Formulation

Maximize total profit subject to each task being assigned once and agent capacities.

formulation = GapFormulation()
print(formulation.to_string(data))

Generalized Assignment Problem Formulation:
  Tasks: 4
  Agents: 3

Parameters:
  p_ij = profit of assigning task i to agent j (profit_matrix)
  r_ij = resource consumed by assigning task i to agent j (resource_matrix)
  b_j  = resource capacity of agent j (capacities)

Decision Variables:
  x_ij in {0,1} for i = 0, ..., 3 (tasks), j = 0, ..., 2 (agents)
  x_ij = 1 if task i is assigned to agent j
  Total: 12 binary variables

Objective:
  maximize  sum_i sum_j p_ij * x_ij

Constraints:
  1. Assignment: sum_j x_ij == 1 for all i  (4 constraints)
  2. Capacity: sum_i r_ij * x_ij <= b_j for all j  (3 constraints)

Create Instance

Combine data and formulation into a solvable instance.

instance = GapInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Generalized Assignment Problem Data:
  Tasks: 4
  Agents: 3
  Capacities: ['7.0', '8.0', '6.0']
  Profit range: [1.0, 10.0]
Formulation:Generalized Assignment Problem Formulation:
  Tasks: 4
  Agents: 3

Parameters:
  p_ij = profit of assigning task i to agent j (profit_matrix)
  r_ij = resource consumed by assigning task i to agent j (resource_matrix)
  b_j  = resource capacity of agent j (capacities)

Decision Variables:
  x_ij in {0,1} for i = 0, ..., 3 (tasks), j = 0, ..., 2 (agents)
  x_ij = 1 if task i is assigned to agent j
  Total: 12 binary variables

Objective:
  maximize  sum_i sum_j p_ij * x_ij

Constraints:
  1. Assignment: sum_j x_ij == 1 for all i  (4 constraints)
  2. Capacity: sum_i r_ij * x_ij <= b_j for all j  (3 constraints)

Formulate Model

Translate the instance into a mixed-integer optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

Waiting for result | elapsed 0:00:01 | poll 1 | next check in 0.5s

Waiting for result | elapsed 0:00:02 | poll 2 | next check in 1s

Waiting for result | elapsed 0:00:03 | poll 3 | next check in 2s

Waiting for result | elapsed 0:00:05 | poll 4 | next check in 4s

Waiting for result | elapsed 0:00:10 | poll 5 | next check in 8s

Waiting for result | elapsed 0:00:18 | poll 6 | next check in 16s

2026-08-20 11:10:46 INFO     Solve job '60aac6a3-0f4a-4a2a-b90f-9db87dcabfa0' finished with status 'DONE' after    
                             0:00:35.

Generalized Assignment Problem Solution:
  Assignments: 0 -> 0, 1 -> 1, 2 -> 2, 3 -> 2
  Total profit: 33.00
  Agent loads: 0: 4.0, 1: 5.0, 2: 6.0
  Valid: True

Plot Solution

Visualize the task-to-agent assignment.

uc_solution.plot(data)

<Axes: title={'center': 'GAP Solution — profit: 33.0, valid=True'}, xlabel='Agent', ylabel='Task'>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = GapCollection.from_random(min_tasks=3, max_tasks=4, num_instances=2, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: generalized_assignment_problem<s42_t3_i0>
Maximize
  2.8716358549829786 * x_0_0 + 3.8584655971645923 * x_0_1
  + 2.248919008072832 * x_1_0 + 7.903351786733379 * x_1_1
  + 6.4776386586482095 * x_2_0 + 1.6214616397519919 * x_2_1
Subject To
  assign_0: x_0_0 + x_0_1 == 1
  assign_1: x_1_0 + x_1_1 == 1
  assign_2: x_2_0 + x_2_1 == 1
  capacity_0: 1.0165342455067852 * x_0_0 + 3.439826327814302 * x_1_0
    + 2.0654129220050605 * x_2_0 <= 6.6744513017004135
  capacity_1: 4.697898534723379 * x_0_1 + 4.8373500476292435 * x_1_1
    + 1.7415147268556663 * x_2_1 <= 6.6744513017004135
Binary
  x_0_0 x_0_1 x_1_0 x_1_1 x_2_0 x_2_1