PaperlayerView exact revision on arXiv

Source-linked AI summary

CG4AI: A Column Generation Framework for Training AI Models Under Constraints

Youcef Magnouche, Abderrahmane Driouch, Sébastien Martin, Pierre Bauguion

arXiv:2608.26375v1cs.LGcs.AIcs.DM

TL;DR

CG4AI addresses the absence of guaranteed output feasibility in standard machine-learning training by constructing convex ensembles under hard linear constraints. A master LP sets mixture weights, pricing adds dual-guided models, and cutting planes extend guarantees beyond the training set. Across MNIST and multi-commodity flow, it produces feasible predictors with strong accuracy and fast inference, while nonlinear local pricing remains heuristic.

  • Problem

    Standard loss minimization does not guarantee that predictions satisfy hard safety, physical, or regulatory constraints on new inputs.

  • Method

    CG4AI trains a convex ensemble using a master LP for constrained mixture weights, dual-guided pricing for new models, and cutting planes for constraints beyond the training set.

  • Results

    CG4AI produces feasible predictors across MNIST and SNDLIB multi-commodity-flow benchmarks, with better accuracy than single-model baselines and fast test-time inference.

  • Takeaways & Limitations

    Constraints can support MNIST constraint-only learning, robustness improvement, misclassification correction, output relabeling, and capacity-feasible neural routing.

  • Takeaways & Limitations

    With local pricing optimization, CG4AI has no optimality certificate and is heuristic, although experiments report feasibility and good accuracy on 38 SNDLIB instances.

Abstract

from arXiv · show

Standard machine-learning training minimizes a loss function over a dataset, but does not guarantee that the resulting model will satisfy predefined rules or constraints on its outputs. In many real-world applications, ranging from autonomous systems to network routing, such guarantees are essential. We propose CG4AI, a framework that builds a convex combination of AI models while enforcing linear constraints on the combined output. A master linear program (LP) determines the optimal mixture weights, while a pricing subproblem generates new models guided by LP dual variables, focusing attention on the most violated constraints. A cutting-plane procedure extends feasibility guarantees beyond the training set. We apply CG4AI to two problems: (i) digit classification on MNIST, where we demonstrate four distinct uses of constraints, learning from constraints alone, improving adversarial robustness, correcting misclassified examples, and enforcing output relabeling; and (ii) the multi-commodity flow problem, where link capacity constraints are enforced on neural-network routing predictors. Experiments on MNIST and standard SNDLIB benchmark networks show that CG4AI reliably produces feasible predictors while achieving better accuracy than single-model baselines.

1 Introduction

CG4AI addresses the lack of test-time guarantees in standard training by learning convex ensembles whose outputs satisfy hard linear constraints through a master LP and column generation.

  • Standard loss minimization can produce predictions that violate safety rules, physical laws, or regulatory requirements on new inputs.
  • Hard constraints are conditions that predictions must never violate, including collision avoidance, tissue-dose bounds, link capacities, and legal fairness requirements.
  • CG4AI builds a convex ensemble whose mixture weights are chosen by a master LP containing output constraints as linear inequalities.
  • Pricing generates new models using dual variables that emphasize inputs where the current ensemble violates constraints most strongly.
  • The framework supports external constraint sets, multiple constraint types, and cutting planes that add the most violated constraints while preserving LP tractability.

2 Related Work

CG4AI extends column-generation and constrained-learning approaches by imposing external output constraints in the master LP, yielding deterministic feasibility rather than relying on penalties or inference-time projection.

  • Penalty-based methods soften constraints and require penalty tuning, while projection and optimization-layer methods can add inference cost or lack guarantees on unseen inputs.
  • CG4AI retains LPBoost’s column-generation structure but replaces margin maximization with general training losses for arbitrary AI models.
  • Its master LP adds external output constraints that may be associated with inputs disjoint from the training set and can encode safety, physical, or user-defined requirements.
  • CG4AI provides a deterministic feasibility guarantee: when the LP is feasible, the ensemble satisfies all output constraints regardless of whether those inputs appeared during training.
  • The framework supports adversarial robustness, misclassification correction, and output relabeling without modifying its general structure.

3 The CG4AI Framework

The CG4AI framework converts constrained ensemble learning into an LP over model weights, then uses pricing to add models that improve loss and constraint satisfaction.

  • CG4AI separates training data from a potentially overlapping or disjoint constraint-input set on which output requirements must hold.
  • The combined predictor is a convex combination of candidate models, allowing output constraints to become linear in the mixture weights.
  • The master LP minimizes a loss bound while using nonnegative slack variables with a large penalty to prioritize feasibility.
  • Dual variable β_j measures constraint difficulty, and large β_j values increase attention to the corresponding input during pricing.
  • Column generation maintains a restricted master LP and adds models with negative reduced cost because they can improve the objective.
  • For nonlinear models, pricing is non-convex and local optimization makes CG4AI heuristic without the exact LP optimality guarantee.

4: Pricing

The cutting-plane extension alternates between generating models, solving for mixture weights, and adding the most violated constraints to extend feasibility beyond a finite constraint sample.

  • When the constraint set is large or continuous, cutting planes begin with a small subset and iteratively add the constraint associated with the most violated input.
  • The separation problem searches for the input whose constraint violation is maximal under the current ensemble.
  • If the maximum violation is non-positive, the ensemble is feasible for the entire constraint set.
  • The combined procedure alternates pricing, master-LP optimization, and separation; when none improves the solution, it is LP-optimal and feasible for the full constraint set.
  • For single-hidden-layer ReLU networks, pricing and separation can be solved globally by mixed-integer programming, whereas the MCF application uses a black-box optimizer.

4 Proof of Concept: Digit Classification

CG4AI demonstrates constrained ensemble learning on MNIST through hard-set guarantees, robustness and correction constraints, relabeling, and comparisons with baseline methods. Its performance depends on how training data are divided between guaranteed hard constraints and optimization data.

  • Setup: A minimalist MLP with h = 4 hidden neurons maps 784-dimensional inputs to 10 class logits, making constraint-driven gains measurable under limited capacity.The architecture uses one hidden ReLU layer; single-model accuracy is modest across training sizes.
  • Constraint scenarios: The LP enforces hard constraints on IConst, while pricing minimizes cross-entropy on ITrain; with ITrain = ∅, learning uses only dual values.The tested hard/optimization splits are (0, 10), (2, 8), (5, 5), and (8, 2).
  • Constraint scenarios: Adversarial robustness adds constraints for misclassified saliency-based perturbations, with up to P = 100 pixel flips in the experiments.A cutting-plane procedure generates constraints from perturbed inputs.
  • Results: At n = 1000, CG-proba reaches 85.7% accuracy (+8.4 pp), while CG-margin reaches 78.7% with kh = 2 and guarantees correct classification on its hard set when constraints are satisfied.All all-constrained CG4AI variants outperform the baseline at every training size.
  • Results: Increasing kh extends guarantee coverage but reduces overall test accuracy, revealing a trade-off between certified hard-set coverage and general performance.The hard/optimization split controls this trade-off for both CG-margin and CG-proba.
  • Comparison with baselines: Against constrained-learning baselines, CG-margin exceeds DC3 by +13.0 and +14.6 pp, while penalty methods fall to ≤18.8% at n = 100.The reported gap attributes the measurable difference to LP output constraints and dual-guided pricing.
  • Results: CG-proba achieves 100% LP constraint satisfaction at every training size, whereas CG-margin reaches 69.7% at n = 1000 under the 400-column limit.CG-proba is recommended for complete coverage; CG-margin is recommended when maximum test accuracy is the priority.

5 Main Use Case: Network Routing Under Capacity Constraints

CG4AI is applied to multi-commodity flow routing, where neural predictors must route all demands while respecting network link capacities. The framework addresses continuous demand scenarios using cutting planes and dual-guided pricing.

  • CG4AI motivation: The routing constraint set is continuous, so cutting planes identify demand scenarios that produce capacity violations.Dual variables for arcs quantify overload and guide subsequent network columns toward capacity-respecting routing decisions.
  • Problem definition: MCFP routes demands through candidate network paths while minimizing maximum link utilization (MLU).Each demand has a source, destination, and traffic volume; path-flow fractions must satisfy demand, capacity, and non-negativity constraints.

5.2 Learning Routing Splits for MCFP

Neural networks predict routing splits from demand vectors instead of solving an LP for every instance. Although this enables millisecond inference, unconstrained predictions can exceed link capacities near maximum utilization.

  • Neural routing prediction: AI models predict routing splits directly from demand vectors, using training pairs containing demand vectors and LP-optimal routing.A softmax output layer enforces that each demand’s predicted path fractions sum to one.
  • Feasibility challenge: Millisecond inference avoids solving an LP, but pure neural predictions may violate capacity constraints when MLU is close to 1.Figure 8 reports frequent capacity exceedances for scenarios with 0.99 < MLU < 1.

5.3 CG4AI Formulation for MCFP

The MCFP formulation assigns convex ensembles of routing models to demands and imposes capacity constraints over the current scenario set. Pricing uses dual information, while separation adds the most violating continuous-demand scenarios.

  • 5.3 CG4AI Formulation for MCFP: The master problem enforces link capacity across all demand vectors currently included in IConst.Capacity constraints are imposed directly in the master LP rather than only through the training loss.
  • 5.3 CG4AI Formulation for MCFP: The cutting-plane procedure extends CG4AI’s feasibility guarantee from sampled scenarios toward continuous demand sets.The MCFP columns are AI models predicting routing splits, and the procedure iteratively enlarges the constraint set.
  • 5.3 CG4AI Formulation for MCFP: Each demand receives a valid convex combination of its associated routing models.The master formulation includes one slack variable per demand to preserve restricted-master feasibility during column generation.
  • 5.3 CG4AI Formulation for MCFP: Pricing minimizes each model’s reduced cost over network weights, using capacity duals and demand-level convex-combination duals.The dual of an arc-capacity constraint measures the role of that arc’s overload in pricing.
  • Cutting: Because IConst may be infinite, separation searches for a demand vector and arc with maximum utilization violation.A black-box optimizer performs this search, with one thread per arc to support parallelization.
  • Cutting: The most violating demand vector and arc are added to the restricted master as a new capacity constraint.This expands the enforced scenario set before another column-generation round.

5.4 Numerical Results

On SNDLIB benchmarks, CG4AI generally produces feasible routing ensembles, with convergence and accuracy varying by network difficulty and utilization. An alternative-objective experiment also preserves capacity feasibility, supporting the role of dual-guided pricing.

  • Evaluation setup: CG4AI is evaluated on real-world and synthetic SNDLIB telecommunication topologies.Training uses 1,000 random demand vectors with LP-optimal splits, and validation uses 10,000 random demand vectors.
  • Evaluation setup: The column models are feedforward PyTorch networks, with the best tested configuration using one 256-neuron GELU hidden layer.Training uses Adam, early stopping, and learning-rate decay; the LP is solved with CPLEX.
  • Feasibility: CG4AI produces feasible ensembles with zero slack for most instances, and slack generally converges rapidly to zero.Small increases can occur when new constraints are added, followed by resolution in the next column-generation step.
  • Prediction quality: All predictions remain below MLU 1.0 in the reported nobel-germany and newyork instances, although high-utilization predictions are less accurate.The newyork ensemble tends to underestimate MLU in the most congested cases.
  • Constraint analysis: Arc 13 violations in the Polska instance initially exceed capacity by 25% and decrease over iterations, though not monotonically.The non-monotonic pattern reflects the interaction between adding columns and adding constraints.
  • Constraint analysis: Three consistently maximum-valued demands are captive to Arc 13, while the optimizer varies non-captive demands to expose routing failures.These adversarial scenarios could seed the initial constraint set and potentially reduce cutting-plane iterations.
  • Benchmark results: Harder instances require more iterations and columns, ranging from 1–3 iterations on simpler cases to 999 iterations and 986 columns for di-yuan with 10 demands.The benchmark results otherwise show feasible solutions for most instances.
  • Alternative objective: With total weighted path cost replacing MLU, CG4AI still respects all capacity constraints but needs more iterations and ends with an 11.20% cost gap.The alternative cost has no inherent capacity-regularizing effect, supporting dual-guided pricing as the enforcement mechanism.

6 Conclusion

CG4AI trains convex ensembles whose mixture weights enforce hard linear constraints, combining LP feasibility, dual-guided model generation, and cutting planes. Across MNIST and multi-commodity flow, it supports several constraint-driven tasks and produces feasible routing predictors, while future work targets interpretability, efficiency, and extensibility.

  • CG4AI combines a master LP for mixture-weight feasibility, dual-guided pricing for new models, and cutting planes extending guarantees beyond finite training data.The pricing subproblem focuses on the most violated constraints identified through LP dual variables.
  • On MNIST, hard constraints support constraint-only learning, adversarial-robustness improvement, misclassification correction, and output relabeling without full retraining.
  • On multi-commodity flow, CG4AI produces routing predictors satisfying all link capacity constraints on standard SNDLIB benchmark networks, with good MLU accuracy and fast test-time inference.
  • The margin formulation requires only 3–6 columns for 1000 training images and achieves zero residual violation, while dual-guided pricing remains effective under an alternative cost function.
  • Open directions include integer ensembles, alternative column classes, problem-specific or exact separation, active learning, and distributed deployment.

Appendix A Experimental Tables

The appendix defines the columns used in the SNDLIB results table and presents a summary table of CG4AI experiments. The supplied passages identify the tables but do not report their contents or findings.

  • Table A1 provides the column definitions for Table A2.
  • Table A2 summarizes CG4AI results on SNDLIB instances.

Note on anomalous opt_mlu values.

The appendix discusses anomalous opt_mlu values as configuration or numerical issues rather than ordinary performance outcomes. Across SNDLIB instances, CG4AI generally produces feasible solutions, with computational effort varying by instance difficulty.

  • opt_mlu= 4.00 × 102 for geant reflects an unbounded LP because demand exceeds capacity, although CG4AI still generates a feasible ensemble within the path set.
  • opt_mlu= −5.37×10−2 for nobel-eu is a floating-point artefact of the CPLEX dual near zero and is functionally equivalent to 0.
  • Across SNDLIB instances, feasible solutions occur for the large majority of tested configurations, while computational effort ranges from a few iterations to nearly a thousand.
  • The nobel family achieves validation losses on the order of 10−4 and maximum differences below 0.15 MLU units.
Loading 2608.26375v1…