monce-optimization

Large-scale combinatorial optimization powered by uniform 3-SAT reduction and speculative EC2 compute.

npdollars live 7 encoders 30x on PHP(12,11)

Try it live Read the paper

30x

Speedup on PHP(12,11)

~10ms

Local reduction time

External dependencies

How it works

Problem → CNF → Uniform 3-SAT (local, ~10ms) → npdollars (remote, budget EC2) → Solution

The uniform 3-SAT reduction balances variable frequency across all clauses. This regularized topology lets SAT solvers prune exponentially faster on structured instances — the harder the problem, the bigger the gain.

Supported problems

Problem	Encoder	Use case
Sudoku	`sudoku.encode(grid)`	Grid puzzles
Graph Coloring	`graph_coloring.encode(V, E, k)`	Scheduling, allocation
k-Clique	`clique.encode(V, E, k)`	Dense subgraphs
Vertex Cover	`vertex_cover.encode(V, E, k)`	Sensor placement
Subset Sum	`subset_sum.encode(W, T)`	Bin packing
0/1 Knapsack	`knapsack.encode(W, V, C, M)`	Resource allocation
Job-Shop	`scheduling.encode(jobs, M, T)`	Manufacturing

Install

pip install git+https://github.com/Monce-AI/monce-optimization.git