Uniformly select multi-shell subsets from a multi-shell scheme
This is a demo to uniformly separate multiple subsets from the multi-shell scheme in Human Connectome Project (HCP) using Mixed Integer Linear Programming (MILP)
Reference:
1. "Single- and Multiple-Shell Uniform Sampling Schemes for Diffusion MRI Using Spherical Codes", Jian Cheng, Dinggang Shen, Pew-Thian Yap, Peter J. Basser, IEEE Transactions on Medical Imaging, 2017.
2. "Designing Single- and Multiple-Shell Sampling Schemes for Diffusion MRI Using Spherical Code", Jian Cheng, Dinggang Shen, Pew-Thian Yap, MICCAI 2014.
Copyright (c) 2013, Jian Cheng (jian.cheng.1983@gmail.com)
Contents
read HCP scheme
grad_hcp_all{1}=ReadDirections('/home/jcheng/mywork/output/sampling/HCP_Q3/grad_b1000.txt');
grad_hcp_all{2}=ReadDirections('/home/jcheng/mywork/output/sampling/HCP_Q3/grad_b2000.txt');
grad_hcp_all{3}=ReadDirections('/home/jcheng/mywork/output/sampling/HCP_Q3/grad_b3000.txt');
VisualizeMultiShellScheme(grad_hcp_all{1}, grad_hcp_all{2}, grad_hcp_all{3});
title(['Original 90x3 HCP scheme']);
extract 45x3 samples from 90x3 scheme
clear params grbParams params.numSamples = [45, 45, 45]; % set a lower bound, it can be 0 or covering radius from an initial guess params.lbCost = [0.25,0.25,0.25,0.11]; % params.lbCost = [0,0,0,0]; % if you want to write the model for gurobi_cl % params.ModelFile='model.mps' % params.ResultFile='grb_solution.sol' params.w=0.5; % grb parameters % MIPFocus 1 grbParams.MIPFocus=1; grbParams.TimeLimit=600; grbParams.OutputFlag=true; % run [grad,grb, indexMatrix] = OptimalSamplingMultiSubsetsFromDifferentSets(grad_hcp_all, params, grbParams); % the selected indices for each shell index_1=find(indexMatrix{1}==1); index_2=find(indexMatrix{2}==1); index_3=find(indexMatrix{3}==1);
MIPFocus = 1
Academic license - for non-commercial use only
Optimize a model with 1653 rows, 274 columns and 5220 nonzeros
Variable types: 4 continuous, 270 integer (270 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+00]
Objective range [2e-01, 5e-01]
Bounds range [1e-01, 1e+00]
RHS range [3e+00, 4e+01]
Presolve time: 0.00s
Presolved: 1653 rows, 274 columns, 5220 nonzeros
Variable types: 4 continuous, 270 integer (270 binary)
Presolved: 274 rows, 1927 columns, 5494 nonzeros
Presolve removed 274 rows and 1927 columns
Root relaxation: objective 3.169220e-01, 912 iterations, 0.02 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 0.31692 0 270 - 0.31692 - - 0s
0 0 0.30700 0 263 - 0.30700 - - 0s
H 0 0 0.1834408 0.30700 67.4% - 0s
0 0 0.30409 0 263 0.18344 0.30409 65.8% - 0s
0 0 0.29387 0 263 0.18344 0.29387 60.2% - 0s
0 0 0.29288 0 263 0.18344 0.29288 59.7% - 0s
0 0 0.29041 0 264 0.18344 0.29041 58.3% - 0s
H 0 0 0.1852242 0.29041 56.8% - 0s
0 0 0.28965 0 263 0.18522 0.28965 56.4% - 0s
0 0 0.28888 0 265 0.18522 0.28888 56.0% - 0s
0 0 0.28854 0 266 0.18522 0.28854 55.8% - 0s
0 0 0.28818 0 263 0.18522 0.28818 55.6% - 0s
H 0 0 0.1871523 0.28818 54.0% - 0s
H 0 0 0.1907722 0.28818 51.1% - 2s
0 2 0.28818 0 262 0.19077 0.28818 51.1% - 2s
H 6 8 0.1909499 0.28711 50.4% 210 2s
H 11 16 0.1910040 0.28711 50.3% 212 2s
H 16 20 0.1918854 0.28607 49.1% 253 2s
H 22 22 0.1918855 0.28607 49.1% 246 2s
H 25 25 0.1922160 0.28607 48.8% 232 2s
H 50 51 0.1922764 0.28607 48.8% 177 3s
H 54 53 0.1922764 0.28607 48.8% 171 3s
H 57 58 0.1923796 0.28607 48.7% 171 3s
H 66 64 0.1924249 0.28607 48.7% 158 3s
H 72 71 0.1925004 0.28607 48.6% 150 3s
H 77 79 0.1928935 0.28607 48.3% 143 3s
H 78 79 0.1934989 0.28607 47.8% 144 3s
H 96 96 0.1934989 0.28607 47.8% 140 3s
99 101 0.25960 20 222 0.19350 0.28607 47.8% 139 6s
H 104 105 0.1934989 0.28607 47.8% 136 6s
H 304 305 0.1934989 0.28607 47.8% 69.2 7s
H 502 467 0.1934989 0.28547 47.5% 62.2 9s
H 540 504 0.1934989 0.28547 47.5% 60.8 9s
591 549 0.21252 43 126 0.19350 0.28547 47.5% 59.0 10s
H 600 549 0.1934989 0.28547 47.5% 58.4 10s
1052 850 0.21588 68 262 0.19350 0.26429 36.6% 46.5 16s
1099 886 0.25424 19 243 0.19350 0.25968 34.2% 56.0 20s
H 1430 1042 0.1934989 0.25935 34.0% 55.0 21s
2893 1629 0.24939 22 224 0.19350 0.25778 33.2% 47.6 25s
H 2909 1594 0.1934989 0.25778 33.2% 47.7 25s
4392 2631 0.24350 32 212 0.19350 0.25411 31.3% 45.5 31s
H 4418 2649 0.1934989 0.25411 31.3% 45.5 31s
H 4673 2852 0.1934990 0.25411 31.3% 45.6 32s
H 4744 2892 0.1934990 0.25366 31.1% 45.5 33s
5035 3118 0.19673 56 89 0.19350 0.25343 31.0% 45.2 38s
5295 3344 0.23223 31 193 0.19350 0.25343 31.0% 44.7 41s
H 5300 3344 0.1934990 0.25343 31.0% 44.7 41s
H 5312 3356 0.1934991 0.25343 31.0% 44.7 41s
6394 4155 0.24336 25 221 0.19350 0.25275 30.6% 44.1 47s
H 6458 4195 0.1934991 0.25275 30.6% 44.1 47s
7483 4961 0.19609 71 62 0.19350 0.25218 30.3% 43.5 52s
H 7654 5043 0.1934991 0.25197 30.2% 43.3 52s
8167 5415 0.23330 33 200 0.19350 0.25173 30.1% 42.8 55s
H 8394 5565 0.1934991 0.25172 30.1% 42.8 55s
9436 6345 0.20165 66 55 0.19350 0.25143 29.9% 42.6 61s
H 9619 6439 0.1934991 0.25141 29.9% 42.6 61s
H10065 6809 0.1934991 0.25124 29.8% 42.8 64s
10150 6900 0.21017 51 131 0.19350 0.25119 29.8% 42.8 68s
10607 7230 0.20475 65 108 0.19350 0.25100 29.7% 42.9 70s
H10784 7291 0.1934994 0.25097 29.7% 42.8 70s
11752 8076 0.21659 39 161 0.19350 0.25078 29.6% 42.6 78s
H11898 8159 0.1934994 0.25078 29.6% 42.6 78s
12187 8429 0.20022 56 93 0.19350 0.25042 29.4% 42.7 81s
12315 8524 0.24581 27 229 0.19350 0.25041 29.4% 42.7 85s
H13063 9076 0.1934994 0.25030 29.4% 42.6 88s
13174 9162 0.22015 36 166 0.19350 0.25024 29.3% 42.6 94s
H13254 9210 0.1934994 0.25024 29.3% 42.5 94s
13535 9419 0.24135 24 209 0.19350 0.25014 29.3% 42.5 101s
H14064 9759 0.1934994 0.25009 29.2% 42.4 101s
14263 9951 0.24477 25 237 0.19350 0.25003 29.2% 42.3 105s
H14501 10095 0.1934994 0.24998 29.2% 42.3 105s
14828 10363 0.20413 53 121 0.19350 0.24993 29.2% 42.4 111s
H15305 10666 0.1934994 0.24984 29.1% 42.3 111s
H15624 10906 0.1934994 0.24976 29.1% 42.2 111s
15625 10954 0.23681 31 218 0.19350 0.24970 29.0% 42.2 116s
H15896 11081 0.1934994 0.24966 29.0% 42.2 116s
H16101 11245 0.1934994 0.24962 29.0% 42.2 116s
16374 11522 0.24307 25 232 0.19350 0.24955 29.0% 42.1 122s
H16608 11656 0.1934994 0.24955 29.0% 42.2 122s
H16635 11670 0.1934994 0.24955 29.0% 42.2 122s
16790 11804 0.22129 32 164 0.19350 0.24955 29.0% 42.3 127s
H16811 11824 0.1934994 0.24955 29.0% 42.3 127s
17202 12093 0.22217 33 154 0.19350 0.24951 28.9% 42.3 132s
H17891 12508 0.1934994 0.24942 28.9% 42.1 132s
18206 12808 0.23405 28 201 0.19350 0.24927 28.8% 42.1 139s
H18590 13026 0.1934994 0.24920 28.8% 42.1 139s
H19027 13278 0.1934994 0.24918 28.8% 42.1 139s
19218 13536 0.23391 29 177 0.19350 0.24911 28.7% 42.2 144s
H19410 13618 0.1934994 0.24911 28.7% 42.2 144s
20230 14309 0.24260 30 213 0.19350 0.24898 28.7% 42.1 151s
H21026 14842 0.1934994 0.24893 28.6% 42.2 151s
21098 14952 0.22066 34 190 0.19350 0.24893 28.6% 42.3 160s
H21099 14952 0.1934994 0.24893 28.6% 42.3 160s
H21100 14952 0.1934994 0.24893 28.6% 42.3 160s
21222 15013 0.21774 37 190 0.19350 0.24891 28.6% 42.2 166s
22592 16027 0.20952 56 107 0.19350 0.24888 28.6% 42.2 173s
H22880 16235 0.1934994 0.24888 28.6% 42.2 173s
22945 16278 0.20642 60 100 0.19350 0.24876 28.6% 42.2 179s
H23380 16549 0.1934994 0.24862 28.5% 42.1 179s
23493 16663 0.20069 55 62 0.19350 0.24860 28.5% 42.2 183s
H23608 16749 0.1934994 0.24860 28.5% 42.1 183s
23831 16911 0.22722 31 192 0.19350 0.24860 28.5% 42.1 189s
H23900 16911 0.1934994 0.24860 28.5% 42.1 189s
H25068 17612 0.1934994 0.24848 28.4% 42.0 189s
25323 18008 0.23853 26 204 0.19350 0.24841 28.4% 42.0 194s
H25756 18283 0.1934994 0.24837 28.4% 42.0 194s
26363 18805 0.20744 54 139 0.19350 0.24820 28.3% 42.0 200s
H26400 18805 0.1934994 0.24820 28.3% 42.1 200s
26867 19137 0.22535 43 158 0.19350 0.24816 28.2% 42.1 207s
28112 20021 0.20104 46 117 0.19350 0.24810 28.2% 42.0 215s
H28200 20021 0.1934994 0.24810 28.2% 42.0 215s
H28850 20533 0.1934994 0.24804 28.2% 42.1 215s
29040 20742 0.22112 40 167 0.19350 0.24802 28.2% 42.0 223s
H29200 20742 0.1934994 0.24802 28.2% 42.0 223s
H29383 20983 0.1934994 0.24802 28.2% 42.1 223s
29950 21410 0.23894 34 208 0.19350 0.24797 28.2% 42.0 229s
H30051 21454 0.1934994 0.24797 28.1% 42.0 229s
31064 22234 0.21654 46 168 0.19350 0.24790 28.1% 42.1 236s
H31100 22234 0.1934994 0.24790 28.1% 42.0 236s
H31585 22576 0.1934994 0.24785 28.1% 42.0 236s
31960 22862 0.23812 34 213 0.19350 0.24781 28.1% 42.1 244s
H32300 22862 0.1934994 0.24781 28.1% 42.0 244s
H32917 23543 0.1934994 0.24775 28.0% 42.0 244s
33429 23922 0.20935 56 107 0.19350 0.24766 28.0% 42.1 251s
H34397 24596 0.1934994 0.24766 28.0% 42.1 251s
34542 24718 0.21766 49 160 0.19350 0.24756 27.9% 42.1 256s
H34798 24798 0.1934994 0.24755 27.9% 42.0 256s
35643 25494 0.22395 40 176 0.19350 0.24744 27.9% 42.0 261s
36519 26151 0.21107 51 152 0.19350 0.24739 27.8% 42.0 268s
H37310 26694 0.1934994 0.24735 27.8% 42.1 268s
37770 27083 0.22573 47 159 0.19350 0.24732 27.8% 42.1 277s
H37931 27185 0.1934994 0.24731 27.8% 42.1 277s
38633 27724 0.23418 28 187 0.19350 0.24726 27.8% 42.1 285s
H38649 27724 0.1934994 0.24726 27.8% 42.1 285s
H38700 27724 0.1934994 0.24726 27.8% 42.1 285s
39882 28622 0.23728 27 222 0.19350 0.24721 27.8% 42.1 293s
H39900 28622 0.1934994 0.24721 27.8% 42.1 293s
40832 29322 0.21476 40 143 0.19350 0.24718 27.7% 42.1 300s
H40900 29322 0.1934994 0.24718 27.7% 42.0 300s
41818 30016 0.21403 49 156 0.19350 0.24704 27.7% 42.0 309s
H42711 30553 0.1934994 0.24702 27.7% 41.9 309s
H43077 30732 0.1934994 0.24700 27.6% 41.9 309s
43196 31043 0.24401 25 225 0.19350 0.24693 27.6% 41.9 319s
H43205 31045 0.1934994 0.24693 27.6% 41.9 319s
H43366 31171 0.1934994 0.24693 27.6% 41.9 319s
43692 31416 0.24068 30 216 0.19350 0.24693 27.6% 41.9 326s
H44045 31658 0.1934994 0.24693 27.6% 42.0 326s
44257 31810 0.22441 39 171 0.19350 0.24690 27.6% 42.0 334s
H44300 31810 0.1934994 0.24690 27.6% 42.0 334s
45086 32456 0.19488 50 72 0.19350 0.24681 27.5% 42.0 343s
H45089 32456 0.1934994 0.24681 27.5% 42.0 343s
H45092 32456 0.1934994 0.24681 27.5% 42.0 343s
46000 33125 0.24034 28 227 0.19350 0.24681 27.5% 42.0 349s
H46001 33126 0.1934994 0.24681 27.5% 42.0 349s
46264 33299 0.23969 29 219 0.19350 0.24679 27.5% 42.0 356s
H46437 33332 0.1934994 0.24679 27.5% 42.0 356s
H47185 34003 0.1934994 0.24670 27.5% 42.0 356s
47686 34412 0.24100 27 220 0.19350 0.24664 27.5% 42.0 363s
H47728 34431 0.1934994 0.24664 27.5% 42.0 363s
H48023 34640 0.1934994 0.24663 27.5% 42.0 364s
H48453 34726 0.1934994 0.24661 27.4% 42.0 364s
48769 35171 0.24059 30 228 0.19350 0.24659 27.4% 42.0 372s
H49000 35171 0.1934994 0.24659 27.4% 42.0 372s
49925 36007 0.21736 42 174 0.19350 0.24656 27.4% 42.0 380s
H50376 36194 0.1934994 0.24654 27.4% 42.1 380s
51733 37293 0.21470 43 133 0.19350 0.24647 27.4% 42.0 387s
H52140 37552 0.1934994 0.24647 27.4% 42.0 387s
53128 38338 0.20271 52 95 0.19350 0.24639 27.3% 42.0 393s
H53473 38452 0.1934994 0.24638 27.3% 42.0 393s
54651 39461 0.21586 39 168 0.19350 0.24628 27.3% 42.0 399s
H54700 39461 0.1934994 0.24628 27.3% 42.0 399s
H55250 39898 0.1934994 0.24627 27.3% 42.0 399s
55251 39905 0.21511 43 155 0.19350 0.24626 27.3% 42.0 408s
56551 40860 0.21663 46 169 0.19350 0.24622 27.2% 42.0 415s
H57058 41202 0.1934994 0.24620 27.2% 42.0 415s
57588 41556 0.23046 39 212 0.19350 0.24616 27.2% 41.9 423s
H58452 42190 0.1934994 0.24612 27.2% 41.9 423s
58544 42248 0.24487 28 232 0.19350 0.24611 27.2% 41.9 433s
H58857 42295 0.1934994 0.24611 27.2% 41.9 433s
H59716 42947 0.1934994 0.24609 27.2% 41.9 433s
59874 43239 0.23038 37 194 0.19350 0.24606 27.2% 41.9 441s
H60100 43239 0.1934994 0.24606 27.2% 41.9 441s
H60396 43640 0.1934994 0.24605 27.2% 41.9 441s
60944 44035 0.23347 36 188 0.19350 0.24602 27.1% 41.9 448s
H61214 44212 0.1934994 0.24601 27.1% 41.9 448s
62176 45020 0.20314 55 101 0.19350 0.24598 27.1% 41.9 457s
H62300 45020 0.1934994 0.24598 27.1% 41.9 457s
H62800 45413 0.1934994 0.24597 27.1% 42.0 457s
63244 45807 0.21166 43 162 0.19350 0.24595 27.1% 41.9 464s
H63828 46213 0.1934994 0.24593 27.1% 41.9 464s
64200 46561 0.22992 36 190 0.19350 0.24593 27.1% 42.0 473s
H64201 46562 0.1934994 0.24593 27.1% 42.0 473s
H64203 46562 0.1934994 0.24593 27.1% 42.0 473s
H64333 46661 0.1934994 0.24593 27.1% 41.9 473s
64472 46735 0.22856 37 179 0.19350 0.24592 27.1% 41.9 482s
H64700 46735 0.1934994 0.24592 27.1% 41.9 482s
66450 48207 0.21328 38 133 0.19350 0.24588 27.1% 41.9 491s
H67186 48529 0.1934994 0.24588 27.1% 41.9 491s
67389 48847 0.23808 28 213 0.19350 0.24588 27.1% 41.9 500s
H67400 48847 0.1934994 0.24588 27.1% 41.9 500s
68033 49263 0.21260 40 167 0.19350 0.24585 27.1% 41.8 507s
69967 50651 0.22305 35 173 0.19350 0.24574 27.0% 41.8 516s
71061 51443 0.22898 32 178 0.19350 0.24570 27.0% 41.7 526s
72081 52178 0.23948 30 211 0.19350 0.24564 26.9% 41.7 534s
H72383 52398 0.1934994 0.24563 26.9% 41.7 534s
73463 53181 0.21394 39 137 0.19350 0.24562 26.9% 41.7 542s
H73500 53181 0.1934994 0.24562 26.9% 41.7 542s
74560 53968 0.23918 26 212 0.19350 0.24558 26.9% 41.7 551s
H74841 54081 0.1934994 0.24557 26.9% 41.7 551s
75834 54879 0.24014 29 214 0.19350 0.24553 26.9% 41.7 558s
H76264 55003 0.1934994 0.24553 26.9% 41.7 558s
H77249 55876 0.1934994 0.24552 26.9% 41.6 558s
77250 55969 0.22201 46 184 0.19350 0.24549 26.9% 41.6 566s
H77356 56016 0.1934994 0.24549 26.9% 41.6 566s
78567 56851 0.21166 49 146 0.19350 0.24547 26.9% 41.6 574s
H79136 57246 0.1934994 0.24547 26.9% 41.6 574s
H79270 57273 0.1934994 0.24547 26.9% 41.6 574s
79739 57686 0.23997 29 226 0.19350 0.24546 26.9% 41.6 583s
H80681 58368 0.1934994 0.24536 26.8% 41.6 583s
80758 58464 0.23068 42 185 0.19350 0.24534 26.8% 41.6 590s
H80900 58464 0.1934994 0.24534 26.8% 41.6 590s
H81558 59013 0.1934994 0.24533 26.8% 41.6 590s
81702 59113 0.21153 41 151 0.19350 0.24532 26.8% 41.6 599s
H82466 59619 0.1934994 0.24530 26.8% 41.5 599s
82973 60063 0.23094 33 192 0.19350 0.24528 26.8% 41.6 600s
Cutting planes:
Gomory: 3
Clique: 60
MIR: 131
StrongCG: 182
Flow cover: 590
Zero half: 21
Explored 83354 nodes (3467489 simplex iterations) in 600.02 seconds
Thread count was 8 (of 8 available processors)
Solution count 10: 0.193499 0.193499 0.193499 ... 0.193499
Time limit reached
Best objective 1.934994111288e-01, best bound 2.452566943159e-01, gap 26.7480%
visualize the result
VisualizeMultiShellScheme(grad{1},grad{2},grad{3});
title({'Estimated scheme.', ['Combined covering radius = ', num2str(CoveringRadius([grad{1};grad{2};grad{3}])*180/pi), ' degree']});
