CombiLatent: Neural Combinatorial Optimization via Latent Space Search under Sinkhorn Divergence Regularization

We introduce \textbf{CombiLatent}, a general two-phase neural framework for solving NP-hard combinatorial optimization problems via continuous latent-space optimization. A Transformer surrogate is first trained to predict the objective value of any candidate solution, embedding the combinatorial structure into a differentiable latent space. A learnable solution tensor is then optimized by gradient descent against the frozen surrogate, with Sinkhorn divergence (entropic optimal transport) enforcing permutation validity. As a first case study, we instantiate CombiLatent on the \textbf{Permutation Flow Shop Scheduling Problem (PFSP)}---a problem of significant industrial and environmental relevance that remains surprisingly underexplored in the neural combinatorial optimization literature. Our experiments show that CombiLatent is competitive with established PFSP heuristics (NEH, CDS, Palmer), and yield insights into how model capacity and regularization shape the latent optimization landscape.