Combinatorial Problems¶

graphfla.problems also provides random instances of classic NP-hard optimization problems. Each problem encodes a solution as \(n\) binary variables and defines fitness so that larger values are better. Synthetic landscapes from evolutionary biology are documented under Biological Models.

Every problem is a subclass of OptimizationProblem and is used the same way. Create an instance, then call evaluate(config) for a single configuration, or get_data() to enumerate all \(2^n\) binary configurations with their fitness values. The output of get_data() can be passed directly to BooleanLandscape.build_from_data. Higher fitness is better for every problem.

Cost of full enumeration

get_data() returns \(2^n\) rows, which is practical up to about \(n = 20\). For larger \(n\), evaluate configurations individually with evaluate(), or stream them with iter_data().

Overview¶

API	Purpose
`Max3Sat`	Random 3-SAT formula; fitness is the number of satisfied clauses.
`Knapsack`	0/1 knapsack with a configurable coupling between item weights and values.
`NumberPartitioning`	Two-way partitioning of random integers, following Mertens (1998).

Max-3-SAT¶

Max-3-SAT asks for an assignment of \(n\) Boolean variables that satisfies as many clauses of a 3-CNF formula as possible. Fitness is the number of satisfied clauses.

An instance contains \(m = \lfloor \alpha n \rfloor\) distinct clauses. Each clause has three literals on three different variables, and each literal is negated with probability one half.

graphfla.problems.Max3Sat(
    n: int, alpha: float, seed: Optional[int] = None
)

Max-3-SAT problem with uniformly sampled distinct clauses.

ParametersAttributesMethodsExamples

Parameters

n : int: Number of Boolean variables. Must be at least 3.
alpha : float: Positive, finite clause-to-variable ratio. The number of clauses is floor(alpha * n), which must not exceed 8 * comb(n, 3). Ratios giving zero clauses are allowed and yield zero fitness.
seed : int or None, default=None: Seed for the instance's random number generator. An integer gives reproducible clauses, sampled at construction. None uses system-provided randomness.

Attributes

m : int: Number of clauses.
clauses : list of tuple: Each clause contains three (variable_index, is_positive) literals with distinct zero-based indices in ascending order.

Find a method

evaluate()

evaluate(config: Union[str, Sequence[int]]) -> int

Return the fitness of one configuration.

ParametersReturnsRaises

Parameters

config : str or array-like of shape (n,): Binary string of length n, or assignments encoded as 0/1 or booleans.

Returns

fitness : int: Number of satisfied clauses, between 0 and m inclusive.

Raises

ValueError: If config does not contain n binary values.

iter_data()

Inherited from OptimizationProblem

iter_data() -> Iterator[Tuple[str, Union[int, float]]]

Yield binary configurations and fitness values one at a time.

YieldsExamplesNotes

Yields

config : str: Binary string of length n, in ascending binary order.
fitness : int or float: Fitness of config, with the scalar type returned by evaluate.

Examples

>>> from itertools import islice
>>> from graphfla.problems import Eggbox
>>> list(islice(Eggbox(n=15).iter_data(), 2))
[('000000000000000', 0.0), ('000000000000001', 1.0)]

Notes

Iteration avoids storing the output lists and can be stopped early. Model-specific random-value caches still grow as configurations are visited, and complete enumeration still takes exponential time.

get_data()

Inherited from OptimizationProblem

get_data() -> Tuple[List[str], List[Union[int, float]]]

Return all binary configurations and their fitness values.

ReturnsExamplesNotesRaises

Returns

X : list of str of length 2**n: Binary strings of length n, in ascending binary order, from all zeros to all ones.
f : list of int or float of length 2**n: Fitness values aligned with X. Scalar types match evaluate.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> X, f = problem.get_data()
>>> X
['00', '01', '10', '11']
>>> f[1] == problem.evaluate(X[1])
True

Notes

This method materializes all 2**n configurations. Time and memory grow exponentially with n; use evaluate for selected configurations in larger problems. Existing random-value caches are retained.

Raises

NotImplementedError: If the subclass does not implement evaluate.
MemoryError: If the complete search space cannot be allocated.

Examples

>>> from graphfla.problems import Max3Sat
>>> problem = Max3Sat(n=3, alpha=8 / 3, seed=0)
>>> len(problem.clauses)
8
>>> problem.evaluate([False, True, False])
7

0/1 Knapsack¶

The 0/1 knapsack problem asks for a subset of \(n\) items with the largest total value whose total weight does not exceed the capacity. Item weights are integers drawn uniformly from 1 to 100, and the correlation parameter controls how item values are generated from the weights.

Fitness is the total value of the selected items. A selection that exceeds the capacity has fitness 0.

graphfla.problems.Knapsack(
    n: int,
    capacity_ratio: float = 0.5,
    correlation: float = 0.0,
    seed: Optional[int] = None,
)

Random 0-1 knapsack problem with a zero penalty for infeasible selections.

ParametersAttributesMethodsExamplesNotes

Parameters

n : int: Number of items. Must be positive.
capacity_ratio : float, default=0.5: Capacity as a fraction of total item weight, in (0, 1]. Capacity is rounded down to an integer and may be zero.
correlation : float, default=0.0: Weight-value coupling parameter, in [-1, 1], not a target Pearson correlation. Values with absolute magnitude below 0.01 select independent weights and values; other values control the formulas below.
seed : int or None, default=None: Seed for the instance's random number generator. An integer gives reproducible items, sampled at construction. None uses system-provided randomness.

Attributes

weights : list of int: Item weights, sampled uniformly from 1 through 100 inclusive.
values : list of int: Positive item values, generated according to correlation.
capacity : int: Maximum allowed total weight, floor(capacity_ratio * sum(weights)).

Find a method

evaluate()

evaluate(config: Union[str, Sequence[int]]) -> float

Return the fitness of one configuration.

ParametersReturnsRaises

Parameters

config : str or array-like of shape (n,): Binary string of length n, or selections encoded as 0/1 or booleans. One selects an item.

Returns

fitness : float: Total selected value if weight is at most capacity; zero otherwise.

Raises

ValueError: If config does not contain n binary values.

iter_data()

Inherited from OptimizationProblem

iter_data() -> Iterator[Tuple[str, Union[int, float]]]

Yield binary configurations and fitness values one at a time.

YieldsExamplesNotes

Yields

config : str: Binary string of length n, in ascending binary order.
fitness : int or float: Fitness of config, with the scalar type returned by evaluate.

Examples

>>> from itertools import islice
>>> from graphfla.problems import Eggbox
>>> list(islice(Eggbox(n=15).iter_data(), 2))
[('000000000000000', 0.0), ('000000000000001', 1.0)]

Notes

Iteration avoids storing the output lists and can be stopped early. Model-specific random-value caches still grow as configurations are visited, and complete enumeration still takes exponential time.

get_data()

Inherited from OptimizationProblem

get_data() -> Tuple[List[str], List[Union[int, float]]]

Return all binary configurations and their fitness values.

ReturnsExamplesNotesRaises

Returns

X : list of str of length 2**n: Binary strings of length n, in ascending binary order, from all zeros to all ones.
f : list of int or float of length 2**n: Fitness values aligned with X. Scalar types match evaluate.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> X, f = problem.get_data()
>>> X
['00', '01', '10', '11']
>>> f[1] == problem.evaluate(X[1])
True

Notes

This method materializes all 2**n configurations. Time and memory grow exponentially with n; use evaluate for selected configurations in larger problems. Existing random-value caches are retained.

Raises

NotImplementedError: If the subclass does not implement evaluate.
MemoryError: If the complete search space cannot be allocated.

Examples

>>> from graphfla.problems import Knapsack
>>> problem = Knapsack(n=3, capacity_ratio=0.5, seed=0)
>>> problem.evaluate([0, 0, 0])
0.0
>>> problem.evaluate([1, 1, 1])
0.0
>>> problem.evaluate([1, 0, 0]) == float(problem.values[0])
True

Notes

For |correlation| < 0.01, values are independent uniform integers from 1 through 100. Otherwise, with w the weight, c the correlation parameter and u uniform on [-10, 10], values are int(w + 10 + (1-c)*u) for c > 0 and max(1, int(100 - w + (1+c)*u)) for c < 0. These are generation conventions, not constraints on the realized sample correlation.

Number Partitioning¶

The number partitioning problem asks for a division of \(n\) positive integers into two subsets whose sums are as close as possible. Fitness is the negative absolute difference between the two sums, so a perfect partition has fitness 0.

Following Mertens (1998), the integers are drawn uniformly from 1 to \(2^{b} - 1\), where \(b = \lfloor \alpha n \rfloor\) is the number of bits per integer. The problem has a phase transition near \(\alpha = 1\). For smaller \(\alpha\), perfect partitions are numerous and easy to find. For larger \(\alpha\), a perfect partition is unlikely to exist and the best partition is hard to find.

graphfla.problems.NumberPartitioning(
    n: int, alpha: float = 1.0, seed: Optional[int] = None
)

Random integer partitioning problem expressed as fitness maximization.

ParametersAttributesMethodsExamples

Parameters

n : int: Number of integers to partition. Must be positive.
alpha : float, default=1.0: Positive, finite ratio of bit precision to number of elements. The bit precision is floor(alpha * n), which must be at least one.
seed : int or None, default=None: Seed for the instance's random number generator. An integer gives reproducible numbers, sampled at construction. None uses system-provided randomness.

Attributes

bit_precision : int: Number of bits used for generated integers.
numbers : list of int: n independent uniform integers from 1 through 2**bit_precision - 1 inclusive. Repeated values are allowed.
total_sum : int: Sum of all generated integers.

Find a method

evaluate()

evaluate(config: Union[str, Sequence[int]]) -> int

Return the fitness of one configuration.

ParametersReturnsRaises

Parameters

config : str or array-like of shape (n,): Binary string of length n, or assignments encoded as 0/1 or booleans. Zero selects the first subset and one selects the second.

Returns

fitness : int: Negative absolute difference between subset sums. Zero is optimal; integer arithmetic preserves the full precision of generated values.

Raises

ValueError: If config does not contain n binary values.

iter_data()

Inherited from OptimizationProblem

iter_data() -> Iterator[Tuple[str, Union[int, float]]]

Yield binary configurations and fitness values one at a time.

YieldsExamplesNotes

Yields

config : str: Binary string of length n, in ascending binary order.
fitness : int or float: Fitness of config, with the scalar type returned by evaluate.

Examples

>>> from itertools import islice
>>> from graphfla.problems import Eggbox
>>> list(islice(Eggbox(n=15).iter_data(), 2))
[('000000000000000', 0.0), ('000000000000001', 1.0)]

Notes

Iteration avoids storing the output lists and can be stopped early. Model-specific random-value caches still grow as configurations are visited, and complete enumeration still takes exponential time.

get_data()

Inherited from OptimizationProblem

get_data() -> Tuple[List[str], List[Union[int, float]]]

Return all binary configurations and their fitness values.

ReturnsExamplesNotesRaises

Returns

X : list of str of length 2**n: Binary strings of length n, in ascending binary order, from all zeros to all ones.
f : list of int or float of length 2**n: Fitness values aligned with X. Scalar types match evaluate.

Examples

>>> from graphfla.problems import Additive
>>> problem = Additive(n=2, seed=0)
>>> X, f = problem.get_data()
>>> X
['00', '01', '10', '11']
>>> f[1] == problem.evaluate(X[1])
True

Notes

This method materializes all 2**n configurations. Time and memory grow exponentially with n; use evaluate for selected configurations in larger problems. Existing random-value caches are retained.

Raises

NotImplementedError: If the subclass does not implement evaluate.
MemoryError: If the complete search space cannot be allocated.

Examples

>>> from graphfla.problems import NumberPartitioning
>>> problem = NumberPartitioning(n=3, seed=0)
>>> problem.numbers
[7, 4, 7]
>>> problem.evaluate([0, 1, 0])
-10
>>> problem.evaluate([1, 0, 1])
-10

References¶

Stephan Mertens, "Phase transition in the number partitioning problem", Phys. Rev. Lett. (1998).
David S. Johnson, "The NP-completeness column: An ongoing guide", J. Algorithms (1981).

Combinatorial Problems¶

Overview¶

Max-3-SAT¶

See Also

Examples

Notes

See Also

Examples

Notes

Examples

0/1 Knapsack¶

See Also

Examples

Notes

See Also

Examples

Notes

Examples

Notes

Number Partitioning¶

See Also

Examples

Notes

See Also

Examples

Notes

Examples

References¶