Skip to content

Generalized Assignment Problem (GAP) API Reference

Data

Data model for Generalized Assignment Problem use case.

GapData

Bases: UcData

Data for the Generalized Assignment Problem (GAP).

Each of n tasks must be assigned to exactly one of m agents. Agent j has a resource capacity b_j. Assigning task i to agent j consumes resource r_ij and yields profit p_ij. The goal is to maximize total profit subject to agent capacities.

Attributes:

  • name (Literal['generalized_assignment_problem']) –

    Identifier for this data type.

  • profit_matrix (NumPyArray) –

    Profit matrix of shape (n_tasks, n_agents). profit_matrix[i, j] is the profit of assigning task i to agent j.

  • resource_matrix (NumPyArray) –

    Resource consumption matrix of shape (n_tasks, n_agents). resource_matrix[i, j] is the resource consumed by assigning task i to agent j.

  • capacities (NumPyArray) –

    Resource capacity b_j of each agent. Length equals the number of agents.

  • task_names (list[int | str]) –

    Names for each task. Defaults to 0, 1, ....

  • agent_names (list[int | str]) –

    Names for each agent. Defaults to 0, 1, ....

Examples:

>>> data = GapData(
...     profit_matrix=[[10.0, 6.0], [5.0, 9.0]],
...     resource_matrix=[[4.0, 3.0], [2.0, 5.0]],
...     capacities=[5.0, 6.0],
... )

n_tasks: int property

Return the number of tasks.

n_agents: int property

Return the number of agents.

plot(*, ax: Axes | None = None) -> Axes

Plot the GAP profit matrix as a heatmap.

Parameters:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the GAP data.

Returns:

  • str –

    String representation of the data.

from_matrices(profit_matrix: np.ndarray, resource_matrix: np.ndarray, capacities: list[float], task_names: list[int | str] | None = None, agent_names: list[int | str] | None = None) -> GapData staticmethod

Create GapData from explicit profit and resource matrices.

Parameters:

  • profit_matrix (ndarray) –

    Profit matrix of shape (n_tasks, n_agents).

  • resource_matrix (ndarray) –

    Resource consumption matrix of shape (n_tasks, n_agents).

  • capacities (list[float]) –

    Resource capacity of each agent.

  • task_names (list[int | str] | None, default: None ) –

    Names for each task. Defaults to 0, 1, ....

  • agent_names (list[int | str] | None, default: None ) –

    Names for each agent. Defaults to 0, 1, ....

Returns:

  • GapData –

    The GAP data instance.

Examples:

>>> import numpy as np
>>> data = GapData.from_matrices(
...     profit_matrix=np.array([[10.0, 6.0], [5.0, 9.0]]),
...     resource_matrix=np.array([[4.0, 3.0], [2.0, 5.0]]),
...     capacities=[5.0, 6.0],
... )

generate_random(n_tasks: int = 4, n_agents: int = 2, seed: int | None = None) -> GapData staticmethod

Generate a random GAP instance.

Profits and resources are drawn uniformly. Capacities are scaled so that the instance is typically feasible.

Parameters:

  • n_tasks (int, default: 4 ) –

    Number of tasks, by default 4.

  • n_agents (int, default: 2 ) –

    Number of agents, by default 2.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

  • GapData –

    A randomly generated GAP instance.

Examples:

>>> data = GapData.generate_random(n_tasks=5, n_agents=3, seed=42)

Formulation

Formulation for Generalized Assignment Problem use case.

GapFormulation

Bases: UcFormulation[GapData, GapSolution]

Constraint-based formulation for the Generalized Assignment Problem.

Mathematical Formulation 
Given:
    - n tasks, indexed i = 0, ..., n-1
    - m agents, indexed j = 0, ..., m-1
    - p_ij: profit of assigning task i to agent j
    - r_ij: resource consumed by assigning task i to agent j
    - b_j: resource capacity of agent j

Decision Variables:
    x_ij in {0, 1} for each task i and agent j
        x_ij = 1 if task i is assigned to agent j.

Objective (maximize):
    maximize  sum_i sum_j p_ij * x_ij

Constraints:
    1. Each task assigned to exactly one agent:
       sum_j x_ij == 1   for all i
    2. Agent capacity:
       sum_i r_ij * x_ij <= b_j   for all j
References
  • Wikipedia: https://en.wikipedia.org/wiki/Generalized_assignment_problem

to_string(data: GapData) -> str staticmethod

Return a string describing the formulation.

Parameters:

  • data (GapData) –

    The problem data.

Returns:

  • str –

    String representation of the formulation.

formulate(data: GapData) -> Model staticmethod

Formulate the GAP using a constraint-based approach.

Parameters:

  • data (GapData) –

    The problem data.

Returns:

  • Model –

    A Luna Model ready to be solved.

Raises:

interpret(solution: Solution, data: GapData) -> GapSolution staticmethod

Extract the GAP solution from the solver result.

Parameters:

  • solution (Solution) –

    The solver solution containing variable assignments.

  • data (GapData) –

    The original problem data.

Returns:

  • GapSolution –

    Structured solution with assignment, profit, and validity.

Raises:

Solution

Solution model for Generalized Assignment Problem use case.

GapSolution

Bases: UcSolution

Solution for the Generalized Assignment Problem (GAP).

Attributes:

  • name (Literal['generalized_assignment_problem']) –

    Identifier for this solution type.

  • assignment (dict[int | str, int | str]) –

    Mapping from each task to the agent it is assigned to.

  • total_profit (float) –

    Total profit of the assignment (the maximized objective).

  • agent_loads (dict[int | str, float]) –

    Total resource consumed on each agent.

  • is_valid (bool) –

    Whether the solution is valid (every task assigned to exactly one agent and no agent capacity exceeded).

plot(data: GapData | None = None, *, ax: Axes | None = None) -> Axes

Plot the GAP solution as a task-to-agent assignment matrix.

Parameters:

  • data (GapData | None, default: None ) –

    Problem data. Required for axis labels.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

Raises:

to_string() -> str

Return a string describing the solution.

Returns:

  • str –

    String representation of the solution.

Instance

Instance model for Generalized Assignment Problem use case.

GapInstance

Bases: UcInstance[GapData, GapFormulation, GapSolution]

Instance combining data and formulation for the Generalized Assignment Problem.

Collection

Collection of Generalized Assignment Problem instances.

GapCollection

Bases: UcInstanceCollection[GapInstance]

Collection of Generalized Assignment Problem instances.

This collection provides methods to generate benchmark instances with various characteristics for testing and evaluation.

from_random(min_tasks: int | None = None, max_tasks: int | None = None, n_agents: int = 2, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> GapCollection classmethod

Generate random Generalized Assignment Problem instances.

Parameters:

  • min_tasks (int | None, default: None ) –

    Minimum number of tasks.

  • max_tasks (int | None, default: None ) –

    Maximum number of tasks.

  • n_agents (int, default: 2 ) –

    Number of agents, by default 2.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

  • sizes (Sequence[int] | None, default: None ) –

    Explicit sizes to generate, e.g. [10, 50, 100], instead of a range. Mutually exclusive with min_tasks/max_tasks, by default None.

Returns:

Examples:

>>> collection = GapCollection.from_random(
...     min_tasks=3,
...     max_tasks=4,
...     num_instances=2,
...     seed=42,
... )

filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]

Drop the instances of this collection that have no feasible solution.

Every instance is formulated and handed to SCIP, which stops as soon as it finds the first feasible solution. An instance is removed from the collection when SCIP proves the model infeasible, when no solution turns up within max_runtime, or when formulating it fails altogether. This keeps randomly generated instances from breaking a downstream pipeline.

Parameters:

  • max_runtime (float, default: 3600 ) –

    SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.

  • quiet (bool, default: True ) –

    Suppress the SCIP solver output.

Returns:

  • list[bool] –

    Feasibility mask over the instances as they were before filtering, in that order: True where the instance was kept, False where it was removed.

Raises: