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
M
Set of all possible AI models (candidates)
IConst
Set of inputs for which output constraints must be satisfied
Table 1: Summary of notations
Figure 1: Architecture of column model si 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 ∑i∈Mλisi(x) .
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.
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.
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, ko=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 kh 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
kh=2 , rest optimize
54.8
78.7
CG-proba
kh=2 , rest optimize
68.5
69.3
CG-margin
kh=5 , rest optimize
51.7
66.1
Table 2: Test accuracy (%) on 2000 MNIST images (MLP, h=4 , all-constrained mode unless stated). kh : images per class in hard set IConst . 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% at n=100 ) due to seed variability.
Method
n=100
n=1000
Baseline (single model, CE)
56.08
70.98
Penalty (L2), λ=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.
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.
Figure 12: Arc violations for Arc 13 in the Polska instance (#d,#p)=(5,3) .
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.