How iolivag/symmetry-reduction-combinatorial-optimization works
Main Components
• Jupyter Notebook UI (Browser)
• IJulia / Julia Kernel
• JuMP Modeling API (Julia package)
• HiGHS Solver (via HiGHS.jl)
• Symmetry Analysis Engine (custom code in notebooks for graph automorphisms and orbit detection)
• Problem Modules / Notebooks
• shortest_path.ipynb
• graph_coloring.ipynb (planned)
• max_cut.ipynb (planned)
• traveling_salesman.ipynb (planned)
• Results & Visualization (plots, tables inside notebooks)
• References Repository (bibliography.bib)
• External Dependencies (Julia runtime, Jupyter server)
Relationships & Data Flow
• User types code in Jupyter UI → dispatch to Julia Kernel.
• Kernel loads a specific Notebook Module →
a. Calls JuMP to build ILP/MIP model for that CO problem.
b. Invokes Symmetry Analysis Engine to detect automorphisms and orbits.
c. Applies symmetry‐breaking constraints to the JuMP model.
d. Passes the augmented model through HiGHS Solver (via HiGHS.jl).
e. Receives solutions back into JuMP → kernel → notebook.
• Notebook renders results via Results & Visualization components.
• References Repository is consulted for bibliographic citations (static resource).
Architectural Patterns
• Pipeline Pattern: Model → Symmetry‐Detect → Constraint‐Augment → Solve → Post‐Process.
• Modular Notebook Design: each CO problem is a plug‐and‐play pipeline instance.
• Extensibility: new notebooks/problems follow exactly the same chain of steps.
Relevant Technologies & Roles
• Jupyter / IJulia: Interactive front end & execution environment.
• Julia 1.9+: Programming language runtime.
• JuMP: Algebraic modeling DSL for mathematical programs.
• HiGHS: High‐performance LP/MIP solver.
• Graph Automorphism Routines: symmetry detection submodule in notebooks.
Essential Details to Capture
• The IJulia bridge between Jupyter and Julia.
• The separate symmetry‐reduction step distinct from pure modeling and solving.
• The parallel modular notebooks as instances of the same workflow.
• The flow of results back into notebooks for visualization and analysis.