GeneratedAssembled automatically from moduleDocs.ts. No human has reviewed this page.

combinatorial_optimization

Concept Overview

AFML Chapter 21 tooling for discrete, path-dependent problems, built around keeping the integer structure explicit rather than relaxing it away. DecisionSchema describes an integer decision space and solve_exact enumerates it. TradingTrajectorySchema describes a trading path — per-step trade bounds, inventory limits, an optional terminal inventory — and enumerate_trading_paths produces every feasible trajectory, which evaluate_trading_path scores against expected returns, risk aversion, market impact and a fixed per-ticket cost.

When to Use

Use exact enumeration on small instances as a correctness oracle: compare_exact_and_adapter exists precisely so a heuristic or external solver can be validated against ground truth before it is trusted at scale. The decision space grows exponentially in horizon and dimension and max_paths will stop you — treat that as the signal to move to an adapter, not to raise the cap. The fixed ticket cost is what makes the problem genuinely combinatorial; without it a continuous relaxation would do.

Mathematical Foundations

Finite Integer Program

$x^*=\arg\max_{x\in\mathcal X\subset\mathbb Z^d} f(x),\quad |\mathcal X|<\infty$

Path-Dependent Objective

$J(\tau)=\sum_{t=1}^{T}\left(q_t r_t-\lambda q_t^2-c_t|\Delta q_t|-\kappa\,\mathbf 1_{\Delta q_t\ne0}\right)-\eta(q_T-q^*)^2$

Adapter Gap vs Exact

$\Delta_{alg}=\begin{cases}f(x^*)-f(\hat x) & \text{maximize}\\f(\hat x)-f(x^*) & \text{minimize}\end{cases}$

Usage Examples

Rust

Exact trajectory search with fixed ticket costs

use openquant::combinatorial_optimization::{
  TradeBounds, TradingTrajectoryObjectiveConfig, TradingTrajectoryPath, TradingTrajectorySchema,
  enumerate_trading_paths, evaluate_trading_path,
};

let schema = TradingTrajectorySchema {
  initial_inventory: 0,
  inventory_min: -2,
  inventory_max: 2,
  step_trade_bounds: vec![
    TradeBounds { min_trade: -1, max_trade: 1 },
    TradeBounds { min_trade: -1, max_trade: 1 },
    TradeBounds { min_trade: -1, max_trade: 1 },
  ],
  terminal_inventory: Some(0),
  max_paths: 50_000,
};
let cfg = TradingTrajectoryObjectiveConfig {
  expected_returns: vec![0.01, -0.015, 0.012],
  risk_aversion: 0.001,
  impact_coefficients: vec![0.0005, 0.0005, 0.0005],
  fixed_ticket_cost: 0.002,
  terminal_inventory_target: 0,
  terminal_inventory_penalty: 0.05,
};

let best = enumerate_trading_paths(&schema)?
  .into_iter()
  .map(|path| {
    let score = evaluate_trading_path(&path, &cfg)?;
    Ok::<(TradingTrajectoryPath, f64), openquant::combinatorial_optimization::CombinatorialOptimizationError>((path, score))
  })
  .collect::<Result<Vec<_>, _>>()?
  .into_iter()
  .max_by(|a, b| a.1.total_cmp(&b.1))
  .expect("at least one feasible path");

println!("best objective: {:.6}", best.1);
println!("trades: {:?}", best.0.trades);

API Reference

Rust API

DecisionSchema
IntegerVariable
IntegerObjective
solve_exact
SolverAdapter
solve_with_adapter
compare_exact_and_adapter
TradingTrajectorySchema
enumerate_trading_paths
evaluate_trading_path
solve_trading_trajectory_exact

Risk Notes and Caveats

Exact enumeration scales exponentially in decision dimension/horizon; treat it as a correctness baseline and regression oracle.
Use adapter interfaces to compare heuristic/external solvers against exact solutions on small calibration instances before production deployment.