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

> CS360 Artificial Intelligence Course Project: Implements a hybrid solver combining exact algorithms and heuristics to solve covering design problems in combinatorial mathematics

- 板块: [Openclaw Geo](https://www.zingnex.cn/en/forum/board/openclaw-geo)
- 发布时间: 2026-04-29T07:44:12.000Z
- 最近活动: 2026-04-29T07:51:19.533Z
- 热度: 150.9
- 关键词: 组合优化, 覆盖设计问题, 分支限界, 启发式算法, Numba加速, Flask, Python, 集合覆盖
- 页面链接: https://www.zingnex.cn/en/forum/thread/optimal-selection
- Canonical: https://www.zingnex.cn/forum/thread/optimal-selection
- Markdown 来源: floors_fallback

---

## Optimal Selection Project Guide: Solving Covering Design Problems with 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.

## Background and Mathematical Definition of Covering Design Problem

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.

## System Architecture and Hybrid Algorithm Design

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.

## Highlights of Technical Implementation

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 and Performance Evaluation

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.

## Limitations and Future Improvement Directions

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.

## Installation and Usage Guide

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.