AN ILP SOLUTION FOR MINIMAL REPRESENTATIVE SUBSET SELECTION

ANILP SOLUTION FOR MINIMAL REPRESENTATIVE SUBSET SELECTION Haoran Chen Developmental Neurobiology Department St. Jude Children’s Research Hospital Memphis, TN 38105 [email protected] Ali Foroughi pour Developmental Neurobiology Department St. Jude Children’s Research Hospital Memphis, TN 38105 [email protected] Abbas Shirinifard Developmental Neurobiology Department St. Jude Children’s Research Hospital Memphis, TN 38105 [email protected] November 12, 2025 ABSTRACT We present an integer linear programming (ILP) formulation for minimal representative subset selection via neighborhood coverage on directed k -nearest-neighbor (k-NN) graphs. Given pairwise distances between samples, such as whole-slide images (WSIs) in a histopathology cohort, we seek the smallest subset such that every sample is either selected or lies among the topk nearest neighbors of at least one selected sample. This problem generalizes the minimum dominating set and set cover formulations. It is an NP-hard problem but solvable efficiently on practical datasets using modern ILP solvers. We outline the formulation, describe neighborhood construction, discuss related problems and the complexity, provide a minimal working example, and include concise implementation notes and code pointers. 1 Motivation & Overview A common challenge with large datasets is selecting a small yet representative subset for curation, visualization, labeling, and benchmarking. We therefore pose a minimal representative subset selection problem: given pairwise distances between samples, choose the fewest exemplars so that every sample is either selected or is sufficiently close to at least one selected sample [1, 2]. We define “close” using directed k -nearest-neighbor (k-NN) neighborhoods constructed from the distance matrix. This view yields a clean graph formulation and a compact optimization model. In particular, the problem specializes to a dominating-set problem on a directed k-NN graph and, equivalently, a set-cover instance over k-NN neighborhoods. As a result, the problem is NP-hard in general. Nevertheless, modern mixed-integer linear programming (MILP) solvers such as COIN-OR Branch and Cut (CBC) [ 3 ] can handle moderate-sized instances efficiently in practice, even though the problem is NP-hard [4]. While our case study uses whole slide images from pathology, the formulation applies to any collection embedded in a metric or learned feature space, such as image, text, or multimodal embeddings. The goal of this note is to present a concise and broadly applicable ILP-based solution. APREPRINT - NOVEMBER 12, 2025 2 Problem Definition & ILP Formulation Setup Let the samples be indexed by V={1, . . . , n} . Let d(i, j) denote a distance (smaller is closer) computed in a learned or metric space. For each i∈V, define the (directed) top-kneighborhood Nk(i)⊆V\ {i} as the set of the k closest indices to i under d(i, ·) . Note Nk(i) need not be symmetric: j∈Nk(i) does not imply i∈Nk(j). For each target j∈V, define its incoming coverage set C(j) = {i∈V:j∈Nk(i)}, i.e., the indices that would cover jif selected. Coverage requirement A subset S⊆V is feasible if every j∈V is either selected ( j∈S ) or covered by a selected in-neighbor (C(j)∩S=∅). Our objective is to find a feasible Sof minimal cardinality. ILP variables Introduce binary variables xi∈ {0,1}indicating selection: xi= 1 iff iis in the representative set. ILP objective Minimize the number of selected samples: min X i∈V xi. Coverage constraints For each j∈V , enforce that j is either selected or covered by at least one selected in-neighbor: xj+X i∈C(j) xi≥1,∀j∈V. (1) Compact ILP Putting it together: min X i∈V xi s.t. xj+X i∈C(j) xi≥1,∀j∈V, xi∈ {0,1},∀i∈V. 3 Related Problems & Complexity Minimum dominating set view Form a directed graph G on V with an arc i→j whenever j∈Nk(i) . A subset S⊆V is said to dominate G if every node j∈V is either selected itself ( j∈S ) or is pointed to by at least one selected node i∈S . The coverage constraints xj+Pi∈C(j)xi≥1 enforce exactly this condition, so our ILP is a minimum dominating set problem on the directed k -nearest-neighbor graph. Since the minimum dominating set problem is NP-complete even for undirected graphs [1, 4], our problem is NP-hard as well. Set cover view Define one set for each i∈V as Si={i} ∪ Nk(i) , representing the elements that would be covered if sample i is selected. The universe to be covered is V . Selecting representatives is therefore equivalent to choosing a subcollection of these sets {Si} whose union equals V , a classical minimum set cover problem [ 2 ]. In our formulation each representative has equal cost (the unweighted case), but a more general weighted set cover can be obtained by assigning nonnegative costs wiand minimizing Piwixi[5, 6]. Complexity and approximation The representative subset selection problem is NP-hard because it generalizes both minimum dominating set and minimum set cover. Modern solvers such as the CBC engine, however, combine linear programming relaxations, branch-and-bound search, and cutting planes to prune most of the search space in practice. For structured, sparse instances like ours, where each constraint involves at most k+1 variables, CBC typically converges quickly to an optimal or near-optimal solution, even though the theoretical worst-case complexity remains exponential. 2 APREPRINT - NOVEMBER 12, 2025 4 Implementation notes MILP implementation We implement the ILP using Python package PuLP with its CBC solver [ 3 , 7 ]. Each sample i is assigned a binary variable xi∈{0,1} , and the objective minimizes Pixi , the total number of selected samples. For every sample j, we enforce a coverage constraint xj+X i∈C(j) xi≥1, so that each sample is either selected or covered by at least one selected neighbor. The reverse coverage sets C(j) = {i:j∈Nk(i)} are built from the topk neighbor lists in O(nk) time. The resulting model has n binary variables and n constraints, each involving at most k+1 terms. The model is solved with CBC using default settings. A time limit can be specified for large datasets, and a feasible solution is always returned even if the optimality gap remains. WSI recipe For the whole-slide image (WSI) setting, we extract slide embeddings, compute pairwise distances, construct Nk(i) and the corresponding C(j) , then call the ILP solver to select representative slides. The output includes the selected slide IDs, total number of slides n , neighborhood size k , and optionally summary statistics such as runtime and solution size |S|. 5 Minimal working example Consider n= 6 with k= 2: N2(1) = {2,3}, N2(2) = {1,3}, N2(3) = {2,4}, N2(4) = {3,5}, N2(5) = {4,6}, N2(6) = {5,4}. Then C(3) = {1,2,4}. One optimal solution is S={2,5}, which covers all elements. 6 Code & Availability We provide a minimal implementation that constructs Nk(i) from a distance matrix, builds C(j) , and solves the ILP in Python with PuLP and CBC [3, 7]. Code is available at https://github.com/haoranch3n/ilp_solution. References [1] Teresa W Haynes, Stephen Hedetniemi, and Peter Slater. Fundamentals of domination in graphs. CRC press, 2013. [2] Vasek Chvatal. A greedy heuristic for the set-covering problem. Mathematics of operations research, 4(3):233–235, 1979. [3] John Forrest and Robin Lougee-Heimer. Cbc user guide. In Emerging theory, methods, and applications, pages 257–277. INFORMS, 2005. [4] Juris Hartmanis. Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson). Siam Review, 24(1):90, 1982. [5] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical programming, 14(1):265–294, 1978. [6] Dorit S Hochba. Approximation algorithms for np-hard problems. ACM Sigact News, 28(2):40–52, 1997. [7] Stuart Mitchell, Michael OSullivan, and Iain Dunning. Pulp: a linear programming toolkit for python. The University of Auckland, Auckland, New Zealand, 65:25, 2011. 3