Trait ColumnGenerationProblem 

pub trait ColumnGenerationProblem<F: Float + FromPrimitive + Debug + Clone> {
    // Required methods
    fn n_constraints(&self) -> usize;
    fn solve_pricing(&self, dual_vars: &[F]) -> Option<Column<F>>;
    fn initial_columns(&self) -> Vec<Column<F>>;

    // Provided methods
    fn initial_rhs(&self) -> Vec<F> { ... }
    fn initial_senses(&self) -> Vec<ConstraintSense> { ... }
}

Interface for a column generation pricing subproblem.

Implementors encode the structure of the subproblem specific to the application (e.g., shortest path, bin-packing, knapsack).

The three required methods (n_constraints, solve_pricing, initial_columns) must always be provided. The two optional methods (initial_rhs, initial_senses) have defaults that produce an equality master LP with rhs = 1, which suits many Dantzig–Wolfe decompositions.

Required Methods

fn n_constraints(&self) -> usize

Number of constraints in the master LP.

fn solve_pricing(&self, dual_vars: &[F]) -> Option<Column<F>>

Solve the pricing subproblem given dual variables π.

Find a column a_j with negative reduced cost c_j - π^T A_j < -tol.

Returns Some(column) if such a column exists, None if no improving column can be found (optimality certificate).

fn initial_columns(&self) -> Vec<Column<F>>

Generate the initial set of columns for warm-starting the RMP.

A safe default is to return identity slack columns (one per constraint).

Provided Methods

fn initial_rhs(&self) -> Vec<F>

RHS vector for the master LP (length n_constraints).

Default: all-ones equality constraints.

fn initial_senses(&self) -> Vec<ConstraintSense>

Constraint sense vector (length n_constraints).

Default: all equality constraints.

Implementors