Longest Path API Reference

Data

Data model for Longest Path use case.

`LongestPathData`

Bases: UcData

Data for the Longest Path use case.

Finds the longest weighted path between two nodes in a graph, visiting exactly path_length nodes.

Attributes:

Name	Type	Description
`name`	`Literal['longest_path']`	Identifier for this data type.
`adjacency_matrix`	`SymMatrix`	Weighted adjacency matrix. Entry (i, j) is the edge weight between nodes i and j, or 0 if there is no edge.
`node_names`	`list[int \| str]`	Node identifiers.
`start_node`	`int \| str`	Node where the path must begin.
`terminal_node`	`int \| str`	Node where the path must end.
`path_length`	`int`	Number of nodes in the path (including start and end).

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

Plot the Longest Path graph instance.

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`

Format the data as a human-readable string.

Returns:

Type	Description
`str`	String representation of the data.

`from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str], start_node: int | str, terminal_node: int | str, path_length: int) -> LongestPathData` `staticmethod`

Create LongestPathData from an adjacency matrix.

Parameters:

Name	Type	Description	Default
`adjacency_matrix`	`ndarray`	Weighted adjacency matrix.	required
`node_names`	`list[int \| str]`	List of node identifiers.	required
`start_node`	`int \| str`	Node where the path begins.	required
`terminal_node`	`int \| str`	Node where the path ends.	required
`path_length`	`int`	Number of nodes in the path (including start and end).	required

Returns:

Type	Description
`LongestPathData`	The Longest Path data instance.

Raises:

Type	Description
`ValueError`	If the matrix is not square, not symmetric, has a non-zero diagonal, or if node_names length doesn't match the matrix, node_names contains duplicates, or start/terminal nodes are not in node_names.

`generate_random(n_nodes: int = 5, edge_prob: float = 0.5, path_length: int = 3, seed: int | None = None) -> LongestPathData` `staticmethod`

Generate a random Longest Path instance.

Parameters:

Name	Type	Description	Default
`n_nodes`	`int`	Number of nodes, by default 5.	`5`
`edge_prob`	`float`	Probability of an edge between any two nodes, by default 0.5.	`0.5`
`path_length`	`int`	Number of nodes in the path, by default 3.	`3`
`seed`	`int \| None`	Random seed for reproducibility, by default None.	`None`

Returns:

Type	Description
`LongestPathData`	A randomly generated data instance.

Examples:

>>> data = LongestPathData.generate_random(n_nodes=6, seed=42)

Formulation

Formulation for Longest Path use case.

`LongestPathFormulation`

Bases: UcFormulation[LongestPathData, LongestPathSolution]

Constraint-based formulation for Longest Path.

Mathematical Formulation

Decision Variables:
    x[i, p] in {0, 1} -- 1 if node i is at position p in the path.
    Note: x[start, 0] and x[terminal, L-1] are treated as constants (= 1)
    and are not added as model variables.

Objective:
    maximize sum over p in 0..L-2 of sum over edges (i,j) of
    w_ij * x[i,p] * x[j,p+1]

Constraints:
    1. Each position has exactly one node: sum_i x[i,p] == 1 for all p.
    2. Each node is used at most once: sum_p x[i,p] <= 1 for all i.
    3. Consecutive nodes must be connected:
       for non-edges (i,j): x[i,p] + x[j,p+1] <= 1 for all p.

Note: The start and terminal constraints are eliminated by substitution:
x[start, 0] = 1 and x[terminal, L-1] = 1 are treated as constants,
reducing the number of variables by 2 and removing 2 equality constraints.

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

Format the formulation as a string.

Parameters:

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

Returns:

Type	Description
`str`	Formatted description of the formulation.

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

Formulate the Longest Path problem as a constraint-based model.

Start and terminal nodes are treated as constants (x[start, 0] = 1 and x[terminal, L-1] = 1) and are not added as model variables. This reduces the number of variables by 2 and eliminates 2 equality constraints.

Variables

x[i, p] : binary 1 if node i occupies position p in the path, 0 otherwise. i : int Node index in range [0, n-1], where n is the total number of nodes. p : int Position index in range [0, L-1], where L is the fixed path length. j : int Secondary node index, used when iterating over potential edges (i -> j).

Parameters:

Name	Type	Description	Default
`data`	`LongestPathData`	The problem data containing the graph structure.	required

Returns:

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

`interpret(solution: Solution, data: LongestPathData) -> LongestPathSolution` `staticmethod`

Extract a Longest Path solution from the solver result.

Since x[start, 0] and x[terminal, L-1] are not model variables, their values are inferred directly from the problem data rather than read from the solution sample.

Parameters:

Name	Type	Description	Default
`solution`	`Solution`	The solver solution.	required
`data`	`LongestPathData`	The original problem data.	required

Returns:

Type	Description
`LongestPathSolution`	Structured solution with path, weight, and validity.

Raises:

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

Solution

Solution model for Longest Path use case.

`LongestPathSolution`

Bases: UcSolution

Solution for the Longest Path use case.

Attributes:

Name	Type	Description
`name`	`Literal['longest_path']`	Identifier.
`path`	`list[int \| str]`	Ordered nodes in the longest path.
`total_weight`	`float`	Sum of edge weights along the path.
`is_valid`	`bool`	Whether the path is valid (connected, respects start/end, correct length).

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

Plot the Longest Path solution on the problem graph.

Path edges are highlighted in green; other edges are grey.

Parameters:

Name	Type	Description	Default
`data`	`LongestPathData \| None`	Problem data used to reconstruct the graph. Required -- a `ValueError` is raised when `None`.	`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`

Format the solution as a human-readable string.

Returns:

Type	Description
`str`	String representation of the solution.

Instance

Instance model for Longest Path use case.

`LongestPathInstance`

Bases: UcInstance[LongestPathData, LongestPathFormulation, LongestPathSolution]

Instance combining data and formulation for Longest Path.

Collection

Collection of Longest Path instances.

`LongestPathCollection`

Bases: UcInstanceCollection[LongestPathInstance]

Collection of Longest Path instances.

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

`from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> LongestPathCollection` `classmethod`

Generate random Longest Path instances.

Parameters:

Name	Type	Description	Default
`min_nodes`	`int \| None`	Minimum number of nodes.	`None`
`max_nodes`	`int \| None`	Maximum number of nodes.	`None`
`edge_prob`	`float`	Edge probability, by default 0.5.	`0.5`
`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_nodes`/`max_nodes`, by default None.	`None`

Returns:

Type	Description
`LongestPathCollection`	Collection containing generated instances.

Examples:

>>> collection = LongestPathCollection.from_random(
...     min_nodes=5,
...     max_nodes=10,
...     num_instances=3,
...     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.

Longest Path API Reference

Data

LongestPathData

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

to_string() -> str

from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str], start_node: int | str, terminal_node: int | str, path_length: int) -> LongestPathData staticmethod

generate_random(n_nodes: int = 5, edge_prob: float = 0.5, path_length: int = 3, seed: int | None = None) -> LongestPathData staticmethod

Formulation

LongestPathFormulation

to_string(data: LongestPathData) -> str staticmethod

formulate(data: LongestPathData) -> Model staticmethod

interpret(solution: Solution, data: LongestPathData) -> LongestPathSolution staticmethod

Solution

LongestPathSolution

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

to_string() -> str

Instance

LongestPathInstance

Collection

LongestPathCollection

from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> LongestPathCollection classmethod

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

`LongestPathData`

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

`to_string() -> str`

`from_adjacency_matrix(adjacency_matrix: np.ndarray, node_names: list[int | str], start_node: int | str, terminal_node: int | str, path_length: int) -> LongestPathData` `staticmethod`

`generate_random(n_nodes: int = 5, edge_prob: float = 0.5, path_length: int = 3, seed: int | None = None) -> LongestPathData` `staticmethod`

`LongestPathFormulation`

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

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

`interpret(solution: Solution, data: LongestPathData) -> LongestPathSolution` `staticmethod`

`LongestPathSolution`

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

`to_string() -> str`

`LongestPathInstance`

`LongestPathCollection`

`from_random(min_nodes: int | None = None, max_nodes: int | None = None, edge_prob: float = 0.5, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> LongestPathCollection` `classmethod`

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