Optimization Techniques for Solving the Minimum Red--Blue Separating Set Problem with an Application to Human--AI Text Separation
Authors: Marko Djukanović, Staša Vujičić Stanković, Žiga Zebec, Christian Blum
Organizations: University of Nova Gorica, Nova Gorica, Slovenia · Institute of Information Sciences (IZUM), Maribor, Slovenia · Faculty of Mathematics, University of Belgrade, Belgrade, Serbia · Artificial Intelligence Research Institute (IIIA-CSIC), Barcelona, Spain
We study the so-called Minimum Red''Blue Separating Set Problem (MRBSSP) which arises from computational geometry. In particular, we propose a compact Set-Cover ILP formulation, safe preprocessing rules, a Greedy Randomized Adaptive Search Procedure (GRASP), and two exact approaches: one is based on Logic-Based Benders Decomposition (LBBD) approach, and the second represents a novel Branch-and-Benders-Cut (BBC) approach. These two exact approaches are compared to ILP--alongside GRASP and the Variable Neighborhood Search (VNS) from literature. Experiments on 250 random graphs with up to 500 vertices reveal complementary strengths: ILP yields the best feasible solutions, LBBD provides the strongest lower bounds and smallest mean optimality gap, and BBC certifies optimality most frequently. We further introduce an NLP application distinguishing human- and AI-generated texts through vocabulary-based graph features. On 42 instances, BBC achieves the smallest mean optimality gap, certifying 16 optima, while GRASP outperforms VNS. Structural analysis of optimal vocabulary separators identifies 113 mandatory and 151 replaceable features across 272 tests, highlighting substantial variability among optimal solutions. Overall, our results demonstrate the effectiveness of complementary optimization strategies and the interpretability of optimal vocabulary-based discrimination.
Figures & tables
Figure 1
Method
Mean UB
Mean LB
Mean gap
Optimal
Ilp
18.83
12.40
29.54%
90/200
Bbc
19.09
13.11
25.97%
92/200
Lbbd
20.25
13.63
24.37 %
91/200
Table 1: Overall results of the exact methods on the 200 (feasible) Random instances after tuning.
Figure 3: Mean optimality gaps of Ilp , tuned Bbc , and tuned Lbbd on the feasible Random groups.
Instance ( n/p )
Ilp
Bbc
Lbbd
20/0.01
9.00
9.00
9.00
20/0.2
5.00
5.00
5.00
20/0.5
3.00
3.00
3.00
50/0.05
16.00
16.00
16.00
50/0.1
10.00
10.00
10.00
50/0.2
8.00
8.00
8.00
Table 2: Mean lower bounds after tuning. Bold indicates the strongest mean lower bound in each group.
Instance ( n/p )
Ilp
Bbc
Lbbd
Grasp
Vns
20/0.01
9.00
9.00
9.00
9.00
9.00
20/0.2
5.00
5.00
5.00
5.00
5.00
20/0.5
3.00
3.00
3.00
3.00
3.00
50/0.05
16.00
16.00
16.00
16.00
16.00
50/0.1
10.00
10.00
10.00
10.00
10.00
50/0.2
8.00
8.00
8.00
8.00
8.00
Table 3: Mean upper bounds after tuning. Bold indicates the smallest value in each group.
Group
qns
N
∣R∣
∣B∣
∣T∣
∣E∣
∣R∣∣B∣
standard, k=1
100
10
99–100
108–126
1 622–1 829
13 239–14 686
10 800–12 600
150
10
149–150
159–188
2 325–2 500
21 313–23 043
23 850–28 200
200
10
199–200
213–244
2 880–3 163
29 307–31 342
42 600–48 800
250
2
250
279–291
3 526–3 621
37 265–38 761
69 750–72 750
variant, k=2
100
3
93–95
108–116
477–568
4 397–5 042
10 260–10 788
250
2
231–236
279–291
1 080–1 141
11 743–12 527
65 844–67 221
Table 4: Size of the 42 NLP instances after preprocessing, given as the range over the instances of each group. ∣T∣ : number of candidate words; ∣E∣ : number of document–word edges; ∣R∣∣B∣ : number of red–blue pairs.
Figure 4: NLP tuning: summary results for Bbc and Lbbd over all 42 instances.
Method
Mean UB
Mean LB
Mean gap (%)
Optimal
Ilp
13.62
10.55
23.75
11/42
Bbc
13.90
12.12
13.21
16/42
Lbbd
14.26
12.29
14.38
11/42
Grasp
13.73
–
–
–
Vns
14.30
–
–
–
Table 5: Overall NLP results on all 42 benchmark instances. Exact methods report mean UB, mean LB, mean relative gap, and the number of proven optima. Grasp and Vns report the per-instance ten-run mean solution size.
ILP
BBC
LBBD
Heuristics
qns
N
UB
LB
Gap (%)
UB
LB
Gap (%)
UB
LB
Gap (%)
GRASP
VNS
100
16
11.81
10.39
13.12
12.00
11.44
4.92
12.31
11.38
7.95
11.88
12.41
150
10
12.80
8.60
32.89
13.30
10.60
20.38
13.80
10.80
21.83
12.75
13.49
200
10
13.90
8.69
37.62
14.30
11.10
22.40
14.70
11.60
21.15
14.10
14.56
250
6
19.33
17.33
13.74
19.33
18.17
8.02
19.50
18.33
7.78
19.68
20.28
Table 6: Grouped results on all 42 NLP benchmark instances. The N column shows the number of instances contributing to each NLP- qns group. Exact methods report mean UB, mean LB, and mean gap; heuristics report ten-run means.
∣D∣
UzL
Bbc
Group
N
∣T∣
min
mean
Single
proved
time (s)
proved
time (s)
standard, k=1
32
1 622–3 621
3–26
94–121
0
0
–
6
333–2 680
variant, k=2
5
477–1 141
1–5
30–36
3
4
73–1 378
5
4–20
variant, k=3
5
222–541
1–2
16–19
3
5
5–30
5
0–1
Table 7: UzL and Bbc on the three groups of NLP instances. ∣T∣ : number of candidate words; ∣D∣ : smallest and mean size of the sets D(r,b) ; both are given as ranges over the instances of the group. Single: instances with a pair separated by one word. UzL: instances whose optimum UzL is able to prove and the time of the shorter of the two runs, which covers the whole job. Bbc : instances certified under the one-hour limit and their solver time.
Instance (qns,seed,k)
z⋆
Core
Repl.
Inc.
ρcert
(100,42,2)
12
2
10
0
0.17
(100,42,3)
15
13
2
0
0.87
(100,43,1)
10
1
9
0
0.10
(100,43,2)
14
2
12
0
0.14
(100,43,3)
15
7
8
0
0.47
(100,44,1)
11
0
11
0
0.00
Table 8: Structural classification of the 272 words belonging to the 19 certified Bbc optima. “Core” denotes words proved mandatory in every optimum; “Repl.” denotes replaceable words; “Inc.” denotes restrictive–inconclusive words.
Figure 5: Coverage P(t) of every candidate word, ordered by rank, on four NLP instances: (a) the instance (100,50,1) , whose optimum is unique; (b) the instance (100,47,1) , whose optimum has an empty core; (c) the instance (100,49,1) , with five core words and six unresolved words; (d) the instance (250,42,3) , with 15 of 25 words in the core. Stop words and content words are drawn in different colors; the words of the certified optimum are marked as core (filled), replaceable (hollow) or restrictive–inconclusive (grey square). The dashed horizontal line distinguishes between the words that separate more than half of the human/ChatGPT pairs (above the line) and those that separate fewer.
candidate words
share
ratio min / median / max
infeasible
all words
1.00
1.00 / 1.00 / 1.00
0
stop words only
0.06
0.93 / 1.00 / 1.23
4
at least 4 letters
0.92
1.08 / 1.25 / 1.69
0
at least 5 letters
0.78
1.33 / 1.64 / 2.75
0
at least 6 letters
0.62
1.75 / 2.29 / 3.50
7
all words except stop words
0.94
1.42 / 1.84 / 3.19
0
Table 9: Size of the greedy separator when the candidate set is restricted, relative to the greedy separator on the full vocabulary, over the 32 standard instances. share : mean share of the vocabulary that remains a candidate; infeasible : instances for which no feasible separator exists within the restricted candidate set. The ratios are taken over the remaining instances.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
qBBC
Mean UB
Mean LB
Mean gap (%)
Opt.
1
19.15
13.00
26.17
9
2
19.10
13.05
26.26
9
5
19.20
13.15
25.39
10
10
19.05
13.05
26.41
9
50
19.00
13.00
26.35
9
100
19.20
13.00
27.10
9
Appendix
Table 10: Bbc approach tuned on 20 selected Random instances.
qLBBD
Mean UB
Mean LB
Mean gap (%)
Opt.
1
20.40
13.15
27.37
8
2
20.45
13.30
26.50
8
5
20.10
13.45
25.61
8
10
20.45
13.50
26.30
8
50
20.35
13.65
25.51
8
100
20.35
13.55
24.85
9
Appendix
Table 11: Lbbd approach tuned on 20 selected Random instances.
qBBC
Mean UB
Mean LB
Mean gap (%)
Opt.
Rounds
1
13.95
12.07
13.78
15
1640.0
2
13.90
12.12
13.21
16
841.5
5
13.86
11.98
13.99
15
346.6
10
13.86
12.05
13.29
16
178.0
50
14.00
11.93
15.37
12
75.6
100
13.98
11.81
16.25
11
62.2
Appendix
Table 12: Bbc tuned on all 42 NLP benchmark instances. “Rounds” denotes the mean number of callback invocations. The selected setting is shown in bold.
qLBBD
Mean UB
Mean LB
Mean gap (%)
Opt.
Rounds
1
14.17
11.45
20.12
10
521.2
2
14.29
11.74
18.61
10
304.4
5
14.29
11.95
17.21
10
145.4
10
14.17
12.07
15.53
10
83.0
50
14.21
12.29
14.20
10
25.4
100
14.26
12.29
14.38
11
18.4
Appendix
Table 13: Lbbd tuned on all 42 NLP benchmark instances. “Rounds” denotes the mean number of master iterations. The selected setting is shown in bold.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
Rounded capacity cuts (RCCs) are among the most effective cuts for capacitated vehicle-routing relaxations, but exact separation is computationally prohibitive at scale. Existing heuristic and neural separators can be fast, but often fail to produce sufficiently many effective cuts within practical separation budgets. We introduce SAG-Sep, a separator that scores node membership in RCC-inducing subsets across vehicle-count levels from a fractional LP solution in a single encoder forward pass, avoiding the iterative predict-and-coarsen inference used by NeuralSEP-style separators. SAG-Sep encodes the LP solution as a Sparse Augmented Graph (SAG), adding flow-informed multi-hop edges that expose long-range routing structure without densifying attention. Beyond LP-aware sparse encoding, we observe that high-value exact RCCs are typically nested, organizing into onion-like subset families, and SAG-Sep's node scores track subset nesting depth. This motivates Onion-Sweep (OS), a training-free decoder that ranks customers by their scores, evaluates the RCC violation of every prefix of the ranking in one vectorized pass, and emits the most violated prefix of each replica together with a cross-replica family of nested proposals, converting independent node scores into structurally coordinated RCC candidates without a tuned threshold or probing band. On the NeuralSEP benchmark with N=1000 customer instances, SAG-Sep with OS reduces the average root gap by 17.7% relative to the strongest NeuralSEP baseline, while the single-pass SAG-Sep separator achieves a roughly 30-fold per-iteration neural separation speedup. Our findings suggest that LP-aware sparse encoding and the nested structure of high-value cuts are structural patterns worth leveraging in neural separation more broadly.
Haoran Liu, Guanyi Wang, Yu Yang
Department of Industrial Systems Engineering, University of Florida, Florida, United States · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore
We study the problem of constructing a decision tree that identifies an unknown hypothesis from a given ground set, under both average- and worst-case cost. The Optimal Decision Tree (ODT) problem has been extensively studied in the literature, and O(logn)-approximation guarantees are known for each criterion, including a simultaneous guarantee for both (here n is the number of hypotheses) [ICML]. Although most of the existing algorithm use simple greedy strategies, their analyses rely on intricate arguments. Since ODT is a fundamental problem with wide-ranging applications, we are interested in developing algorithms that are both effective and easy to understand. We present a new greedy algorithm with a simplified analysis that simultaneously achieves approximation factors below 3.65log2n for worst-case cost and 7.3log2n for average-case cost. Our algorithm for the Optimal Decision Tree behaves greedily with respect to the hereby introduced Separating Subfamily problem which asks for the cheapest subfamily of tests which partitions the hypotheses into pieces of small enough size. We show that the Separating Subfamily can itself be reduced to an instance of the well-known Maximum Coverage problem. At the core of our approach lies exploiting properties of cutting a clique into small pieces, where edges represent pairs of hypotheses to be separated. In the spirit of simplicity, we also provide a new and straightforward application of ODT: an O(log(k⋅n))-approximation for the Adaptive Set Cover problem, where k is the number of possible realizations.
Can a single LLM-based optimization system match specialized tools across fundamentally different domains? We show that when optimization problems are formulated as improving a text artifact evaluated by a scoring function, a single AI-based optimization system-supporting single-task search, multi-task search with cross-problem transfer, and generalization to unseen inputs-achieves state-of-the-art results across six diverse tasks. Our system discovers agent architectures that nearly triple Gemini Flash's ARC-AGI accuracy (32.5% to 89.5%), finds scheduling algorithms that cut cloud costs by 40%, generates CUDA kernels where 87% match or beat PyTorch, and outperforms AlphaEvolve's reported circle packing solution (n=26). Ablations across three domains reveal that actionable side information yields faster convergence and substantially higher final scores than score-only feedback, and that multi-task search outperforms independent optimization given equivalent per-problem budget through cross-task transfer, with benefits scaling with the number of related tasks. Together, we show for the first time that text optimization with LLM-based search is a general-purpose problem-solving paradigm, unifying tasks traditionally requiring domain-specific algorithms under a single framework. We open-source optimize_anything with support for multiple backends as part of the GEPA project at https://github.com/gepa-ai/gepa .