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

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

cs.LGAug 26, 2026

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

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

Organizations: Huawei Technologies Ltd., France Research Center, 18 Quai du Point du Jour, Boulogne-Billancourt, 92100, France.

Abstract

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.

Figures & tables

Notation	Description
$n$	Size of the input data set
$m$	Size of the hard constraints set
$d$	Input size of the AI model
$r$	Output size of the AI model
$\mathcal{M}$	Set of all possible AI models (candidates)
$\mathcal{I}^{\text{Const}}$	Set of inputs for which output constraints must be satisfied

Table 1: Summary of notations

Panel of Figure 1 — Figure 1: Architecture of column model $s_{i}$ used in the MNIST experiments: one hidden layer with $h=4$ neurons and ReLU activation, mapping a $784$ -dimensional input to $10$ class logits. The ensemble output is $\sum_{i\in\mathcal{M}}\lambda_{i}s_{i}(x)$ .

Panel of Figure 2 — Figure 2: Three adversarially perturbed digits (up to 100 pixels flipped). The models before adding constraints predict 2, 3, and 4 respectively, but the original labels are different. CG4AI adds constraints to enforce correct classification of these perturbed inputs.

Panel of Figure 3 — Figure 3: Two training images initially misclassified: digit 1 is predicted as 3, and digit 4 is predicted as 0. Adding hard constraints for these images forces the ensemble to classify them correctly.

Panel of Figure 4 — Figure 4: Relabeling example: three digits (0, 3, 3, 2) are shown after adding constraints forcing digit 3 to be predicted as 2. The digit-0 image is predicted as 0 by 50%, as 2 by 42%, and as 4 by 8%. The first 3 is predicted as 2 by 54%, the second as 2 by 100%, and the 2 as 2 by 100%.

Figure 5: Test accuracy on 2000 MNIST images vs. training set size. CG-margin and CG-proba (constraints only,

k_{o}=0

) outperform the baseline at every scale. The “2 hard + 8 train” split provides a guaranteed-correct hard set with a small accuracy cost.

Figure 6: Effect of the hard/optimization split on test accuracy (CG-margin left, CG-proba right). All CG4AI variants surpass the baseline. Increasing

k_{h}

extends the guarantee coverage but reduces overall test accuracy.

Variant	Split	$n=100$	$n=1000$
Baseline (CE only)	—	52.4	77.3
CG-margin	all constrained	57.1	83.8
CG-proba	all constrained	57.5	85.7
CG-margin	$k_{h}=2$ , rest optimize	54.8	78.7
CG-proba	$k_{h}=2$ , rest optimize	68.5	69.3
CG-margin	$k_{h}=5$ , rest optimize	51.7	66.1

Table 2: Test accuracy (%) on 2000 MNIST images (MLP,

h=4

, all-constrained mode unless stated).

k_{h}

: images per class in hard set

\mathcal{I}^{Const}

. Single run (seed 42). Note: the comparison in Table 3 uses a separate 3-seed benchmark (seeds 42, 43, 44), giving a slightly different baseline (

56.1\%

n=100

) due to seed variability.

Method	$n=100$	$n=1000$
Baseline (single model, CE)	56.08	70.98
Penalty (L2), $\lambda=10$	16.18	52.00
Augmented Lagrangian	18.80	61.35
DC3 ( $K=5$ steps)	56.70	71.73
Projection † (oracle)	82.37	90.42
CG-margin	69.70	86.30

Table 3: Test accuracy (%) at

n=100

and

n=1000

, averaged over 3 seeds (baselines) and single C++ run (CG4AI). Same MLP for all methods (1 hidden layer, 4 neurons). Best result excluding the oracle Projection is bolded .

Method	$n=100$	$n=1000$
Baseline	99.7	99.7
Penalty (L2)	7.0	11.2
Augmented Lagrangian	9.3	16.7
DC3	99.7	99.7
CG-margin	100.0	69.7 †
CG-proba	100.0	100.0

Table 4: Training constraint satisfaction (%) at

n=100

and

n=1000

, 3-seed averages for baselines. CG-proba provides a formal LP guarantee; all others are heuristic.

Figure 7: Test accuracy (left) and training constraint satisfaction (right). DC3 and the baseline are nearly superimposed, confirming that constraint-correction without an LP guarantee provides negligible accuracy gain. Both CG4AI variants separate clearly from all competitors; the

+14.6

pp gap over DC3 at

n=1000

is the measurable effect of the LP output constraints. Penalty and Aug. Lagrangian satisfy fewer than

17\%

of constraints at any scale.

Panel of Figure 9 — Figure 9: Slack variable evolution during the column-generation and cutting-plane iterations. The slack converges rapidly to zero, confirming that the algorithm achieves feasibility.

Figure 10: Predicted vs. optimal MLU on the nobel-germany instance $(\#d,\#p)=(15,3)$ . The ensemble closely tracks the optimal solution.

Figure 11: Predicted vs. optimal MLU on the newyork instance $(\#d,\#p)=(5,3)$ . Greater dispersion occurs for high-utilization scenarios, but predictions remain feasible.

Panel of Figure 12 — Figure 12: Arc violations for Arc 13 in the Polska instance $(\#d,\#p)=(5,3)$ .

Panel of Figure 13 — Figure 13: Constrained optimization with the alternative cost function on the ta1 instance. CG4AI satisfies all capacity constraints even though the training objective is not aligned with them.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Column	Description
instance	Network instance name.
#d	Number of demands.
#p	Number of candidate paths per demand.
#iter	Total iterations of the combined column-generation and cutting-plane procedure.
#cols	Total columns generated.
#rows	Constraints (rows) added by the cutting-plane step.

Appendix

Table 5: Column definitions for Table 6 .

instance	#d	#p	#iter	#cols	#rows	col_time	row_time	tot_time	opt_mlu	#mod	val. loss	max_diff
abilene	5	3	4	4	0	284.83	875.47	1160.41	7.63e-02	2	0.021	0.38
	10	3	57	36	9	2207.11	7831.87	10040.36	1.57e-01	34	0.013	0.46
	15	3	28	21	0	1336.92	1215.77	2553.48	4.26e-02	3	0.015	0.42
	5	5	11	8	4	463.05	1190.41	1653.69	9.14e-02	10	0.027	0.42
atlanta	5	3	45	26	10	2229.10	13427.90	15658.01	6.07e-01	43	0.010	0.33
	10	3	63	42	16	2832.30	19045.30	21879.00	9.91e-02	53	0.017	0.37

Appendix

Table 6: Summary of CG4AI results on SNDLIB instances.

Constrained Optimization

Constrained optimization finds the best decisions while satisfying equality, inequality, resource, safety, or fairness requirements.

See all 337 papers

Oct 2, 2026

Constraint-Aware Training

When generating programs with language models, constrained decoding can apply program analyses to exclude tokens that violate syntax, scope, or typing rules. However, there is a duplication: standard training already teaches the model to suppress the tokens rejected by these analyses. This duplication leads to the question: if we will perform some analysis to filter a set tokens out during inference anyways, can we avoid teaching the model the said analysis altogether during training, and does this externalization lead to more efficient models? This paper defines a general constraint-aware objective satisfying this externalization desideratum and formalizes the benefits of externalization into three concrete theorems about model size and data efficiency. We show, through a controlled synthetic experiment, that the theorems survive training dynamics: constraint-aware training yields lower prediction loss at a matched parameter count and data compared to ordinary cross-entropy training, motivating training objectives that incorporate the analyses used during generation.

Jinwoo Kim

Department of Computer Science and Engineering University of California-San Diego La Jolla, CA

Constrained Generative Modeling Efficient Language Model Training Constrained Decoding Program Synthesis

Ask PDF

Sep 7, 2026

Mathematical Programming in Machine Learning and Artificial Intelligence: A Unified Taxonomy of Models and Applications

Mathematical programming provides a common language for many decisions embedded in modern machine-learning (ML) and artificial-intelligence (AI) systems: selecting retrieval context, routing tokens, allocating inference compute, fitting structured predictors, protecting against distribution shift, and balancing competing objectives. However, the relevant literature is fragmented across optimization, information retrieval, recommendation, natural-language processing, computer vision, and learning theory. This paper organizes various applications under common mathematical programming paradigms: linear, quadratic, binary and mixed-integer, conic, bilevel, multi-objective, inverse, distributionally robust, submodular, and min--max optimization. We normalize the models with a mostly unified notation and, for every application, identify inputs, decision variables, a principal formulation, structural properties, solution strategies, and limitations. Across paradigms, we compare tractability, relaxation quality, decomposition, approximation guarantees, and scalability bottlenecks. The paper shows that mathematical programming is most useful not as a claim that all learning is LP or MIP, but as a disciplined interface between predictions and constrained decisions.

Chaosheng Dong

Topic pending

Ask PDF

Oct 26, 2026

Constraint Learning by Optimizing over Trained Neural Networks: A Pragmatic Tutorial

Constraint learning is an emerging paradigm of modeling optimization problems with the help of machine learning. In this paradigm, trained machine learning models are embedded into the optimization model. For example, we can learn constraints empirically from available data, or we can avoid using a nonlinear objective function by learning a simpler approximation for it. Neural networks become a compelling option if the machine learning models must capture more elaborate and nuanced relationships. However, optimization models embedding neural networks may become too large or too slow to solve. In this tutorial, we present practical considerations for an effective and efficient use of constraint learning with neural networks and validate it with a case study highlighting the benefit of smaller and sparser networks.

Jiaxiao Fang, Thiago Serra

University of Iowa

Constrained Optimization

Ask PDF

Abstract

Constrained Optimization

Explore similar work

Constraint-Aware Training

Mathematical Programming in Machine Learning and Artificial Intelligence: A Unified Taxonomy of Models and Applications

Constraint Learning by Optimizing over Trained Neural Networks: A Pragmatic Tutorial