A solver for the maximum(-weight) independent set and for the maximum(-weight) clique problems.
To solve a stable (resp. clique) problem, it is possible to use a clique (resp. stable) algorithm on the complementary graph (option --complementary). However, graphs being generally sparse, the complementary graph might be huge. When a more optimized implementation is possible, both are implemented.
The stable solver can also be used to solve the Minimum (Weight) Vertex Cover Problem by just considering the vertices outside of the solution.
-
Greedy algorithms, see "A note on greedy algorithms for the maximum weighted independent set problem" (Sakai et al., 2001) DOI
-a greedy-gwmin-a greedy-gwmax-a greedy-gwmin2-a greedy-strong
-
Mixed-Integer Linear Programs
- Model 1,
|E|constraints-a milp-1 - Model 2,
|V|constraints, see "A multi-KP modeling for the maximum-clique problem" (Della Croce et Tadei, 1994) DOI-a milp-2 - Model 3, clique constraints, see "A Branch-and-Bound Algorithm for the Knapsack Problem with Conflict Graph" (Bettinelli et al., 2017) DOI (seems useless since solvers already detect and merge clique constraints)
-a milp-3
- Model 1,
-
Local search algorithm implemented with fontanf/localsearchsolver
-a "local-search --threads 3" -
Row weighting local search (unweighted only)
- based on "Weighting-Based Parallel Local Search for Optimal Camera Placement and Unicost Set Covering" (Lin et al., 2020) DOI
-a "local-search-row-weighting-1 --iteration-limit 100000 --iteration-without-improvment-limit 10000" - based on "An efficient local search heuristic with row weighting for the unicost set covering problem" (Gao et al., 2015) DOI
-a "local-search-row-weighting-2 --iteration-limit 100000 --iteration-without-improvment-limit 10000"
- based on "Weighting-Based Parallel Local Search for Optimal Camera Placement and Unicost Set Covering" (Lin et al., 2020) DOI
-
Large neighborhoodsearch based on "NuMWVC: A novel local search for minimum weighted vertex cover problem" (Li et al., 2020) DOI
-a "large-neighborhood-search"
-
Greedy algorithms:
-a greedy-gwmin, adapted from the stable version, same complexity-a greedy-strong
-
Mixed-Integer Linear Program from "Worst-case analysis of clique MIPs" (Naderi et al., 2021) DOI
-a milp -
Local search algorithm implemented with fontanf/localsearchsolver
-a "local-search"
Download and uncompress the instances in the data/ folder:
Compile:
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release cmake --build build --config Release --parallel cmake --install build --config Release --prefix installSetup Python environment to use the Python scripts:
python3 -m venv .venv source .venv/bin/activate pip install -r requirements.txtDownload data:
python3 scripts/download_data.pyExamples:
./install/bin/stablesolver_stable --verbosity-level 1 --input "data/dimacs1992/brock200_1.clq" --format dimacs1992 --algorithm "local-search-row-weighting-2" --maximum-number-of-iterations 3000 --certificate solution.txt==================================== StableSolver ==================================== Problem ------- Maximum-weight independent set problem Instance -------- Number of vertices: 200 Number of edges: 5066 Density: 0.2533 Average degree: 50.66 Maximum degree: 69 Total weight: 200 Number of connected components: 1 Algorithm --------- Row weighting local search 2 Reduced instance ---------------- Number of vertices: 200 Number of edges: 5066 Density: 0.2533 Average degree: 50.66 Maximum degree: 69 Total weight: 200 Number of connected components: 1 T (s) LB UB GAP GAP (%) Comment ----- -- -- --- ------- ------- 0.003 0 200 200 100.00 0.003 15 200 185 92.50 initial solution 0.003 16 200 184 92.00 iteration 2 0.010 17 200 183 91.50 iteration 2 0.010 18 200 182 91.00 iteration 2 0.010 19 200 181 90.50 iteration 3 0.012 20 200 180 90.00 iteration 1162 0.013 21 200 179 89.50 iteration 2440 Final statistics ---------------- Value: 21 Bound: 200 Absolute optimality gap: 179 Relative optimality gap (%): 89.5 Time (s): 0.0134117 Number of iterations: 3000 Solution -------- Number of vertices: 21 / 200 (10.5%) Number of conflicts: 0 Feasible: 1 Vertex cover weight: 179 Weight: 21 ./install/bin/stablesolver_stable --verbosity-level 1 --input "data/dimacs2010/clustering/caidaRouterLevel.graph" --format dimacs2010 --algorithm "local-search-row-weighting-1" --maximum-number-of-iterations 300000===================================== StableSolver ===================================== Problem ------- Maximum(-weight) independent set problem Instance -------- Number of vertices: 192244 Number of edges: 609066 Density: 3.29601e-05 Average degree: 6.33639 Maximum degree: 1071 Total weight: 192244 Number of connected components: 308 Algorithm --------- Row weighting local search 1 Parameters ---------- Time limit: inf Messages Verbosity level: 1 Standard output: 1 File path: # streams: 0 Logger Has logger: 0 Standard error: 0 File path: Reduction Enable: 1 Max. # of rounds: 10 Reduced instance ---------------- Number of vertices: 2800 Number of edges: 8646 Density: 0.00220561 Average degree: 6.17571 Maximum degree: 56 Total weight: 2800 Number of connected components: 148 Time (s) Value Bound Gap Gap (%) Comment -------- ----- ----- --- ------- ------- 0.000 0 192244 192244 100.00 0.503 117029 192244 75215 39.12 initial solution 0.503 117029 118026 997 0.84 initial solution 0.934 117146 118026 880 0.75 iteration 100000 1.382 117150 118026 876 0.74 iteration 200000 Final statistics ---------------- Value: 117150 Bound: 118026 Absolute optimality gap: 876 Relative optimality gap (%): 0.742209 Time (s): 1.81302 Solution -------- Number of vertices: 117150 / 192244 (60.9382%) Number of conflicts: 0 Feasible: 1 Vertex cover weight: 75094 Weight: 117150