PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Learning-Guided Discovery of Extremal Geometric Constructions: A PatternBoost Study

Deepak Ajwani, Paula Carroll, Rishikesh Gajjala, Ananta Manoranjan, Ryan O'Connor, Rajiv Raman, Saurabh Ray, Aimen Taha

arXiv:2610.19980v1cs.CGmath.CO

TL;DR

Extremal constructions reveal algorithmic obstacles, but are usually found through slow, manual, problem-specific work. This paper adapts PatternBoost to geometric construction discovery and combines automated search with expert input to reach a 14/9 unit-square stabbing gap.

  • Problem

    Extremal constructions expose limits of relaxations and algorithmic approaches, yet computational-geometry examples are usually found through a slow, manual, problem-specific process.

    Source: §1 · p. 1

  • Method

    The paper adapts PatternBoost/Axplorer with geometry-specific representations, local-search operations, and surrogate models, combining transformer-generated candidates with local search.

    Source: §1 · p. 2, §4 · pp. 5–6

  • Results

    14/9 ≈1.555 is the unit-square stabbing gap reached with an expert-structured staircase; automated search reaches 20/13 ≈1.54, and the adapted system finds non-trivial constructions for all three problems.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The reported division of labor is that automated search covers ground tedious by hand, while an expert supplies the template the system cannot invent.

    Source: §6 · p. 12

    Purely automated search plateaus because, within its fixed setup, it cannot leave the region where it starts.

    Source: §5.3 · p. 10, §6 · p. 12

Abstract

from arXiv · show

Extremal constructions play a central role in the design and analysis of algorithms. Integrality-gap instances expose the limitations of relaxations, while hard configurations reveal structural sources of computational difficulty. Such constructions, however, are still typically discovered through a slow, manual process. This paper investigates how machine learning can accelerate their discovery to support algorithm design and analysis. We build on PatternBoost, a framework alternating local search with generation from a trained transformer, using its Axplorer implementation to investigate three problems: integrality gaps for maximum independent set of rectangles, integrality gaps for stabbing unit squares with axis-parallel lines, and hard instances for recursive guillotine cutting. By exploring candidate representations, local search operations, and surrogate models used to rank candidates before exact verification, we carefully adapt the framework to these combinatorial geometry problems.While naive representations and search strategies fail to find non-trivial instances, our tailored adaptation discovers numerous non-trivial constructions. For stabbing unit squares, the method reaches a gap of $20/13\approx 1.54$, improving on the literature's best known lower bound of $3/2$. Purely automated search converges rapidly and then plateaus, prompting the question of what is required to push the bound higher still. We find that initial instance diversity plays an important role: with modest expert input via a structured staircase construction, the system reaches an improved integrality gap of $14/9\approx 1.555$. These results demonstrate that machine learning and domain expertise can be combined to discover new extremal constructions that advance algorithmic lower bounds.

1 Introduction

The paper adapts PatternBoost/Axplorer to discover extremal constructions in computational geometry, where such constructions are important but usually found through slow, manual, problem-specific work. Tailored search finds a 20/13 unit-square stabbing gap automatically and reaches 14/9 with an expert-structured staircase construction.

1 Introduction

  • Extremal constructions expose relaxation limits or algorithmic obstacles and can prompt new theory, yet computational-geometry examples are usually found through slow, manual, problem-specific work.The paper asks whether machine learning can accelerate their discovery.Source: §1 · p. 1
  • The adaptation redesigns candidate representations, local-search operations, and surrogate ranking, then independently verifies reported constructions.The problems are maximum independent set of rectangles, unit-square stabbing by axis-parallel lines, and recursive guillotine cutting.Source: §1 · pp. 1–2
  • 20/13 ≈1.54 is the fully automated unit-square stabbing gap; the MISR and guillotine constructions do not improve their best known bounds.The reported constructions are 3/2 for MISR and 1/3 for guillotine cutting, matching the best known bounds.Source: §1 · p. 2
  • For each problem, only one of 27 tested configurations reaches its best value, showing that representation, search, and surrogate choices must be co-designed.The study varies those components across all three target problems.Source: §1 · p. 2
  • 14/9 ≈1.555 is the certified unit-square stabbing gap reached with an expert-structured staircase construction, exceeding the prior best known lower bound of 3/2.The staircase formulation lifts a one-dimensional family of intervals to unit squares by products.Source: §1 · p. 2

2 Related work

Prior work explores learning-guided mathematical construction, learned optimization, instance hardness, and human-guided discovery. This paper distinguishes its focus on generating geometric instances that are scored by exact optimization and independently verifiable certificates.

2.1 Model-guided construction discovery

  • Learning-guided construction work includes AlphaTensor, FunSearch, AlphaEvolve [27], and PatternBoost [11]; this paper builds on PatternBoost/Axplorer for geometric candidates scored by exact optimization.The authors distinguish their approach from exhaustive search by generating geometric objects and independently verifying certificates.Source: §2.1 · p. 3

2.2 Machine learning for combinatorial optimization

  • Unlike literature that learns to solve instances, this work generates candidate instances and scores each with an exact solver, so reported gaps are exact values rather than model estimates.The objective is itself the output of an LP and an ILP, rather than a directly predicted quantity.Source: §2.2 · p. 3

2.3 Instance hardness and adversarial instance generation

  • Instance-hardness research studies test instances, difficulty measures, and evolving hard instances; here, each reported instance has an exact, independently re-verifiable certificate.The related work cites,,, and for those strands.Source: §2.3 · p. 3

2.4 Human-guided discovery and diversitydriven search

  • Human-guided discovery informs the staircase strategy, while novelty search and MAP-Elites [26] motivate diversity controls and a proposed quality-diversity archive.The expert reframes the problem so the obstruction is native, and the learned search tunes it beyond a known lower bound.Source: §2.4 · p. 3

3 Problems and exact objectives

This section defines three combinatorial-geometry objectives: an integrality gap for maximum independent set of rectangles, an integrality gap for unit-square stabbing, and the fraction of rectangles destroyed by recursive guillotine cutting. It also situates these objectives among known bounds and explains how critical-line compression makes the stabbing problem finite.

3.1 MISR integrality gap

  • MISR compares the clique-LP optimum for rectangles with the integer maximum number of pairwise-disjoint rectangles.The search targets instances where the LP substantially exceeds the integer optimum.Source: §3.1 · pp. 3–4

3.2 Unit-square stabbing integrality gap

  • Unit-square stabbing compares the minimum number of axis-parallel stabbing lines with the fractional set-cover optimum over critical lines.Critical-line compression preserves both optima while reducing infinitely many candidate lines to a finite universe.Source: §3.2 · p. 4

3.1 MISR integrality gap

  • For MISR, the known integrality-gap lower bound approaches 2, while the upper bound is O(log log n); finite small instances can realize a different, smaller maximum.The value 2 is a supremum over growing families, not a gap realized by a single finite instance.Source: §3.2 · p. 4

3.2 Unit-square stabbing integrality gap

  • For unit-square stabbing, the cited bounds are at least 3/2 and at most 1.93; the lower bound comes from a four-square construction with LP optimum 2 and integer optimum 3.Source: §3.2 · p. 4

3.3 Recursive guillotine hardness

  • Guillotine cutting seeks a recursive sequence of full horizontal or vertical cuts that preserves as many pairwise interior-disjoint rectangles as possible.Its score is the fraction destroyed, and an optimal strategy uses at most |R|−1 cuts.Source: §3.3 · p. 5
  • For squares, the best explicit guillotine-separability guarantee cited is 9/256, while an arrangement limits every sequence to separating at most half; these bounds translate into dynamic-programming approximations.Whether general disjoint rectangles always admit a constant separable fraction remains open.Source: §3.3 · p. 5

4 PatternBoost/Axplorer framework

PatternBoost/Axplorer alternates local search with transformer-generated candidates trained on high-scoring constructions. The paper argues that geometric problems require co-design of representations, search operations, and surrogate ranking, while independent exact verification determines reported scores.

4 PatternBoost/Axplorer framework

  • PatternBoost alternates targeted local search over existing constructions with transformer generation trained on high-scoring candidates in a growing database.Generated candidates return to local search for correction, and improved constructions are retained.Source: §4 · p. 5
  • Candidates are canonicalized before scoring, and every reported value is recomputed by an exact oracle and saved as a standalone certificate.A post-processing audit independently re-verified every certificate and checked recorded-score agreement.Source: §4 · p. 6
  • Local moves range from coordinate perturbations to structure-aware changes and exactly scored hill climbs, while surrogates rank candidates and select elites for exact audits.A surrogate is distinguished from the oracle by its search role, not necessarily by approximating the objective.Source: §4 · p. 6
  • Geometric representations contain many equivalent coordinate encodings, exact optimization objectives are costly and change in coarse jumps, and random or generated coordinates often violate validity constraints.These challenges motivate problem-specific representations, local-search operations, and surrogate models.Source: §4 · p. 6

5 Exploring the design space of components for geometric construction discovery

The study systematically explores representations, local-search operations, and surrogate ranking choices for three geometric construction problems. Its strongest automated result is a unit-square stabbing gap of 20/13, while results and search dynamics show that high-scoring constructions are rare and automated search plateaus.

5.1 Components

  • Each problem crosses three choices for representation, local search, and surrogate, yielding 27 combinations per problem and 81 overall.The components encode and repair candidates, modify them, and rank them for exact verification; choices range from direct coordinate encodings to structured encodings and exact-scoring surrogates.Source: §5.1 · pp. 6–7, §5.2 · p. 7

5.2 Experimental setup

  • Each configuration runs once from fresh geometry under a 24-hour budget, so marginal means across configurations are descriptive rather than estimates with error bars.The experiments track exact score, time-to-best, epoch-to-best, and post-best plateau fraction.Source: §5.2 · pp. 7, 9

5.3 Results

  • Only one of 27 configurations reaches the best value for each problem, and the median configuration scores well below the maximum.Weak configurations pairing generic coordinate representations with cheap heuristic surrogates remain at trivial or half-integral constructions.Source: §5.3 · p. 9
  • The best configuration is problem-specific, and the component carrying the useful structural signal differs across the three problems.The reported choices preserve sparse conflicts for MISR, measure the true gap for stabbing, and target the recursive escape route for guillotine cutting; a mismatch in any component can cap the score.Source: §5.3 · pp. 9–10
  • 97.5%, 64.1%, and 87.2% of median-run generations occur after the best construction appears for MISR, unit-square stabbing, and guillotine cutting, respectively.The best configurations reach their records after 3.12, 0.37, and 5.81 of the 24 available hours, respectively; the paper attributes the plateau to reachability rather than insufficient computation.Source: §5.3 · p. 10
  • 20/13 ≈1.54 is the unit-square stabbing gap; the search also finds an MISR gap of 3/2 and a guillotine destroyed fraction of 1/3.The stabbing witness has twenty squares, LP optimum τ ∗= 13/5, and integer optimum τ = 4; the MISR witness uses twelve rectangles, and the guillotine witness uses nine.Source: §5.3 · p. 9, Figure 3 · p. 10

6 Human-in-the-loop: an expert-structured staircase construction

The staircase formulation reaches a certified unit-square stabbing gap of 14/9, exceeding both the previous lower bound and the automated search result. Its structured search space encodes hard square–line incidences and a proof template that coordinate-based search did not discover.

Structuring the search space

  • Staircase search samples squares as products of intervals from a one-dimensional family, forcing shared-line incidences instead of independently placing squares.Its local moves scan interval starts, common length, level count and assignments, support points, and shifted staircase variants.Source: §6 · p. 11

Lower-bound certificate

  • For any split into fewer than T vertical and horizontal lines, the staircase levels leave an admissible square unstabbed, certifying τ(S) ≥ T.The fractional optimum is computed by an LP over the compressed critical-line universe.Source: §6 · p. 11

Results

  • 14/9 ≈ 1.555 is the certified staircase gap, exceeding the prior lower bound of 3/2 and the automated search’s 20/13.The levels, rational measure, and product rule provide the proof template while the search optimizes within it.Source: §6 · p. 12
  • Uniformly random seeding does not help, while the structured staircase search reaches 14/9 by optimizing within its proof template.The passage attributes the gain to the levels, rational measure, and product rule, not an injected answer.Source: §6 · p. 12

Plateau diagnosis

  • The automated loop plateaus because it is confined to the region where it starts, rather than because of limited model capacity.The neutral search samples square coordinates directly, while coupled hard incidences are isolated in the design space.Source: §6 · pp. 10, 12

Future directions

  • Proposed directions include structurally organized archives, composition operators for certified obstructions, and search moves guided by solver-computed structure.The stated applicability is to extremal questions with exactly computable, certifiable objectives.Source: §6 · p. 12

8 Reproducibility and artifacts

The paper archives its code, certificates, and analysis scripts with independent exact-score verification and reproduction support. It also reports human post-processing and generalization of search results.

Reproducibility and artifacts

  • The archived artifact includes code, certificates, analysis scripts, a reduced smoke test, and a full reproduction script for the main tables.An independent verifier recomputes each certificate’s exact score, and every certificate carries a canonical hash.Source: §8 · p. 12
  • Manual post-processing reduces the automated 20/13 witness from twenty squares to eleven without changing its score, while the 3/2 MISR construction extends by hand into an infinite family.The paper describes the search as supplying seeds that humans can compress or generalize.Source: §8 · p. 12

7 Conclusion and future directions

The appendix illustrates the paper’s three problems with small instances and handcheckable hard examples. Those examples were discovered by domain experts, while the paper aims to develop methods for automatic discovery of hard instances with larger gaps.

A Problem illustrations and hard examples

  • Figure 1 shows small instances with optimal solutions, and Figures 5–7 show handcheckable hard instances whose relaxations are far from integral.The hard examples were discovered by domain experts and are not a contribution of the paper.Source: A Problem illustrations and hard… · p. 15
  • The paper’s stated goal is to develop methods that automatically discover hard instances with larger gaps.The appendix examples serve as illustrations of the three studied problems.Source: A Problem illustrations and hard… · p. 15
  • The illustrated problems are presented through small instances and handcheckable hard examples, rather than as new constructions from this paper.Figure 1 pairs each problem with an optimal solution.Source: A Problem illustrations and hard… · p. 15

B Complete per-configuration results

The appendix provides complete configuration results, component-slice convergence plots, and expanded descriptions of component behavior. Reported scores are determined by the exact verifier.

B Complete per-configuration results

  • Tables 4–6 report each configuration’s best exact score, gain over its initial construction, best-score timing, plateau fraction, and object count.The top-scoring configuration in each table is bolded, and Table 2 summarizes them.Source: B Complete per-configuration results · p. 15

C Component-slice figures

  • Figures 8 and 9 plot best exact score against cumulative transformer-training epochs while varying one component and fixing the other two at their best choices.They complement the unit-square stabbing component-slice plot in Figure 4.Source: C Component-slice figures · p. 15

D Detailed component descriptions

  • The component descriptions explain what each choice stores, how it initializes and repairs candidates, and how it moves or ranks them.Only the exact verifier determines a reported score.Source: D Detailed component descriptions · p. 15

D.1 MISR components

The MISR search compares rectangle representations, local-search operators, and ranking surrogates. Their design choices trade off structural constraints, move scope, and the cost and fidelity of candidate ranking.

Representations

  • The triangle_free_rect representation stores integer rectangles while enforcing a triangle-free intersection graph, but cannot reach constructions whose graph contains a triangle.Repair deletes a rectangle from any triangle and refills to the minimum size.Source: §D.1 · p. 15
  • The quadratic-program representation changes many rectangles through coefficient moves, while fixed_symmetry_rectangles searches direct rectangles at fixed cardinality and canonicalizes symmetric copies.The program representation favors algebraic regularity but its repair step can collapse different programs to the same geometry.Source: §D.1 · p. 15

Local-search operations

  • Local search ranges from representation-specific rectangle changes to coefficient pivots and a 25-proposal hill climb that exactly scores and accepts only nonworsening candidates.The coefficient pivot is a genuinely distinct global move only for the quadratic-program representation; global symmetries are neutral with fixed_symmetry_rectangles.Source: §D.1 · pp. 15–17

Surrogates

  • The exact MISR gap surrogate ranks by the clique-LP-to-integer gap but is costly, whereas graph_conflict_proxy uses cheaper graph statistics that need not predict the true gap.The triangle-free exact-gap surrogate instead filters out graphs with triangles before ranking survivors by exact gap.Source: §D.1 · p. 17

D.2 Unit-square stabbing components

The unit-square stabbing search varies anchor representations, stabbing-aware moves, and surrogates with different scoring costs and fidelity. Its methods balance structured starting patterns against the flexibility of searching coordinates and scale.

Representations

  • The line_square_incidence representation starts from balanced row-and-column patterns that can favor hard covers but may overproduce easy-to-stab grids.Its incidence labels guide initialization and structured moves, while the solver-facing state remains the square anchors.Source: §D.2 · p. 17

Local-search operations

  • Stabbing-aware proposals copy or tighten square coordinates, add or replace anchors, drop squares, shift to the origin, or restart with fresh grid points.For families up to about 48 squares, the method keeps the candidate with the best exact stabbing key; larger families use a cheaper greedy-cover-versus-frequency proxy.Source: §D.2 · p. 18

Representations

  • The exact_grid searches distinct integer anchors and a common side length, while fixed_symmetry_grid fixes object count and side length, limiting movement between scale regimes.The exact grid has a large, rugged search space with many plateaus.Source: §D.2 · p. 18

Surrogates

  • The exact stabbing-gap surrogate scores each candidate with the exact set-cover and fractional-LP scorer, while greedy_partial_lp_bitset and incidence_statistics use cheaper estimates that can misrank candidates.The exact surrogate favors larger integer covers and more spread-out LP support among equal-gap candidates.Source: §D.2 · pp. 18–19

D.3 Guillotine components

The guillotine search compares neutral and structured packing representations, neighborhoods, and surrogates. The methods expose a key constraint: nonworsening local search from easy packings can stall at the trivial hardness value.

Representations

  • The recursive_obstruction_grammar representation begins with seven-rectangle spiral obstruction cores plus disjoint fillers, whereas fixed_symmetry_packing uses a bar-heavy shape distribution without fixed non-sliceable topology.The grammar is an obstruction-family search with a hand-designed topology prior; fixed_symmetry_packing fixes object count and canonicalizes symmetries.Source: §D.3 · p. 19

Local-search operations

  • The witness_breaking neighborhood targets a concrete separable subset by extending rectangles across projection gaps or inserting thin bridges, while packing_resize adds guided trials after its primary move.Both approaches use guided nonseparability trials, but witness_breaking acts adversarially on an identified weakness.Source: §D.3 · pp. 19–20
  • The shared exact-nonworsening hill climb stalls at the trivial 1/6 value for guillotine configurations because it cannot move from an easily separable packing to a harder one.Its acceptance gate first requires at least two destroyed rectangles, then accepts only nonworsening exact objectives.Source: §D.3 · p. 20

Surrogates

  • The depth-four dynamic-program surrogate sees beyond the first cut but misses deeper obstructions, while k_subset_nonseparability combines several signals that may diverge from exact destruction.The first-cut obstruction score can be high even when the resulting subproblems are easy.Source: §D.3 · pp. 20–21

E Prioritized limitations

The limitations are prioritized by estimated leverage, while the accompanying pseudocode sketches population search and the certificate section describes independently checked outputs.

E Prioritized limitations

  • Table 7 ranks limitations by how much removing each barrier could change reachable constructions, not by how easy it would be to remove.The supplied material does not enumerate the table’s individual barriers.Source: E Prioritized limitations · p. 21, Table 7 · p. 22

F PatternBoost pseudocode

  • Each generation scores candidates with a surrogate, audits elites exactly at intervals, retrains on the archive periodically, and refills the population with local mutations and random newcomers.Improved exact scores update the best construction and save its certificate.Source: F PatternBoost pseudocode · p. 21

G Certificate schemas and verification

  • Each reported construction has a standalone certificate whose exact score an independent verifier recomputes, with a canonical hash recorded.The certificate schemas record problem-specific construction and score fields, including MISR’s LP and integer optima and unit-square stabbing’s cover optima.Source: G Certificate schemas and verification · pp. 21–22
Loading 2610.19980v1…