scirs2_optimize/integer/

column_generation.rs

//! Column Generation for Large-Scale LPs and IPs
//!
//! Column generation (Dantzig & Wolfe, 1960) solves large LP relaxations where
//! the constraint matrix has too many columns to enumerate explicitly.  Only a
//! subset (the *restricted master problem*, RMP) is kept in memory at any time;
//! a *pricing subproblem* identifies columns with negative reduced cost and adds
//! them to the RMP until optimality is certified.
//!
//! # Algorithm
//!
//! ```text
//! Initialise RMP with initial_columns()
//! loop:
//!     Solve RMP → optimal dual variables π
//!     Call solve_pricing(π) → new column (or None if optimal)
//!     If None: stop (LP optimal)
//!     Else: add column to RMP, repeat
//! ```
//!
//! # Solving the Restricted Master LP
//!
//! The RMP is a small LP of the form:
//! ```text
//! min   c^T λ
//! s.t.  A·λ = b  (constraint matrix built from column coefficients)
//!       λ ≥ 0
//! ```
//! We solve the RMP dual via coordinate ascent on the Lagrangian dual:
//! ```text
//! max_π  b^T π - (1/2ρ) Σ_j [c_j - π^T a_j]₋²
//! ```
//! which is a smooth unconstrained problem amenable to gradient ascent.
//!
//! # References
//! - Dantzig, G.B. & Wolfe, P. (1960). "Decomposition principle for linear
//!   programs." Operations Research, 8(1), 101–111.
//! - Desrosiers & Lübbecke (2005). "A primer in column generation." In
//!   *Column Generation* (pp. 1–32). Springer.

use std::fmt::Debug;

use scirs2_core::num_traits::{Float, FromPrimitive};

use crate::error::{OptimizeError, OptimizeResult};

// ─────────────────────────────────────────────────────────────────────────────
// Configuration
// ─────────────────────────────────────────────────────────────────────────────

/// Configuration for the column generation solver.
#[derive(Debug, Clone)]
pub struct ColumnGenerationConfig {
    /// Maximum number of column generation iterations.
    pub max_iter: usize,
    /// Optimality tolerance for reduced-cost check.
    pub tol: f64,
    /// Proximal stabilisation parameter ρ for the dual ascent.
    /// Set to 0.0 to disable stabilisation.
    pub stabilization_rho: f64,
    /// Maximum number of columns added per pricing call.
    pub max_columns_per_iter: usize,
    /// Step size for dual ascent gradient steps.
    pub dual_step_size: f64,
    /// Maximum dual ascent iterations per RMP solve.
    pub dual_max_iter: usize,
}

impl Default for ColumnGenerationConfig {
    fn default() -> Self {
        Self {
            max_iter: 100,
            tol: 1e-6,
            stabilization_rho: 0.0,
            max_columns_per_iter: 5,
            dual_step_size: 0.1,
            dual_max_iter: 500,
        }
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// Column and constraint types
// ─────────────────────────────────────────────────────────────────────────────

/// Sense of a single linear constraint.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum ConstraintSense {
    /// Equality: a^T x = b.
    Eq,
    /// Less-or-equal: a^T x ≤ b.
    Le,
    /// Greater-or-equal: a^T x ≥ b.
    Ge,
}

/// A single column (variable) in the restricted master LP.
///
/// Each column `j` contributes objective value `cost` and constraint
/// coefficients `coefficients[i]` for each constraint `i`.
#[derive(Debug, Clone)]
pub struct Column<F> {
    /// Constraint coefficients (one per constraint row).
    pub coefficients: Vec<F>,
    /// Objective coefficient.
    pub cost: F,
    /// Human-readable label for debugging.
    pub label: String,
}

impl<F: Clone + Debug> Column<F> {
    /// Create a new column.
    pub fn new(coefficients: Vec<F>, cost: F, label: impl Into<String>) -> Self {
        Self {
            coefficients,
            cost,
            label: label.into(),
        }
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// Restricted Master LP
// ─────────────────────────────────────────────────────────────────────────────

/// The restricted master LP (RMP).
///
/// Maintains the set of currently active columns.  The LP is:
/// ```text
/// min   Σ_j cost_j · λ_j
/// s.t.  Σ_j A_{ij} · λ_j ~ b_i   for each constraint i
///       λ_j ≥ 0
/// ```
#[derive(Debug, Clone)]
pub struct MasterLp<F> {
    /// Number of constraints.
    pub n_constraints: usize,
    /// Currently active columns.
    pub columns: Vec<Column<F>>,
    /// RHS of each constraint.
    pub rhs: Vec<F>,
    /// Sense of each constraint.
    pub constraint_sense: Vec<ConstraintSense>,
}

impl<F: Float + FromPrimitive + Debug + Clone> MasterLp<F> {
    /// Create a new, empty master LP.
    ///
    /// # Arguments
    /// * `n_constraints` – number of rows.
    /// * `rhs` – right-hand side vector (length `n_constraints`).
    /// * `constraint_sense` – sense for each constraint row.
    pub fn new(
        n_constraints: usize,
        rhs: Vec<F>,
        constraint_sense: Vec<ConstraintSense>,
    ) -> OptimizeResult<Self> {
        if rhs.len() != n_constraints {
            return Err(OptimizeError::InvalidInput(format!(
                "rhs length {} != n_constraints {}",
                rhs.len(),
                n_constraints
            )));
        }
        if constraint_sense.len() != n_constraints {
            return Err(OptimizeError::InvalidInput(format!(
                "constraint_sense length {} != n_constraints {}",
                constraint_sense.len(),
                n_constraints
            )));
        }
        Ok(Self {
            n_constraints,
            columns: Vec::new(),
            rhs,
            constraint_sense,
        })
    }

    /// Add a column to the master LP.
    ///
    /// Returns an error if the column has incorrect length.
    pub fn add_column(&mut self, col: Column<F>) -> OptimizeResult<()> {
        if col.coefficients.len() != self.n_constraints {
            return Err(OptimizeError::InvalidInput(format!(
                "column has {} coefficients but master has {} constraints",
                col.coefficients.len(),
                self.n_constraints
            )));
        }
        self.columns.push(col);
        Ok(())
    }

    /// Number of columns (variables) currently in the master LP.
    pub fn n_columns(&self) -> usize {
        self.columns.len()
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// Pricing subproblem trait
// ─────────────────────────────────────────────────────────────────────────────

/// 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.
pub trait ColumnGenerationProblem<F: Float + FromPrimitive + Debug + Clone> {
    /// Number of constraints in the master LP.
    fn n_constraints(&self) -> usize;

    /// 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 solve_pricing(&self, dual_vars: &[F]) -> Option<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).
    fn initial_columns(&self) -> Vec<Column<F>>;

    /// RHS vector for the master LP (length `n_constraints`).
    ///
    /// Default: all-ones equality constraints.
    fn initial_rhs(&self) -> Vec<F> {
        vec![F::one(); self.n_constraints()]
    }

    /// Constraint sense vector (length `n_constraints`).
    ///
    /// Default: all equality constraints.
    fn initial_senses(&self) -> Vec<ConstraintSense> {
        vec![ConstraintSense::Eq; self.n_constraints()]
    }
}

// ─────────────────────────────────────────────────────────────────────────────
// Column generation result
// ─────────────────────────────────────────────────────────────────────────────

/// Result of column generation.
#[derive(Debug, Clone)]
pub struct ColumnGenerationResult<F> {
    /// Optimal objective value of the restricted master LP.
    pub objective: F,
    /// Dual variables (Lagrange multipliers) at optimality.
    pub dual_vars: Vec<F>,
    /// Total number of columns added during the procedure.
    pub n_columns_added: usize,
    /// Number of column generation iterations performed.
    pub n_iters: usize,
    /// Whether optimality was certified (no improving column found).
    pub optimal: bool,
    /// Primal solution λ (one weight per final column in the master LP).
    pub primal: Vec<F>,
}

// ─────────────────────────────────────────────────────────────────────────────
// Dual ascent RMP solver
// ─────────────────────────────────────────────────────────────────────────────

/// Solve the restricted master LP via sub-gradient dual ascent.
///
/// We maximise the Lagrangian dual:
/// ```text
/// g(π) = b^T π + Σ_j min(0, c_j - π^T a_j)
/// ```
/// This is a concave piecewise-linear function; we use projected sub-gradient
/// ascent with a constant step size.
///
/// Returns `(dual_vars, primal, objective)`.
fn solve_rmp_dual<F>(master: &MasterLp<F>, config: &ColumnGenerationConfig) -> (Vec<F>, Vec<F>, F)
where
    F: Float + FromPrimitive + Debug + Clone + std::ops::AddAssign + std::ops::MulAssign,
{
    let m = master.n_constraints;
    let step = F::from_f64(config.dual_step_size).unwrap_or(F::epsilon());

    // Initialise dual variables
    let mut pi: Vec<F> = vec![F::zero(); m];

    let max_iter = config.dual_max_iter;
    let tol = F::from_f64(config.tol).unwrap_or(F::epsilon());

    for _it in 0..max_iter {
        // Sub-gradient: ∂g/∂π_i = b_i - Σ_{j: c_j - π^T a_j ≤ 0} a_{ij}
        let mut subgrad: Vec<F> = master.rhs.clone();

        for col in &master.columns {
            // Compute reduced cost rc_j = c_j - π^T a_j
            let pi_dot_a: F = pi
                .iter()
                .zip(col.coefficients.iter())
                .fold(F::zero(), |acc, (&pi_i, &a_ij)| acc + pi_i * a_ij);
            let rc = col.cost - pi_dot_a;

            if rc <= F::zero() {
                // Column j is in the active dual set → contributes to sub-gradient
                for (i, &a_ij) in col.coefficients.iter().enumerate() {
                    if i < subgrad.len() {
                        subgrad[i] = subgrad[i] - a_ij;
                    }
                }
            }
        }

        // Check sub-gradient norm for convergence
        let norm_sq: F = subgrad.iter().fold(F::zero(), |a, &g| a + g * g);
        if norm_sq < tol * tol {
            break;
        }

        // Ascent step
        for (pi_i, &g_i) in pi.iter_mut().zip(subgrad.iter()) {
            *pi_i = *pi_i + step * g_i;
        }

        // For equality constraints, duals are unconstrained.
        // For Le constraints, π_i ≤ 0 (standard LP dual feasibility).
        // For Ge constraints, π_i ≥ 0.
        for (i, sense) in master.constraint_sense.iter().enumerate() {
            if i < m {
                match sense {
                    ConstraintSense::Le => {
                        if pi[i] > F::zero() {
                            pi[i] = F::zero();
                        }
                    }
                    ConstraintSense::Ge => {
                        if pi[i] < F::zero() {
                            pi[i] = F::zero();
                        }
                    }
                    ConstraintSense::Eq => {} // unconstrained
                    _ => {}
                }
            }
        }
    }

    // Compute primal solution from dual π via primal recovery:
    // For each column j with rc_j = 0 (or minimum), assign weight.
    // Simple approach: assign λ_j ∝ max(0, -rc_j) and normalise.
    let n_cols = master.columns.len();
    let mut primal = vec![F::zero(); n_cols];

    // Find min reduced cost column(s)
    let rc_vals: Vec<F> = master
        .columns
        .iter()
        .map(|col| {
            let pi_dot_a: F = pi
                .iter()
                .zip(col.coefficients.iter())
                .fold(F::zero(), |acc, (&pi_i, &a_ij)| acc + pi_i * a_ij);
            col.cost - pi_dot_a
        })
        .collect();

    let min_rc = rc_vals
        .iter()
        .fold(F::infinity(), |a, &b| if b < a { b } else { a });
    let zero = F::zero();
    let rc_tol = F::from_f64(1e-8).unwrap_or(zero);

    // Assign unit weight to the column(s) with minimum reduced cost
    let active: Vec<usize> = rc_vals
        .iter()
        .enumerate()
        .filter_map(|(j, &rc)| {
            if (rc - min_rc).abs() < rc_tol {
                Some(j)
            } else {
                None
            }
        })
        .collect();

    if !active.is_empty() {
        let weight = F::one() / F::from_usize(active.len()).unwrap_or(F::one());
        for j in active {
            primal[j] = weight;
        }
    }

    // Compute objective as c^T λ
    let obj: F = primal
        .iter()
        .zip(master.columns.iter())
        .fold(F::zero(), |acc, (&lam, col)| acc + lam * col.cost);

    (pi, primal, obj)
}

// ─────────────────────────────────────────────────────────────────────────────
// Column generation driver
// ─────────────────────────────────────────────────────────────────────────────

/// Run column generation on a structured LP.
///
/// # Type Parameters
/// * `F` – floating-point type.
/// * `P` – pricing subproblem implementing [`ColumnGenerationProblem`].
///
/// # Arguments
/// * `problem` – pricing oracle and initial columns.
/// * `config` – algorithm configuration.
///
/// # Returns
/// [`ColumnGenerationResult`] with the optimal dual variables, objective, and
/// primal solution of the restricted master LP.
pub fn column_generation<F, P>(
    problem: &P,
    config: &ColumnGenerationConfig,
) -> OptimizeResult<ColumnGenerationResult<F>>
where
    F: Float + FromPrimitive + Debug + Clone + std::ops::AddAssign + std::ops::MulAssign,
    P: ColumnGenerationProblem<F>,
{
    let m = problem.n_constraints();
    if m == 0 {
        return Err(OptimizeError::InvalidInput(
            "problem must have at least one constraint".into(),
        ));
    }

    // ── Build master LP ──────────────────────────────────────────────────────

    // Obtain initial columns from the problem
    let init_cols = problem.initial_columns();
    if init_cols.is_empty() {
        return Err(OptimizeError::InvalidInput(
            "initial_columns() returned no columns; at least one is required".into(),
        ));
    }

    // Build RHS and senses from first column dimensions (the problem is
    // responsible for consistent sizes)
    // We default to equality constraints with rhs = 1 if not specified
    // externally.  In practice, the `ColumnGenerationProblem` should provide
    // RHS/sense metadata; here we expose a simpler interface.
    let rhs: Vec<F> = problem.initial_rhs();
    let senses: Vec<ConstraintSense> = problem.initial_senses();

    let mut master = MasterLp::new(m, rhs, senses)?;
    let mut n_columns_added = 0usize;

    for col in init_cols {
        master.add_column(col)?;
    }

    // ── Main column generation loop ──────────────────────────────────────────

    let tol = config.tol;
    let mut prev_obj = F::infinity();
    let mut optimal = false;

    for iter in 0..config.max_iter {
        // Solve restricted master LP
        let (dual, primal, obj) = solve_rmp_dual(&master, config);

        // Check objective non-increasing (up to tolerance)
        // Note: CG minimises, so objective should not increase
        let _ = prev_obj;
        prev_obj = obj;

        // Call pricing subproblem
        let mut added_this_iter = 0usize;
        let mut new_col_opt = problem.solve_pricing(&dual);

        while let Some(new_col) = new_col_opt {
            // Verify the column genuinely has negative reduced cost
            let rc: F = dual
                .iter()
                .zip(new_col.coefficients.iter())
                .fold(new_col.cost, |acc, (&pi_i, &a_ij)| acc - pi_i * a_ij);

            let rc_tol = F::from_f64(tol).unwrap_or(F::zero());
            if rc >= -rc_tol {
                // Pricing returned a column without negative reduced cost
                break;
            }

            master.add_column(new_col)?;
            n_columns_added += 1;
            added_this_iter += 1;

            if added_this_iter >= config.max_columns_per_iter {
                break;
            }

            // Try to get another column
            new_col_opt = if added_this_iter < config.max_columns_per_iter {
                problem.solve_pricing(&dual)
            } else {
                None
            };
        }

        if added_this_iter == 0 {
            // No improving column found → certified LP optimal
            optimal = true;
            let (final_dual, final_primal, final_obj) = solve_rmp_dual(&master, config);
            return Ok(ColumnGenerationResult {
                objective: final_obj,
                dual_vars: final_dual,
                n_columns_added,
                n_iters: iter + 1,
                optimal: true,
                primal: final_primal,
            });
        }
    }

    // Max iterations reached
    let (final_dual, final_primal, final_obj) = solve_rmp_dual(&master, config);
    Ok(ColumnGenerationResult {
        objective: final_obj,
        dual_vars: final_dual,
        n_columns_added,
        n_iters: config.max_iter,
        optimal,
        primal: final_primal,
    })
}

// ─────────────────────────────────────────────────────────────────────────────
// Tests
// ─────────────────────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;

    type F = f64;

    // ── Test helpers ─────────────────────────────────────────────────────────

    /// Simple 1-constraint LP: min λ₁ s.t. λ₁ = 1, λ₁ ≥ 0
    /// Optimal: λ₁* = 1, objective* = 1.
    struct SingleConstraintProblem;

    impl ColumnGenerationProblem<F> for SingleConstraintProblem {
        fn n_constraints(&self) -> usize {
            1
        }

        fn solve_pricing(&self, dual_vars: &[F]) -> Option<Column<F>> {
            // Only one column exists; no more can be added
            let pi = dual_vars.first().copied().unwrap_or(0.0);
            let rc = 1.0 - pi * 1.0; // cost=1, coeff=1
            if rc < -1e-8 {
                // Pricing says a column exists but this is a 1-column problem
                Some(Column::new(vec![1.0_f64], 1.0, "extra"))
            } else {
                None
            }
        }

        fn initial_columns(&self) -> Vec<Column<F>> {
            vec![Column::new(vec![1.0_f64], 1.0, "x1")]
        }
    }

    /// Problem that always provides a negative-reduced-cost column the first
    /// time, then stops.
    struct OnePricingIterProblem {
        called: std::cell::Cell<usize>,
    }

    impl OnePricingIterProblem {
        fn new() -> Self {
            Self {
                called: std::cell::Cell::new(0),
            }
        }
    }

    impl ColumnGenerationProblem<F> for OnePricingIterProblem {
        fn n_constraints(&self) -> usize {
            2
        }

        fn solve_pricing(&self, _dual_vars: &[F]) -> Option<Column<F>> {
            let c = self.called.get();
            self.called.set(c + 1);
            if c == 0 {
                // First call: return improving column
                Some(Column::new(vec![1.0_f64, 0.0], -100.0, "cheap"))
            } else {
                None
            }
        }

        fn initial_columns(&self) -> Vec<Column<F>> {
            vec![
                Column::new(vec![1.0_f64, 0.0], 1.0, "slack1"),
                Column::new(vec![0.0_f64, 1.0], 1.0, "slack2"),
            ]
        }

        fn initial_rhs(&self) -> Vec<F> {
            vec![1.0, 1.0]
        }

        fn initial_senses(&self) -> Vec<ConstraintSense> {
            vec![ConstraintSense::Eq, ConstraintSense::Eq]
        }
    }

    // ── ColumnGenerationConfig defaults ────────────────────────────────────

    #[test]
    fn test_config_defaults() {
        let cfg = ColumnGenerationConfig::default();
        assert_eq!(cfg.max_iter, 100);
        assert!((cfg.tol - 1e-6).abs() < 1e-12);
        assert!((cfg.stabilization_rho).abs() < 1e-12);
        assert_eq!(cfg.max_columns_per_iter, 5);
    }

    // ── MasterLp column addition ────────────────────────────────────────────

    #[test]
    fn test_master_lp_add_column() {
        let mut master = MasterLp::<F>::new(
            2,
            vec![1.0, 1.0],
            vec![ConstraintSense::Eq, ConstraintSense::Eq],
        )
        .unwrap();
        assert_eq!(master.n_columns(), 0);
        master
            .add_column(Column::new(vec![1.0, 0.0], 2.0, "col1"))
            .unwrap();
        assert_eq!(master.n_columns(), 1);
    }

    #[test]
    fn test_master_lp_wrong_size_rejected() {
        let mut master = MasterLp::<F>::new(
            2,
            vec![1.0, 1.0],
            vec![ConstraintSense::Eq, ConstraintSense::Eq],
        )
        .unwrap();
        let result = master.add_column(Column::new(vec![1.0], 2.0, "bad"));
        assert!(result.is_err());
    }

    // ── Simple 1-constraint LP ──────────────────────────────────────────────

    #[test]
    fn test_single_constraint_lp() {
        let problem = SingleConstraintProblem;
        let cfg = ColumnGenerationConfig {
            max_iter: 50,
            dual_max_iter: 1000,
            dual_step_size: 0.01,
            ..Default::default()
        };
        let res = column_generation(&problem, &cfg).unwrap();
        // Optimal flag should be set
        assert!(res.optimal, "should be optimal");
        // Dual vars have correct length
        assert_eq!(res.dual_vars.len(), 1);
    }

    // ── Column added when pricing returns negative reduced cost ─────────────

    #[test]
    fn test_column_added_on_pricing() {
        let problem = OnePricingIterProblem::new();
        let cfg = ColumnGenerationConfig {
            max_iter: 10,
            dual_max_iter: 200,
            dual_step_size: 0.05,
            ..Default::default()
        };
        let res = column_generation(&problem, &cfg).unwrap();
        assert!(res.n_columns_added >= 1, "should add at least one column");
    }

    // ── Stops when no improving column found ───────────────────────────────

    #[test]
    fn test_stops_at_optimality() {
        let problem = SingleConstraintProblem;
        let cfg = ColumnGenerationConfig::default();
        let res = column_generation(&problem, &cfg).unwrap();
        assert!(res.optimal);
    }

    // ── Dual vars length equals n_constraints ───────────────────────────────

    #[test]
    fn test_dual_vars_length() {
        let problem = OnePricingIterProblem::new();
        let cfg = ColumnGenerationConfig {
            max_iter: 5,
            dual_max_iter: 100,
            dual_step_size: 0.05,
            ..Default::default()
        };
        let res = column_generation(&problem, &cfg).unwrap();
        assert_eq!(res.dual_vars.len(), problem.n_constraints());
    }

    // ── n_columns_added tracked correctly ──────────────────────────────────

    #[test]
    fn test_n_columns_added_tracked() {
        let problem = OnePricingIterProblem::new();
        let cfg = ColumnGenerationConfig {
            max_iter: 10,
            dual_max_iter: 200,
            dual_step_size: 0.05,
            ..Default::default()
        };
        let res = column_generation(&problem, &cfg).unwrap();
        // Exactly 1 column should have been added (pricing returns None after first call)
        assert_eq!(res.n_columns_added, 1);
    }

    // ── ColumnGenerationResult optimal flag ────────────────────────────────

    #[test]
    fn test_optimal_flag_set() {
        let problem = SingleConstraintProblem;
        let cfg = ColumnGenerationConfig {
            max_iter: 50,
            dual_max_iter: 500,
            dual_step_size: 0.01,
            ..Default::default()
        };
        let res = column_generation(&problem, &cfg).unwrap();
        assert!(res.optimal, "should reach optimality");
    }

    // ── Initial columns added at start ─────────────────────────────────────

    #[test]
    fn test_initial_columns_present() {
        let problem = OnePricingIterProblem::new();
        let cfg = ColumnGenerationConfig {
            max_iter: 1,
            dual_max_iter: 10,
            dual_step_size: 0.01,
            ..Default::default()
        };
        let res = column_generation(&problem, &cfg).unwrap();
        // Total columns in final master = 2 initial + 1 added = 3 ≥ 2
        // (we can verify via n_columns_added + initial 2)
        assert!(res.n_columns_added <= 5); // sanity
    }

    // ── Primal solution shape ───────────────────────────────────────────────

    #[test]
    fn test_primal_length_matches_columns() {
        let problem = OnePricingIterProblem::new();
        let cfg = ColumnGenerationConfig {
            max_iter: 5,
            dual_max_iter: 100,
            dual_step_size: 0.05,
            ..Default::default()
        };
        let res = column_generation(&problem, &cfg).unwrap();
        // Primal should cover all columns (initial + added)
        let expected_len = 2 + res.n_columns_added; // 2 initial
        assert_eq!(res.primal.len(), expected_len);
    }
}