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	Type	Description
`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:

Name	Type	Description	Default
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`Axes`	The axes with the plot.

`to_string() -> str`

Return a string describing the GAP data.

Returns:

Type	Description
`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:

Name	Type	Description	Default
`profit_matrix`	`ndarray`	Profit matrix of shape (n_tasks, n_agents).	required
`resource_matrix`	`ndarray`	Resource consumption matrix of shape (n_tasks, n_agents).	required
`capacities`	`list[float]`	Resource capacity of each agent.	required
`task_names`	`list[int \| str] \| None`	Names for each task. Defaults to `0, 1, ...`.	`None`
`agent_names`	`list[int \| str] \| None`	Names for each agent. Defaults to `0, 1, ...`.	`None`

Returns:

Type	Description
`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:

Name	Type	Description	Default
`n_tasks`	`int`	Number of tasks, by default 4.	`4`
`n_agents`	`int`	Number of agents, by default 2.	`2`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`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:

Name	Type	Description	Default
`data`	`GapData`	The problem data.	required

Returns:

Type	Description
`str`	String representation of the formulation.

`formulate(data: GapData) -> Model` `staticmethod`

Formulate the GAP using a constraint-based approach.

Parameters:

Name	Type	Description	Default
`data`	`GapData`	The problem data.	required

Returns:

Type	Description
`Model`	A Luna Model ready to be solved.

Raises:

Type	Description
`EmptyDataError`	If there are no tasks or no agents.

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

Extract the GAP solution from the solver result.

Parameters:

Name	Type	Description	Default
`solution`	`Solution`	The solver solution containing variable assignments.	required
`data`	`GapData`	The original problem data.	required

Returns:

Type	Description
`GapSolution`	Structured solution with assignment, profit, and validity.

Raises:

Type	Description
`NoSolutionFoundError`	If the solver did not find a solution.

Solution

Solution model for Generalized Assignment Problem use case.

`GapSolution`

Bases: UcSolution

Solution for the Generalized Assignment Problem (GAP).

Attributes:

Name	Type	Description
`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:

Name	Type	Description	Default
`data`	`GapData \| None`	Problem data. Required for axis labels.	`None`
`ax`	`Axes \| None`	Matplotlib axes to draw on. Creates a new figure if `None`.	`None`

Returns:

Type	Description
`Axes`	The axes with the plot.

Raises:

Type	Description
`ValueError`	If data is `None`.

`to_string() -> str`

Return a string describing the solution.

Returns:

Type	Description
`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:

Name	Type	Description	Default
`min_tasks`	`int \| None`	Minimum number of tasks.	`None`
`max_tasks`	`int \| None`	Maximum number of tasks.	`None`
`n_agents`	`int`	Number of agents, by default 2.	`2`
`num_instances`	`int`	Number of instances per size, by default 1.	`1`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`
`sizes`	`Sequence[int] \| None`	Explicit sizes to generate, e.g. `[10, 50, 100]`, instead of a range. Mutually exclusive with `min_tasks`/`max_tasks`, by default None.	`None`

Returns:

Type	Description
`GapCollection`	Collection containing generated instances.

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:

Name	Type	Description	Default
`max_runtime`	`float`	SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds.	`3600`
`quiet`	`bool`	Suppress the SCIP solver output.	`True`

Returns:

Type	Description
`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:

Type	Description
`ValueError`	If `max_runtime` is not positive.

Generalized Assignment Problem (GAP) API Reference

Data

GapData

n_tasks: int property

n_agents: int property

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

to_string() -> str

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

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

Formulation

GapFormulation

to_string(data: GapData) -> str staticmethod

formulate(data: GapData) -> Model staticmethod

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

Solution

GapSolution

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

to_string() -> str

Instance

GapInstance

Collection

GapCollection

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

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

`GapData`

`n_tasks: int` `property`

`n_agents: int` `property`

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

`to_string() -> str`

`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`

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

`GapFormulation`

`to_string(data: GapData) -> str` `staticmethod`

`formulate(data: GapData) -> Model` `staticmethod`

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

`GapSolution`

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

`to_string() -> str`

`GapInstance`

`GapCollection`

`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`

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