Optimal Selection: A Solution System for Covering Design Problems Based on Hybrid Optimization Algorithms

Optimal Selection is a team project for the CS360 Artificial Intelligence course, aiming to solve the NP-hard covering design problem in combinatorial mathematics. This project implements a high-performance hybrid solver combining exact algorithms and heuristics, uses technologies like Numba acceleration to improve efficiency, and provides a user-friendly web interface. It can be applied in multiple fields such as experimental design and machine learning data sampling.

The covering design problem is a classic NP-hard problem in combinatorial optimization. It requires selecting the minimum number of k-tuples from candidate samples such that any j-sample combination appears in at least s k-tuples. Its mathematical definition involves parameters like m (sample pool size: 45-54), n (number of selected samples: 7-25), k (size of each group: 4-7), j (size of covered subset: s≤j≤k), s (coverage count:3-7), with constraints s≤j≤k≤n≤m. For example, selecting 6-tuples from 9 samples, requiring any 5-sample combination to appear at least 5 times, the optimal solution contains 14 groups.

Optimal Selection adopts a four-layer architecture: 1. Preprocessing layer: Problem reduction + bitmask encoding to reduce the search space; 2. Lower bound estimation layer: Count lower bound and Schönheim lower bound to evaluate solution quality and prune; 3. Hybrid solver: For small-scale problems, use branch and bound (LNS + local search) to get optimal solutions; for medium and large-scale problems, use heuristic warm start; 4. Quality search layer (enhanced in v2): Global greedy construction, fixed B descent compression, LNS destruction and repair, local search polishing.

The project's technical highlights include: 1. Numba JIT acceleration for key loops, increasing speed by 30 times; 2. Full bit-set encoding (Python big integers) to optimize set operations for medium-scale instances; 3. Adaptive time budget: Allocate 120/300/600 seconds according to problem scale, with 65% for construction and 35% for quality search; 4. Scale protection mechanism: Avoid memory explosion for ultra-large-scale instances; 5. K-group deduplication to support multiple coverage scenarios.

Application scenarios include experimental design (medical/agricultural experiments), machine learning data sampling, statistical sampling, and combinatorial testing. Performance tests are divided into three layers: correctness test (verify solution correctness for small instances), quality test (acceptable gap for medium instances), stress test (stability under extreme parameters). The v2 version reduced the number of groups from 185 to 178 in the instance with n=20, k=6, j=5, s=4.

Current limitations: Low solving efficiency for ultra-large-scale instances (n>25); limited parameter range; insufficient parallelization. Future directions: Introduce genetic/simulated annealing algorithms; distributed parallel solving; support flexible constraints (weights/priorities); provide solution structure visualization tools.

The system depends on Python 3.11+ and requires installation of Flask, NumPy, and Numba. Installation steps: pip install flask numpy numba; Startup methods: python web_app.py or ./start.sh. The first run of Numba requires 10-30 seconds for compilation, and subsequent runs use cache. It runs by default at http://localhost:3000 and supports mobile device access.