Univerzálne optimalizačné jadro
Universal optimization core
Pri hľadaní trasy je kandidátom poradie zastávok. Pri diferenciálnej rovnici to môžu byť koeficienty funkcie. Adaptér v oboch prípadoch určí, ako kandidáta zmeniť a podľa čoho posúdiť výsledok. Tento princíp spája výskum RoboPol Refined so štyrmi aplikáciami.
A candidate route is an ordered list of stops. For a differential equation, a candidate can be a set of function coefficients. In each case an adapter defines how to change a candidate and how to evaluate it. This principle connects research on RoboPol Refined with four applications.
RoboPol Refined je optimalizačné jadro v Ruste. Riadi hľadanie a zlepšovanie kandidátov; adaptér mu poskytuje pravidlá konkrétneho problému, spôsob hodnotenia a užitočné zmeny riešenia.
RoboPol Refined is an optimization core written in Rust. It manages candidate search and improvement; an adapter supplies the problem rules, scoring and useful changes to a solution.
Určuje reprezentáciu stavu alebo funkcie, skóre či rezíduum a podmienky prípustnosti. Dodáva doménové ťahy, odporúčané väzby (guidance edges) a opravy kandidátov.
It defines the state or function representation, score or residual, and feasibility rules. It supplies domain moves, guidance edges and candidate repairs.
Kombinuje guided beam a frontier search, lokálne zlepšovanie, perturbácie a rekombináciu. Pracuje s rozmanitými kandidátmi, zdieľaným učením, paralelnými behmi a diagnostikou; pri stagnácii riadi ďalší prieskum.
It combines guided beam and frontier search, local improvement, perturbation and recombination. It manages diverse candidates, shared learning, parallel runs and diagnostics, and directs further exploration when progress stalls.
Výsledok sa prepočíta a skontroluje voči vstupným pravidlám. Optimum je potvrdené pri zhode s dokázanou hodnotou alebo po uzavretí dolnej hranice exaktnou metódou.
The result is rescored and checked against the input rules. Optimality is established by matching a proven value or closing the lower bound with an exact method.
Vyberte si z 36 adaptérov a 74 vzorových úloh alebo importujte vlastný adaptér. Pri farbení grafu môžete napríklad zmeniť hrany a počet farieb a skontrolovať konflikty vo výsledku. Prostredie zahŕňa aj presné počítanie a symbolickú algebru.
Choose from 36 adapters and 74 sample tasks, or import your own adapter. In a graph-coloring task, for example, change the edges and palette size and inspect conflicts in the result. The workspace also offers exact counting and symbolic algebra.
Naplánujte trasu medzi bodmi alebo jazdy pre viac vozidiel. Aplikácia pracuje s 2D a 3D súradnicami aj s cestnými vzdialenosťami a ponúka Refined, LKH a ich hybridnú metódu.
Plan a tour through a set of locations or routes for several vehicles. Work with 2D or 3D coordinates or road distances and choose Refined, LKH or their hybrid method.
Rozvrhnite operácie na strojoch podľa pracovných zmien, odstávok a priorít zákaziek. Výsledný plán môžete porovnať s riešením CP-SAT.
Schedule operations on machines around shifts, downtime and job priorities. Compare the resulting schedule with a CP-SAT solution.
Rozložte obdĺžnikové alebo polygonové dielce na tabule alebo uložte boxy do 3D kontajnerov. Aplikácia kontroluje hranice a kolízie a vyhodnotí počet použitých tabúľ či kontajnerov.
Lay rectangular or polygonal parts on sheets, or pack boxes into 3D containers. The application checks boundaries and collisions and reports how many sheets or containers the layout uses.
Pri porovnaní dvoch trás rozhoduje ich dĺžka. Pri matematickej konštrukcii môže o úspechu rozhodnúť presná kontrola vlastnosti, pri aproximácii funkcie veľkosť rezídua. Nasledujúce experimenty ukazujú, čo sa dá v každom prípade z výsledku vyčítať.
Two routes can be compared by their lengths. A mathematical construction may admit an exact check, while a function approximation can be assessed by its residual. The experiments below show what each kind of result establishes.
Max-Cut, set cover, farbenie grafov, knapsack, bin packing, partition, QAP, Golombove pravítka a Costasove polia. Rozhranie jadra sa dá napojiť aj na priraďovacie úlohy (assignment). Doménové ťahy a guidance edges prenášajú štruktúru úlohy do hľadania.
Max-Cut, set cover, graph coloring, knapsack, bin packing, partition, QAP, Golomb rulers and Costas arrays. The core interface can also support assignment problems. Domain moves and guidance edges carry the problem structure into the search.
Experimenty zahŕňajú funkcie Rastrigin, Ackley, Rosenbrock a členitú testovaciu krajinu (rugged landscape). Kandidátom je bod v priestore parametrov a cieľom je čo najnižšia hodnota funkcie.
Experiments include Rastrigin, Ackley, Rosenbrock and a rugged test landscape. A candidate is a point in parameter space, and the objective is to minimize the function value.
Ak sa úloha dá vyjadriť ako priestor kandidátnych hypotéz, Refined môže hľadať sľubné objekty, konfigurácie alebo protipríklady. Presný overovací algoritmus (verifier/oracle) potom rozhodne, či kandidát spĺňa požadované vlastnosti.
When a problem can be expressed as a space of candidate hypotheses, Refined can search for promising objects, configurations or counterexamples. An exact verifier or oracle then determines whether a candidate satisfies the required properties.
Implementovaný adaptér hľadá zafarbenie hrán grafu bez zakázanej monochromatickej kliky. Skóre naviguje hľadanie; presná kontrola potvrdzuje platnosť nájdeného zafarbenia.
The implemented adapter searches for an edge coloring without a forbidden monochromatic clique. The score guides the search; exact verification establishes the validity of a discovered coloring.
Adaptér hľadá maticu s prvkami ±1 a nulovou chybou ortogonality. Refined navrhuje a opravuje kandidátov, pričom overovací algoritmus presne kontroluje ich ortogonalitu.
The adapter searches for a matrix with ±1 entries and zero orthogonality error. Refined proposes and repairs candidates, while the verifier checks their orthogonality exactly.
Diferenciálne rovnice · konkrétne nájdené riešenia
Differential equations · solutions found
Refined hľadá funkciu priamo podľa rezídua rovnice a okrajových alebo periodických podmienok. Adaptéry používajú Chebyshevove a Fourierove koeficienty, spline uzly či spektrálne bázy. Výskumné experimenty priniesli tieto výsledky:
Refined searches directly for a function using the residual of the equation and its boundary or periodic conditions. Adapters use Chebyshev and Fourier coefficients, spline nodes or spectral bases. Research experiments produced the following results:
Nelineárne okrajové úlohy
Nonlinear boundary-value problems
Refined našiel obe známe vetvy riešenia Bratuovej rovnice. Ďalšie experimenty zahŕňali Allenovu–Cahnovu rovnicu s vnútornou prechodovou vrstvou a asymetrickú nútenú Duffingovu rovnicu.
Refined found both known solution branches of the Bratu equation. Further experiments included the Allen–Cahn equation with an internal transition layer and an asymmetric forced Duffing equation.
Adaptívne zahusťovanie spline siete zvyšuje rozlíšenie v miestach veľkého rezídua.
Adaptive spline-mesh refinement increases resolution at residual hotspots.
Periodické ODE
Periodic ODEs
V nelineárnom dvojstavovom ODE systéme Refined našiel tri periodické orbity vrátane nestabilnej orbity. Periodický priebeh opisuje Fourierova reprezentácia.
In a nonlinear two-state ODE system, Refined found three periodic orbits, including an unstable orbit. A Fourier representation describes the periodic solution.
Hľadanie prebieha priamo v priestore periodických funkcií, bez časovej integrácie.
Search operates directly in the space of periodic functions, without time integration.
Spektrálne PDE
Spectral PDEs
Experiment s dvojrozmernou nelineárnou eliptickou PDE používal spektrálnu sínusovú bázu. Refined vyhľadal všetkých šesť kompaktných vetiev skúmanej úlohy.
The two-dimensional nonlinear elliptic PDE experiment used a spectral sine basis. Refined found all six compact branches of the studied problem.
Nájdené vetvy prešli oddelenou validáciou na kontrolných bodoch.
The discovered branches underwent separate validation at check points.
Priame reziduálne hľadanie: tieto adaptéry používajú Refined bez externého ODE, BVP alebo PDE solvera. Jadro hľadá reprezentáciu funkcie; výsledok sa kontroluje na oddelených validačných bodoch. Každá trieda rovníc má vlastnú reprezentáciu a validačné pravidlá.
Direct residual search: these adapters use Refined without an external ODE, BVP or PDE solver. The core searches for a function representation; the result is checked at separate validation points. Each equation class has its own representation and validation rules.
Pri trasách meriame dĺžku; pri plánovaní výroby čas dokončenia alebo meškanie podľa priorít. Nesting a packing porovnávajú platné kompletné rozloženia, cenu, počet tabúľ či kontajnerov a ďalšie doménové kritériá.
Routes are scored by tour length; production schedules by completion time or priority-weighted tardiness. Nesting and packing compare valid complete layouts, cost, sheet or container count and further domain criteria.
TSP Solver 3.05 · 07. 09. 2026
Refined Balanced našiel kratšiu trasu v 27 z 30 prípadov. V troch sa dĺžky zhodovali. Samostatný LKH nemal kratšiu trasu ani raz.
Refined Balanced found shorter tours in 27 of 30 cases. The other three tied. Standalone LKH did not return a shorter tour in any case.
30 upravených tetrahedrálnych inštancií T′n,m · 157 až 4 396 bodov · 120 výsledkov. Porovnávali sme rovnaké vstupné body a LKH-3.0.10 s nastavením DELAUNAY.
30 modified tetrahedron instances T′n,m · 157 to 4,396 points · 120 results. All methods received the same input points; the baseline was LKH-3.0.10 with DELAUNAY candidates.
| Metóda / profil Method / profile | Inštancie Instances |
|---|---|
| Refined Balanced | 24 / 30 |
| Refined Heavy | 27 / 30 |
| LKH + Refined Balanced | 28 / 30 |
| LKH · DELAUNAY | 3 / 30 |
LKH bol riadený parametrami vyhľadávania: DELAUNAY, RUNS=10, MAX_TRIALS=1, MAX_CANDIDATES=5, MOVE_TYPE=5, PATCHING_C=1, PATCHING_A=1, INITIAL_PERIOD=100. Refined používal produkčné profily Balanced a Heavy; hybrid používal Balanced.
LKH search was configured with DELAUNAY, RUNS=10, MAX_TRIALS=1, MAX_CANDIDATES=5, MOVE_TYPE=5, PATCHING_C=1, PATCHING_A=1 and INITIAL_PERIOD=100. Refined used the production Balanced and Heavy profiles; the hybrid used Balanced.
Výsledok dokladá lepšiu kvalitu trás pre túto rodinu a tieto nastavenia. Časy jednotlivých behov sú v CSV. Každá kombinácia inštancie a profilu má jeden úspešný beh; dva neúspešné štarty hybridu boli zopakované.
The results demonstrate better tour quality for this family and these settings. Individual runtimes are in the CSV. Each instance/profile combination has one successful run; two failed hybrid initializations were retried.
Solvery používali EXACT_2D. Dĺžky v benchmarku sú vyhodnotené na pôvodnej nezaokrúhlenej geometrii so 70-cifernou presnosťou; zhoda so známym optimom používa toleranciu 10−40. Referenčné optimum vychádza z dokázanej konštrukcie rodiny Hougardy–Zhong.
The solvers used EXACT_2D. Benchmark lengths are scored on the original unrounded geometry at 70-digit precision; agreement with the known optimum uses a 10−40 tolerance. The reference optimum follows from the proven Hougardy–Zhong family construction.
Výsledné trasy a nastavenia (JSON) Returned tours and settings (JSON)JSSP · 09. 09. 2026
Refined Custom dosiahol porovnateľnú kvalitu s CP-SAT. Z 30 dvojíc s výsledkom oboch metód mal 24-krát zhodný makespan, 3-krát kratší a 3-krát dlhší.
Refined Custom achieved comparable quality to CP-SAT. Of 30 pairs with results from both methods, 24 had equal makespan, 3 favored Refined and 3 favored CP-SAT.
12 scenárov · 3 seedy · 72 behov · 20 sekúnd na beh · rovnaké 4 logické CPU a 4 workery. Sada zahŕňa klasické JSSP úlohy, fabriky, kalendár a priority.
12 scenarios · 3 seeds · 72 runs · 20 seconds per run · the same 4 logical CPUs and 4 workers. The suite covers classic JSSP, factories, calendars and priorities.
| Výsledok Outcome | Dvojice Pairs |
|---|---|
| Kratší s Refined Shorter with Refined | 3 / 30 |
| Zhodný Equal | 24 / 30 |
| Kratší s CP-SAT Shorter with CP-SAT | 3 / 30 |
Priority: v troch samostatných dvojiciach bolo vážené meškanie zákaziek s Refined priemerne o 1,53 % nižšie.
Priorities: across three separate pairs, Refined reduced weighted job tardiness by 1.53% on average.
Na fabrike so 46 080 operáciami vrátil Refined platný plán vo všetkých troch behoch. CP-SAT v 20-sekundovom limite kompletný plán nevrátil. Tieto tri dvojice sú v celkových počtoch, ale nemajú číselné porovnanie makespanu.
On the 46,080-operation factory, Refined returned a valid schedule in all three runs. CP-SAT did not return a complete schedule within the 20-second budget. These three pairs remain in the totals but have no numeric makespan comparison.
Všetkých 69 vrátených plánov prešlo validáciou. Kalendárové ciele používajú rovnaký vstup, preto 12 scenárov predstavuje 11 odlišných datasetov. Meranie prebehlo na jednom počítači vo WSL2; výsledky opisujú túto sadu a tento rozpočet.
All 69 returned schedules passed validation. The two calendar objectives reuse one input, so the 12 scenarios represent 11 distinct datasets. Tests ran on one WSL2 workstation; the results describe this suite and budget.
JSSP Refined používa CP-SAT na pomocné hľadanie a overenie optima. Podrobný report obsahuje presné nastavenia, hashe vstupov, výsledné plány a postup reprodukcie.
JSSP Refined uses CP-SAT for auxiliary search and optimality checks. The full report includes exact settings, input hashes, returned schedules and reproduction instructions.
Nesting & Packing · PackingSolver
Obdĺžniky: 25 výhier Refined, 10 remíz a 10 výhier PackingSolvera pri jednom formáte tabule. Všetkých 45 párov malo rovnakú cenu aj počet tabúľ; rozdiely vznikli v zvyškoch a následných výrobných kritériách.
Rectangles: 25 Refined wins, 10 ties and 10 PackingSolver wins with single-format stock. All 45 pairs tied on cost and sheet count; differences came from offcuts and subsequent manufacturing criteria.
| Doména / dátum Domain / date | Zákazky Orders | Výhry Refined Refined wins | Remízy Ties | Výhry PackingSolver PackingSolver wins | Neporovnateľné Not comparable |
|---|---|---|---|---|---|
| Obdĺžniky · jeden formát Rectangles · single format2026-09-30 | 15 | 25 | 10 | 10 | 0 |
| Polygony Polygons2026-09-28 | 30 | 54 | 30 | 0 | 6 |
| 3D boxy 3D boxes2026-09-28 | 35 | 64 | 2 | 31 | 8 |
Polygony: všetkých 84 porovnateľných párov sa zhodovalo v cene a počte tabúľ; výhry sú v sekundárnej kvalite rozloženia. Pri 3D balení sú výhry Refined vo voľnom priestore a rozložení; v cene a počte kontajnerov bolo 89 remíz a 8 výhier PackingSolvera.
Polygons: all 84 comparable pairs tied on cost and sheet count; wins concern secondary layout quality. In 3D packing, Refined wins concern free space and layout; cost and container count produced 89 ties and 8 PackingSolver wins.
V 2D sa kontroluje poloha, orientácia a odstup dielcov od seba aj od hranice tabule. Obdĺžnikové prípady v tejto sade používajú jeden formát tabule. V 3D sa kontrolujú rozmery kontajnera a kolízie boxov. Podmienky podopretia sú uvedené osobitne.
In 2D the checks cover part positions, orientations, clearances and sheet boundaries. The rectangular cases in this set use a single stock format. The 3D checks cover container bounds and box collisions. Support conditions are reported separately.
Obdĺžniky boli znovu merané 30. 9. 2026: 15 odlišných zákaziek, tri profily, 45 porovnaní, bez časového limitu pre oba solvery. Polygony a 3D balenie používajú staršiu verziu z 28. 9. 2026: 30 a 35 zákaziek. Limity profilov boli 3/15/60 s pre polygony a 2,5/5/15 s pre 3D balenie.
Rectangles were rerun on 30 September 2026: 15 distinct orders, three profiles, 45 comparisons, no wall-clock limit for either solver. Polygons and 3D packing use the earlier revision from 28 September 2026: 30 and 35 orders. Profile limits were 3/15/60 s for polygons and 2.5/5/15 s for 3D packing.
Výhry sa prideľujú iba párom s nezávisle overeným platným a kompletným výsledkom na oboch stranách. Šesť chybových polygonových párov a osem neporovnateľných 3D párov sú mimo skóre. Pri 3D porovnaní sa nevyžadovalo podopretie, preto nejde o fyzický nakladací plán. Samostatné rameno Refined s podopretím malo 105/105 platných kompletných výsledkov a nezapočítava sa do výhier.
Wins require independently validated, complete results on both sides. Six polygon error pairs and eight non-comparable 3D pairs are outside the score. The 3D comparison did not require base support and is not a physical loading plan. A separate Refined support-required cohort returned 105/105 valid complete results and contributes no comparison wins.
Syntetická vývojová sada na jednom počítači; päť vstupných seedov na scenár, seed Refined 2026 a jeden beh na vstup/profil/solver. Profily nie sú nezávislé zákazky. Rozdielne dátumy a rozpočty nespájame do jedného skóre ani do tvrdenia o všeobecnej prevahe.
Synthetic development corpus on one workstation; five input seeds per scenario, Refined seed 2026 and one run per input/profile/solver. Profiles are not independent orders. Different dates and budgets are not pooled into one score or a claim of general superiority.
Vlastné adaptéry, overené výpočty a škálovanie vyhľadávania podľa hardvéru · Zenodo
User-defined adapters, verified calculations and hardware-scalable search · Zenodo
Architektúra jadra a doménové adaptéry · Zenodo
Core architecture and domain adapters · Zenodo
Doplnková publikácia o aplikácii na TSP · PDF
Supplementary publication on the TSP application · PDF
Konštrukcia rodiny a dôkaz referenčného optima · PDF
Family construction and proof of the reference optimum · PDF
Výsledky, metodika a reprodukovateľné podklady · september 2026
Results, methodology and reproducible evidence · September 2026
Ukážka Refined Sudoku Lab bola stiahnutá a už nie je k dispozícii.
The Refined Sudoku Lab demo has been withdrawn and is no longer available.
Video: ukážky hľadania a použitia jadra. Aktuálne porovnania solverov sú v dátach uvedených vyššie.
Video: demonstrations of the search core and its applications. Current solver comparisons are in the data linked above.
Otvoriť na YouTube ↗ Watch on YouTube ↗