# CombiLatent

A standalone research project developing a general two-phase neural framework for solving NP-hard combinatorial optimization problems via continuous latent-space optimization.

## Problem: Permutation Flow Shop Scheduling (PFSP)

Given n jobs and m machines, find the job ordering (permutation) that minimizes makespan (total completion time). NP-hard. Classical heuristics (NEH, CDS, Palmer) are strong baselines. The PFSP is underrepresented in the Neural Combinatorial Optimization (NCO) literature, which has focused mostly on routing problems (TSP, VRP).

## The CombiLatent Framework

Two phases, applicable to any combinatorial problem with a well-defined objective:

**Phase 1 — Surrogate training**
Train a Transformer to predict the objective value (makespan) of any candidate solution (job permutation). The model's token embedding table learns rich job representations that capture the structure of the problem. Trained via supervised regression on (permutation → makespan) pairs.

**Phase 2 — Latent optimization**
Freeze the surrogate. Introduce a learnable tensor X₂ ∈ ℝⁿˣᵈ (one embedding per schedule slot). Minimize:

```
L_total = f_θ(X₂) + λ · L_Sinkhorn(X₁, X₂)
```

where `f_θ` is the frozen surrogate and `L_Sinkhorn` is Sinkhorn divergence (entropic OT) between the learnable slots X₂ and the frozen job embeddings X₁. The Sinkhorn term enforces that X₂ remains anchored to a valid permutation of jobs. After convergence, the Hungarian algorithm snaps X₂ back to a discrete sequence.

Langevin-like Gaussian noise is injected into X₂ periodically during Phase 2 to escape local minima.

## Architecture

**Surrogate model (GPT-style):** Decoder-only Transformer with relative positional embeddings (motivated by the sequential, DP-like nature of makespan computation).

| Config | Embedding dim | Heads | Layers | Params |
|--------|--------------|-------|--------|--------|
| Sm     | 64           | 4     | 2      | ~100K  |
| Mm     | 128          | 8     | 4      | ~800K  |
| Bm     | 256          | 16    | 8      | ~6M    |

**Phase 2 hyperparameters (best config):** λ=2, Sinkhorn ε=0.01, 40 Sinkhorn iterations, 1500 gradient descent steps, Langevin noise every 200 steps.

Hardware: single NVIDIA RTX 3070 (8GB VRAM).

## Iteration 1: Experimental Setup

- **15 PFSP instances:** n ∈ {7,8,9} jobs, m ∈ {2,3,4,5,6} machines, execution times ~ U(0,1)
- **Exhaustive datasets:** all permutations enumerated exactly (feasible since n ≤ 9)
- **Dataset degradation (top_0 to top_4):** removes the 0–4 best schedules from training data, simulating real-world conditions where the global optimum is unknown
- **Grid search:** 3 model sizes × 4 weight decays (0.1, 1.0, 5.0, 10.0) = 60 configs
- **Metric:** "Min Rank k" = number of instances (out of 15) where CombiLatent ranked in the top k against NEH, CDS, and Palmer (k ∈ {1, 2, 3})

## Iteration 1: Key Results

**Best config:** Sm + weight decay 10.0 → Min Rank 3 of ~11–12/15 across all degradation levels.

1. **Smaller models win.** Bm overfits to combinatorial artifacts; its latent manifold is too complex for Phase 2 gradient descent. Sm's limited capacity forces it to learn the "physics" of scheduling, giving better inductive bias.

2. **Weight decay is the most impactful hyperparameter.** High weight decay (5.0–10.0) smooths the latent loss landscape, making Phase 2 gradient descent more reliable. Its importance increases as training data degrades.

3. **Sinkhorn is structurally necessary, not optional.** Ablation: removing Sinkhorn collapses Min Rank 1 from ~2/15 to 1/15 and Min Rank 3 from ~11/15 to ~6/15. Without it, X₂ converges to continuous vectors not corresponding to any real job.

4. **Langevin noise helps moderately.** Removing it drops Min Rank 3 from ~11–12/15 to ~8–9/15. High weight decay already provides significant landscape smoothing; Langevin is complementary.

## Limitations (to address in next iterations)

1. **Instance-specific retraining.** The surrogate must be retrained for each PFSP instance. Fix: condition the surrogate on an MLP-encoded representation of the execution time matrix, enabling generalization across instances.

2. **Latent landscape non-convexity.** Phase 2 gradient descent is prone to local minima. Ideas: latent Tabu-search (penalize proximity to detected local minima), principled non-convex optimizers.

3. **Scale.** Experiments restricted to n ∈ [7,9], m ∈ [2,6] due to exhaustive enumeration cost. Target: Taillard benchmarks (n ∈ [20, 500]).

## Repository Structure

```
deprecated/                         # Iteration 1 — all artifacts
  source/
    create_dataset.py               # PFSP instance generation + makespan computation
    process_dataset.py              # Filter, train/val split, normalize
    train.py                        # GPT architecture + Phase 1 training loop
    recover_schedules.py            # Phase 2: Sinkhorn optimization + Hungarian recovery
    launch_create_dataset.py        # Grid search launcher for dataset generation
    launch_process_dataset.py       # Grid search launcher for processing
    launch_train.py                 # Grid search launcher for training
    launch_recover_schedules.py     # Grid search launcher for Phase 2
    viz_train.ipynb                 # Phase 1 training visualization
    viz_rs.ipynb                    # Phase 2 optimization visualization
  presentation/
    final_report.pdf                # Full paper with results, ablations, related work
```