dedekind::optimization::detail Namespace Reference

Typedefs
template<typename T>
using	LPSolutionSet
template<typename T>
using	LPSolutionIdF

Functions
template<typename T>
constexpr bool	is_singular (const T &det)
	Carrier-aware singularity predicate on the Cramer determinant.
template<typename T>
constexpr VertexCandidate< T >	solve_active_set (const HalfspaceTriple< T > &h1, const HalfspaceTriple< T > &h2)
	2×2 active-set solve for the intersection of two halfspaces, treated as equalities: a1 x + b1 y = c1, a2 x + b2 y = c2.
template<typename T>
constexpr VertexCandidate< T >	maximize_impl (std::span< const HalfspaceTriple< T > > constraints, T cx, T cy)
	Argmax over feasible vertex-candidates under the objective cx · x + cy · y. The co-Kleisli argmax on the candidate path; returns {x*, y*, true} on success, {0, 0, false} on an empty feasible set.
template<typename T>
constexpr VertexCandidate< T >	maximize_impl_axis_aligned (std::span< const HalfspaceTriple< T > > constraints, T cx, T cy)
	Bit-ops fast-path kernel for axis-aligned signed-unimodular polytopes. Sibling of maximize_impl ; same return shape, same constexpr-callable / runtime-callable bridge property.
template<typename T, T cx, T cy, typename... Hs> requires (sizeof...(Hs) >= 2) && dedekind::algebra::HasRingOperators<T>
constexpr auto	maximize_set ()
	NTTP packaging on top of maximize_with_values returning a :expressions Set whose predicate type encodes the LP's mathematical regime. Implementation of the canonical public entry argmax ; callers use argmax , not this.

Variables
template<typename H>
constexpr bool	entries_in_unit_range_v
	Per-halfspace check: (coeff_x, coeff_y) ∈ {−1, 0, +1}².
template<typename H>
constexpr bool	axis_aligned_v
	Per-halfspace check: at least one of (coeff_x, coeff_y) is zero — the halfspace is axis-aligned (constrains x or y but not both).
template<typename T>
constexpr auto	lp_step_arrow
	Shape-level F-algebra structure map on the output Set: an endomap representing the "active-set step" at the type level. Concrete LP folds close over halfspaces internally; the shape-level witness here is halfspace-agnostic, which is what F-algebra structure abstracts.

Detailed Description

lp__Structural_Classifiers

Structural properties of halfspace packs that the maximize NTTP entry uses to dispatch among the §5 triptych: the signed-unimodular fast path, the generic Cramer fold, and the static_assert refusal for infeasible packs. Algebraic gates over the halfspace family — the dispatch is driven by what the constraints are, not by what the call site says they should be.

lp__LP_Reduction_Internals

Value-level helpers used by the bridge kernel. The kernel itself (detail::maximize_impl) is one constexpr function called from both modes — the NTTP packaging maximize materialises a constexpr std::array of triples and hands its span to the single public entry maximize_with_values (folds at compile time); the runtime call site hands a std::vector-backed span to the same maximize_with_values (runs at call time). Same code path, two evaluation modes, selected by the constexpr-ness of the arguments at the call site.

lp__F_Algebra_Witness

Inline type-witness: the output Set of argmax is an F-algebra (Mac~Lane ch.~V, Pierce~1991 §5; the project's category::IsFAlgebra concept). This pins the catamorphism shape mechanically — the output Set carries a structure map F<X> → X for the carrier X = Set<Vec2V<T>, Boole, LPSolutionPredicate<T>> . The witness uses the identity endofunctor ( F(X) = X ); the catamorphism interpretation — that argmax is the unique morphism into this algebra from the initial halfspace-list F-algebra carrying the polytope's pack — additionally requires F to be the halfspace-list functor and the opt-in is_initial_f_algebra_v registration that captures the universal property's uniqueness clause (engineer's honesty obligation per category:f_algebra ; deferred here as the halfspace-list endofunctor needs its own Σ_cat / Shape / φ scaffolding).

See also [optimization:lp][f-algebra][catamorphism] in lp_test.cpp for the test-side static_assert and the parallel IsSet witness.

Typedef Documentation

LPSolutionIdF

template<typename T>

using dedekind::optimization::detail::LPSolutionIdF

Initial value:

 dedekind::category::identity_functor<
    dedekind::category::DiscreteCategory<LPSolutionSet<T>>>

LPSolutionSet

template<typename T>

using dedekind::optimization::detail::LPSolutionSet

Initial value:

 dedekind::sets::Comprehension<
    dedekind::sets::𝔸<dedekind::linear_algebra::Vec2V<T>,
                      dedekind::category::Boole>,
    LPSolutionPredicate<T>>

Function Documentation

is_singular()

template<typename T>

bool dedekind::optimization::detail::is_singular ( const T & det )

constexpr

Carrier-aware singularity predicate on the Cramer determinant.

For plain ring-like carriers (Rational<Z>, int, etc.) a determinant is singular iff it equals the additive identity. For Dual<F> (forward-mode AD) the situation is subtler: a dual of the form {val = 0, der = t} is still singular regardless of t, because the first-order primal part is what controls invertibility. A naive det == T{} check would miss this because operator== on Dual<F> compares both components and would treat {0, t} with t != 0 as non-zero.

We duck-type on the .val / .der pair to detect Dual-like carriers without adding a dedekind.numbers:dual import: any carrier exposing both fields is treated as having primal-determined singularity; everything else falls back to full equality.

maximize_impl()

template<typename T>

VertexCandidate< T > dedekind::optimization::detail::maximize_impl ( std::span< const HalfspaceTriple< T > > constraints, T cx, T cy )

constexpr

Argmax over feasible vertex-candidates under the objective cx · x + cy · y. The co-Kleisli argmax on the candidate path; returns {x*, y*, true} on success, {0, 0, false} on an empty feasible set.

One constexpr kernel for both evaluation modes. Called with a constexpr std::span (e.g. from maximize_with_values below, when maximize materialises the NTTP pack as a fixed-size std::array), the reduction folds at translation time and the optimum collapses to a typed constant. Called with a runtime std::span (e.g. over a std::vector materialised from a Python list of triples), the same function runs at runtime — same code path, same active-set enumeration, same carrier-aware is_singular check. This is the paper's two-way bridge made literal: one function, two modes, selection by the constexpr-ness of the arguments at the call site.

maximize_impl_axis_aligned()

template<typename T>

VertexCandidate< T > dedekind::optimization::detail::maximize_impl_axis_aligned ( std::span< const HalfspaceTriple< T > > constraints, T cx, T cy )

constexpr

Bit-ops fast-path kernel for axis-aligned signed-unimodular polytopes. Sibling of maximize_impl ; same return shape, same constexpr-callable / runtime-callable bridge property.

Precondition (caller's responsibility, statically gated by HasUnitRangeEntries && IsAxisAlignedPolytope at the maximize dispatch site): every halfspace in constraints has (a, b) ∈ {−1, 0, +1}² with at least one coefficient zero. Under this precondition each halfspace contributes one bound on one axis, the active set degenerates to per-axis bracketing, and the optimum vertex is selected by the sign of the objective coefficients. No multiplication or division is performed on the carrier — the IR for the runtime call reduces to comparisons, negations, and selects.

maximize_set()

template<typename T, T cx, T cy, typename... Hs>
requires (sizeof...(Hs) >= 2) && dedekind::algebra::HasRingOperators<T>

auto dedekind::optimization::detail::maximize_set ( )

constexpr

NTTP packaging on top of maximize_with_values returning a :expressions Set whose predicate type encodes the LP's mathematical regime. Implementation of the canonical public entry argmax ; callers use argmax , not this.

Same kernel dispatch as the runtime entries (signed- unimodular fast path vs generic Cramer fold), but the return is a Set whose predicate type carries the regime. When the LP is infeasible the return is a Set with :expressions::EmptyPredicate ; no static_assert fires — the empty optimum is a value of the output Set type. Callers who want compile-time refusal can static_assert on decltype(argmax(G, U)) themselves.

Lives in detail:: because argmax(G, U) is the canonical public Set DSL surface — input polytope and output optimum are both Sets end-to-end, with no NTTP-direct shortcut exposed.

solve_active_set()

template<typename T>

VertexCandidate< T > dedekind::optimization::detail::solve_active_set ( const HalfspaceTriple< T > & h1, const HalfspaceTriple< T > & h2 )

constexpr

2×2 active-set solve for the intersection of two halfspaces, treated as equalities: a1 x + b1 y = c1, a2 x + b2 y = c2.

Uses Invertible2x2's Cramer inverse if the active-set matrix is full-rank. If singular, returns an infeasible sentinel (the two halfspaces are parallel; no vertex).

Variable Documentation

axis_aligned_v

template<typename H>

bool dedekind::optimization::detail::axis_aligned_v

constexpr

Initial value:

= H::coeff_x == typename H::scalar_type{} ||
                                H::coeff_y == typename H::scalar_type{}

Per-halfspace check: at least one of (coeff_x, coeff_y) is zero — the halfspace is axis-aligned (constrains x or y but not both).

entries_in_unit_range_v

template<typename H>

bool dedekind::optimization::detail::entries_in_unit_range_v

constexpr

Initial value:

= []() {
  using T = typename H::scalar_type;
  if constexpr (requires { T{-1}; }) {
    return (H::coeff_x == T{-1} || H::coeff_x == T{} || H::coeff_x == T{1}) &&
           (H::coeff_y == T{-1} || H::coeff_y == T{} || H::coeff_y == T{1});
  } else {
    return false;
  }
}()

Per-halfspace check: (coeff_x, coeff_y) ∈ {−1, 0, +1}².

Gated on T{-1} being a valid construction so unsigned halfspace carriers gracefully classify as false rather than ill-forming the classifier (which would otherwise emit a narrowing conversion error on unsigned{-1} under -Wconversion ). Per Copilot review on PR #751.

lp_step_arrow

template<typename T>

auto dedekind::optimization::detail::lp_step_arrow

constexpr

Initial value:

=
    dedekind::category::arrow([](const LPSolutionSet<T>& s) { return s; })

Shape-level F-algebra structure map on the output Set: an endomap representing the "active-set step" at the type level. Concrete LP folds close over halfspaces internally; the shape-level witness here is halfspace-agnostic, which is what F-algebra structure abstracts.