netoptim package

Submodules

netoptim.network_oracle module

netoptim.network_oracle.Cut

A cutting plane represented as a tuple of (gradient, intercept).

The gradient is typically a vector representing the subgradient of the objective function, and the intercept is the constant term in the linear cut.

alias of Tuple[Any, float]

netoptim.network_oracle.Graph

A directed graph represented as an adjacency dictionary.

The outer dict maps each node to a dict of its neighbors. Each neighbor maps to either a dict of edge attributes (e.g., {‘w’: weight}) or a tuple of (source, target) edge information.

alias of Dict[Any, Dict[Any, Dict[str, Any] | Tuple[Any, Any]]]

class netoptim.network_oracle.NetworkOracle(gra: Dict[Any, Dict[Any, Dict[str, Any] | Tuple[Any, Any]]], u: Dict[Any, int], oracle: Any)

Bases: object

Oracle for Parametric Network Problem:

The NetworkOracle class represents an oracle for solving a parametric network problem, where the goal is to find values for variables x and u that satisfy certain constraints.

find x, u

s.t. u[j] − u[i] ≤ oracle(edge, x)

∀ edge(i, j) ∈ E

Examples

>>> from unittest.mock import Mock
>>> gra = {
...     "v1": {"v2": {"w": 3}, "v3": {"w": 4}},
...     "v2": {"v1": {"w": -2}, "v3": {"w": 1}},
...     "v3": {"v1": {"w": -3}, "v2": {"w": -2}},
... }
>>> u = {"v1": 0, "v2": 0, "v3": 0}
>>> oracle = Mock()
>>> oracle.eval.side_effect = lambda e, x: e["w"] - x
>>> oracle.grad.side_effect = lambda e, x: -1
>>> network = NetworkOracle(gra, u, oracle)
>>> network.assess_feas(1)
(2, 3)

assess_feas(x: Any) → Tuple[Any, float] | None

Assess feasibility and generate a cutting plane if infeasible.

This method implements the feasibility oracle for the parametric network problem. It searches for negative cycles in the graph using Howard’s algorithm. If a negative cycle exists, it returns a cutting plane (gradient, intercept) to cut off the infeasible point.

Parameters:

x – The current iterate value to assess for feasibility.

Returns:

A Cut tuple (gradient, intercept) if the point is infeasible (negative cycle exists), or None if feasible.

update(t: float) → None

Update the oracle with the best-so-far optimal value.

This method notifies the underlying oracle about the current best feasible solution value, which may be used to refine cutting planes.

Parameters:

t – The best-so-far optimal value to update the oracle with.

netoptim.optscaling_oracle module

netoptim.optscaling_oracle.Arr

A NumPy array type alias for array operations in the optimization.

netoptim.optscaling_oracle.Cut

A cutting plane represented as a tuple of (gradient array, intercept).

The gradient is a NumPy array representing the subgradient, and the intercept is a scalar constant term.

alias of Tuple[ndarray, float]

class netoptim.optscaling_oracle.OptScalingOracle(gra: Any, utx: Any, get_cost: Any)

Bases: OracleOptim[ndarray]

Oracle for Optimal Matrix Scaling

This example is taken from[Orlin and Rothblum, 1985]

min π/ψ

s.t. ψ ≤ u[i] * |a_ij| * u[j]^{−1} ≤ π,

∀ (i,j) ∈ E,

π, ψ, utx, positive

class Ratio(gra: Any, get_cost: Any)

Bases: object

Inner class for computing ratio constraints in matrix scaling.

This class evaluates the constraint ψ ≤ u[i] * |a_ij| * u[j]^{-1} ≤ π by computing the minimum of two differences in logarithmic scale.

eval(edge, x: ndarray) → float

Evaluate the ratio constraint for an edge.

Computes min(π - a_ji, a_ij - ψ) where x = (π, ψ) in log scale. A positive result indicates the constraint is satisfied.

Parameters:

• edge – The edge (i, j) to evaluate.

• x – The current iterate (π, ψ) in logarithmic scale.

Returns:

The minimum of the two ratio differences.

grad(edge, x: ndarray) → ndarray

Compute the subgradient of the ratio constraint.

Returns a subgradient vector indicating which bound is active: - [1.0, 0.0] if the upper bound (π) is active - [0.0, -1.0] if the lower bound (ψ) is active

Parameters:

• edge – The edge (i, j) to evaluate.

• x – The current iterate (π, ψ) in logarithmic scale.

Returns:

A 2-element NumPy array representing the subgradient.

assess_optim(xc: ndarray, gamma: float) → Tuple[Tuple[ndarray, float], float | None]

Make object callable for cutting_plane_optim()

Parameters:

• xc (Arr) – (π, ψ) in log scale

• gamma (float) – the best-so-far optimal value

Returns:

Tuple[Cut, Optional[float]]

Examples

>>> from mywheel.map_adapter import MapAdapter
>>> gra = MapAdapter([{}, {0: (1.0, 1.0)}])
>>> utx = [0.0, 0.0]
>>> def get_cost(edge):
...     return 1.0, 1.0
>>> oracle = OptScalingOracle(gra, utx, get_cost)
>>> x = np.array([0.0, 0.0])
>>> t = 0.0
>>> cut, t1 = oracle.assess_optim(x, t)
>>> cut[0]
array([ 1., -1.])
>>> cut[1]
0.0
>>> import numpy as np
>>> bool(np.isclose(t1, 0.0))
True

>>> x = np.array([1.0, 0.0])
>>> t = 0.0
>>> cut, t1 = oracle.assess_optim(x, t)
>>> cut[0]
array([ 1., -1.])

See also

cutting_plane_optim

Module contents