## Line Graphs: Algorithm Performance Analysis ### Overview The image contains four line graphs (a-d) comparing the timing performance of seven algorithms (BaBSB, BaB, reluBaB, reluplex, MIPplanet, planet, BlackBox) across four parameters: number of inputs, layer width, satisfaction margin, and network depth. All graphs use a logarithmic scale for timing (y-axis) and linear/logarithmic scales for parameters (x-axis). A horizontal "Timeout" threshold line (10^4 s) is present in all graphs. ### Components/Axes 1. **Graph (a): Number of inputs** - X-axis: "Number of inputs" (10^1 to 10^3) - Y-axis: "Timing (in s.)" (10^-2 to 10^4) - Legend: Positioned top-right, colors match lines: - Blue: BaBSB - Orange: BaB - Green: reluBaB - Red: reluplex - Purple: MIPplanet - Brown: planet - Pink: BlackBox - Dashed red: Timeout threshold 2. **Graph (b): Layer width** - X-axis: "Layer width" (10^1 to 10^2) - Y-axis: "Timing (in s.)" (10^-2 to 10^4) - Legend: Same as (a), positioned top-right 3. **Graph (c): Satisfaction margin** - X-axis: "Satisfaction margin" (10^-4 to 10^4) - Y-axis: "Timing (in s.)" (10^-2 to 10^4) - Legend: Includes SAT/False (blue) and UNSAT/True (green) in addition to algorithm colors 4. **Graph (d): Network depth** - X-axis: "Layer depth" (2×10^0 to 6×10^0) - Y-axis: "Timing (in s.)" (10^-2 to 10^4) - Legend: Same as (a), positioned top-right ### Detailed Analysis #### Graph (a) Trends - **Timeout (red dashed)**: Flat line at 10^4 s (timeout threshold) - **BaBSB (blue)**: Sharp initial rise, plateaus at ~10^2 s - **BaB (orange)**: Steeper rise than BaBSB, plateaus at ~10^3 s - **reluBaB (green)**: Gradual rise, plateaus at ~10^2 s - **reluplex (red)**: Sharp rise, plateaus at ~10^3 s - **MIPplanet (purple)**: Moderate rise, plateaus at ~10^2 s - **planet (brown)**: Steep rise, plateaus at ~10^3 s - **BlackBox (pink)**: Gradual rise, plateaus at ~10^2 s #### Graph (b) Trends - **Timeout (red dashed)**: Flat line at 10^4 s - **BaBSB (blue)**: Gradual rise, plateaus at ~10^2 s - **BaB (orange)**: Steeper rise than BaBSB, plateaus at ~10^3 s - **reluBaB (green)**: Moderate rise, plateaus at ~10^2 s - **reluplex (red)**: Sharp rise, plateaus at ~10^3 s - **MIPplanet (purple)**: Gradual rise, plateaus at ~10^2 s - **planet (brown)**: Steep rise, plateaus at ~10^3 s - **BlackBox (pink)**: Moderate rise, plateaus at ~10^2 s #### Graph (c) Trends - **Timeout (red dashed)**: Flat line at 10^4 s - **SAT/False (blue)**: Flat line at ~10^-1 s - **UNSAT/True (green)**: Sharp rise at ~10^2 s, plateaus at 10^4 s - **BaBSB (blue)**: Gradual rise, plateaus at ~10^2 s - **BaB (orange)**: Steeper rise than BaBSB, plateaus at ~10^3 s - **reluBaB (green)**: Moderate rise, plateaus at ~10^2 s - **reluplex (red)**: Sharp rise, plateaus at ~10^3 s - **MIPplanet (purple)**: Gradual rise, plateaus at ~10^2 s - **planet (brown)**: Steep rise, plateaus at ~10^3 s - **BlackBox (pink)**: Moderate rise, plateaus at ~10^2 s #### Graph (d) Trends - **Timeout (red dashed)**: Flat line at 10^4 s - **BaBSB (blue)**: Gradual rise, plateaus at ~10^2 s - **BaB (orange)**: Steeper rise than BaBSB, plateaus at ~10^3 s - **reluBaB (green)**: Moderate rise, plateaus at ~10^2 s - **reluplex (red)**: Sharp rise, plateaus at ~10^3 s - **MIPplanet (purple)**: Gradual rise, plateaus at ~10^2 s - **planet (brown)**: Steep rise, plateaus at ~10^3 s - **BlackBox (pink)**: Moderate rise, plateaus at ~10^2 s ### Key Observations 1. **Timeout Consistency**: All algorithms hit the 10^4 s timeout threshold at maximum parameter values. 2. **Algorithm Sensitivity**: - **BaBSB/BlackBox**: Most stable across parameters, plateauing at ~10^2 s - **BaB/planet**: High sensitivity to layer width and network depth - **reluplex**: Most sensitive to satisfaction margin (sharp rise in graph c) 3. **Anomalies**: - **reluplex** shows a sharp drop in graph (d) at 4×10^0 layer depth - **UNSAT/True** (green) in graph (c) exhibits a discontinuous jump at 10^2 margin ### Interpretation The data suggests algorithm performance varies significantly with input complexity: - **BaBSB and BlackBox** demonstrate robustness across all parameters, maintaining sub-second timing for most configurations - **BaB and planet** show exponential scaling with layer width and network depth, becoming impractical beyond moderate sizes - **reluplex**'s sensitivity to satisfaction margin indicates potential optimization opportunities for constraint-based problems - The **UNSAT/True** discontinuity suggests a fundamental shift in computational complexity when unsatisfiability is confirmed These trends highlight tradeoffs between algorithmic approaches: some prioritize speed at the cost of precision (BaBSB/BlackBox), while others offer deeper analysis at the expense of computational resources (BaB/planet/reluplex).