Maximum Entropy Relaxation of Multi-Way Cardinality Constraints for Synthetic Population Generation

François Pachet; Jean-Daniel Zucker

cs.AIMar 23, 2026

Maximum Entropy Relaxation of Multi-Way Cardinality Constraints for Synthetic Population Generation

Authors: François Pachet, Jean-Daniel Zucker

Organizations: ImagineAllThePeople, Paris, France · IRD, UMMISCO, Sorbonne Universit´e, France

Abstract

Generating synthetic populations from aggregate statistics is a core component of microsimulation, agent-based modeling, policy analysis, and privacy-preserving data release. Beyond classical census marginals, many applications require matching heterogeneous unary, binary, and ternary constraints derived from surveys, expert knowledge, or automatically extracted descriptions. Constructing populations that satisfy such multi-way constraints simultaneously poses a significant computational challenge. We consider populations where each individual is described by categorical attributes and the target is a collection of global frequency constraints over attribute combinations. Exact formulations scale poorly as the number and arity of constraints increase, especially when the constraints are numerous and overlapping. Grounded in methods from statistical physics, we propose a maximum-entropy relaxation of this problem. Multi-way cardinality constraints are matched in expectation rather than exactly, yielding an exponential-family distribution over complete population assignments and a convex optimization problem over Lagrange multipliers. We evaluate the approach on NPORS-derived scaling benchmarks with 4 to 40 attributes and compare it primarily against generalized raking. The results show that MaxEnt becomes increasingly advantageous as the number of attributes and ternary interactions grows, while raking remains competitive on smaller, lower-arity instances.

Figures & tables

Problem	Unary	Binary	Ternary	Total
4-Var	12	54	92	158
12-Var	35	117	1 082	1 234
20-Var	67	510	2 249	2 826
28-Var	107	703	3 824	4 634
40-Var	197	1 329	17 883	19 409

Table 1: Number of nonzero atomic cells induced by the selected unary, binary, and ternary marginals in the NPORS-derived scaling benchmarks (

N=5{,}626

in the source population). Reported counts correspond to observed support sizes summed over retained marginals, not simply to the number of variables, pairs, or triples. For

K\geq 20

, the numbers of retained binary and ternary marginals are capped at 50.

Figure 1: Scalability of the CP-SAT solver. Left: 12 variables (315 target cells); the solver proves optimality up to

n=30

(green dots). Right: 24 variables (3,621 target cells); the solver never proves optimality. Markers indicate solver status: optimal (proved best), feasible (not proved optimal), and timeout/infeasible. Error bars show the range over 3 random seeds. The time limit is 120 s per run.

Figure 2: Competence map of MaxEnt vs. Raking (2D view): relative advantage as a function of population size and number of variables, for arity 2 and arity 3. Green = MaxEnt better; red = Raking better.

Figure 3: Competence map of MaxEnt vs. Raking (3D view): height encodes MaxEnt precision (1 $-$ err); color encodes relative advantage. Green regions indicate configurations where MaxEnt wins.

Figure 4: Mean relative error vs. population size for 28-variable instances (left: arity 2; right: arity 3). MaxEnt consistently outperforms Raking for small populations and high arity.

Figure 5: Mean relative error vs. population size for 40-variable instances (left: arity 2; right: arity 3). The advantage of MaxEnt over Raking grows with the number of variables.

Config	Pop. $N$	ME	Raking	Winner	Gap
12 variables
12-var, arity=2	1 000	0.036	0.030	Raking	$-17\%$
12-var, arity=3	100	0.129	0.176	ME	$+27\%$
12-var, arity=3	5 626	0.026	0.026	equal	$\approx 0$
12-var, arity=3	100 000	0.017	0.009	Raking	$-46\%$
20 variables

Table 2: Mean relative constraint error (lower is better) on representative NPORS-derived scaling benchmarks. Gap = relative reduction over the weaker method. At

K\leq 12

, the winner depends on arity and

N

. At

K\geq 28

, MaxEnt wins in all configurations we tested.

Situation	Guidance
$K\leq 12$ , arity $=2$	Raking is a strong baseline and can be preferred when speed is the main concern.
$K\leq 12$ , arity $=3$ , small or moderate $N$	MaxEnt often yields lower error and is worth trying first.
$K\approx 20$	Method choice becomes regime-dependent; MaxEnt is safer when ternary interactions matter.
$K\geq 28$	MaxEnt consistently outperformed raking on our benchmarks.
$K=40$	The largest empirical gaps favor MaxEnt by a wide margin.

Table 3: Empirical guidance on the NPORS-derived scaling benchmarks. These recommendations summarize observed trends and should not be read as universal guarantees.

Synthetic Population Generation

See all 18 papers

Scalable Maximum Entropy Population Synthesis via Persistent Contrastive Divergence
Mar 28, 2026Mirko Degli EspostiSynthetic Population Generation Synthetic Data Generation
Department of Physics and Astronomy, City Science Lab University of Bologna, Bologna, Italy
Manifold Sampling via Entropy Maximization
May 12, 2026Cornelius V. Braun, Tilman Burghoff, Marc ToussaintMarkov Chain Monte Carlo Constrained Sampling
Technische Universität Berlin · Robotics Institute Germany
Population-Level Generative Modeling for Ranking Data
Aug 9, 2026Zhaoyang ShiSynthetic Data Generation
Center for Applied Mathematics, Fudan University Shanghai, China

Mar 28, 2026J/K move · Enter open · S save

Scalable Maximum Entropy Population Synthesis via Persistent Contrastive Divergence

Mirko Degli Esposti

Department of Physics and Astronomy, City Science Lab University of Bologna, Bologna, Italy

Synthetic Population Generation Synthetic Data Generation

Open paper AskPDF arXiv

Maximum entropy (MaxEnt) modelling provides a principled framework for generating synthetic populations from aggregate census data, without access to individual-level microdata. The bottleneck of exact-enumeration approaches is expectation computation by explicit summation over the full tuple space

\cX

, which becomes infeasible for more than

K \approx 20

categorical attributes; sampling-based alternatives exist but rely on Metropolis-type schemes that require proposal tuning and rejection steps. We propose GibbsPCDSolver, a stochastic replacement for this computation based on Persistent Contrastive Divergence (PCD): a persistent pool of

N

synthetic individuals is updated by Gibbs sweeps at each gradient step, providing a stochastic approximation of the model expectations without ever materialising

\cX

. We validate the approach on controlled benchmarks and on Syn-ISTAT, a

K{=}15

Italian demographic benchmark with analytically exact marginal targets derived from ISTAT-inspired conditional probability tables. Scaling experiments across

K \in \{12, 20, 30, 40, 50\}

confirm that GibbsPCDSolver maintains

\MRE \in [0.010, 0.018]

while

|\cX|

grows eighteen orders of magnitude, with runtime scaling as

O(K)

rather than

O(|\cX|)

. On Syn-ISTAT, GibbsPCDSolver reaches

\MRE{=}0.03

on training constraints and -- crucially -- produces populations with effective sample size

\Neff = N

versus

\Neff \approx 0.012\,N

for generalised raking, an

86.8{\times}

diversity advantage that is essential for agent-based urban simulations.

Abstract

Synthetic Population Generation

Explore similar work

Scalable Maximum Entropy Population Synthesis via Persistent Contrastive Divergence

Manifold Sampling via Entropy Maximization

Population-Level Generative Modeling for Ranking Data