GravOpt Pro

Adaptive MAX-CUT Optimizer with Meta-Engine

95.91% of best known solutions · G81 (20,000 nodes) · 5 minutes · CPU only · <80 MB RAM

---

Empirical Phase Transition Discovery

Preprint (v7, May 2026): doi.org/10.5281/zenodo.20400062
Submitted to: SIAM Journal on Discrete Mathematics (June 2026)

We report a universal empirical phase transition in the MAX-CUT optimization landscape near the NP-hard inapproximability bound:

T_empirical = 0.950 ± 0.001   (255 measurements)
16/17 (Håstad, 2001) = 0.9412
Δ = 0.009

Key results:

• T_emp invariant across 6 graph topologies (Erdős-Rényi, Barabási-Albert, Watts-Strogatz, 4-Regular, Planted Partition, Complete Bipartite)
• T_emp invariant across 5 graph sizes (n = 500 to 10,000)
• T_emp does NOT converge to 16/17 as n → ∞ (slope = -6e-8)
• First Improvement Time ratio peaks at 588x at T = 0.94

---

Results on Gset Benchmark

Graph	Vertices	Meta-Engine	% of Best Known	Time
G62	7,000	4,656	95.61%	2 min
G66	9,000	6,076	95.47%	2 min
G67	10,000	6,664	96.02%	2 min
G70	10,000	9,347	97.97%	2 min
G72	10,000	6,690	95.46%	2 min
G77	14,000	9,476	95.33%	3 min
G81	20,000	13,428	95.50%	5 min
Mean	—	—	95.91%	<5 min

All results: standard CPU · <80 MB RAM · No GPU · Fixed T₁=0.85, T₂=0.92

---

Comparison

Algorithm	CUT	% of Best	Time	Hardware
Cosm (Zick, 2025)	14,060	100%	—	specialized CMOS
GravOpt Meta-Engine	13,428	95.50%	5 min	standard CPU
BLS (Benlic & Hao, 2013)	14,030	99.8%	up to 5.6 hours	CPU
Fixed Perturb 10%	12,842	91.34%	2 min	CPU

---

Meta-Engine Logic

CUT < 85%  →  Perturb 10% + LS  (coarse)
CUT 85-92% →  Perturb  3% + LS  (medium)
CUT > 92%  →  Perturb  1% + LS  (fine)

W = Q·D − T (Kretski vitality formula)
+4.39% vs fixed Perturb 10%

---

Quick Start

pip install numpy numba
python meta_engine.py G81.txt run 300
python meta_engine.py G81.txt compare 120
python threshold_discovery.py

---

Repository Structure

meta_engine.py           Adaptive Meta-Engine (main solver)
threshold_discovery.py   Phase transition measurement
gravopt.py               GravOptAdaptiveE_QV (PyTorch variant)
vlsi_bipartition.py      VLSI vs FM comparison
bms_ev_100cells.py       BMS EV thermal simulation
GravOpt_Pro_Demo.ipynb   Interactive demo notebook

---

Applications

5G Frequency Assignment

Network	Stations	Time	Gain
City	1,200	19 sec	+21% interference reduction
National	5,000	80 sec	~+1.5 dB SINR
Major city	8,000	~2.5 min	~+2.0 dB SINR

VLSI Bi-Partitioning (ISPD98)

Benchmark	Gates	vs FM (1982)
ibm01	12,752	+14.6%
ibm02	19,601	+8.5%
ibm03	23,136	+15.6%

BMS Thermal Balancing (NASA dataset)

• +22.2% temperature uniformity
• +15.0% reduced degradation (100-cell EV pack)

---

Reproducibility

All benchmark data and code:

• Zenodo v7: doi.org/10.5281/zenodo.20400062
• 255 measurements across 9 conditions
• Seeds: [1, 2, 3, 4, 5]
• System sizes: [500, 1000, 2000, 5000, 10000]

---

IP & Licensing

Patent Application № 114200, Bulgarian Patent Office (pending).

• Academic: Free with citation
• Commercial: Contact for license

---

Citation

@misc{kretski2026maxcut,
  author = {Kretski, Dimitar Vasilev},
  title  = {Empirical Phase Transition Near the NP-Hard
            Inapproximability Bound in MAX-CUT Local Search},
  year   = {2026},
  doi    = {10.5281/zenodo.20400062},
  note   = {Submitted to SIAM Journal on Discrete Mathematics}
}

---

References

• Zick (2025). arXiv:2505.18508
• Håstad (2001). Journal of the ACM, 48(4)
• Benlic & Hao (2013). Engineering Applications of AI, 26(3)
• Goemans & Williamson (1995). Journal of the ACM, 42(6)

---

Made in Bulgaria · Independent Research
kretski1@gmail.com