结合look-ahead值排序的自适应分支求解算法

doi:10.3969/j.issn.1000-436X.2013.06.012

Journal on Communications ›› 2013, Vol. 34 ›› Issue (6): 102-107.doi: 10.3969/j.issn.1000-436X.2013.06.012

• paper • Previous Articles Next Articles

Novel adaptive branching constraint solving algorithm with look-ahead strategy

Hai-yan WANG¹,YANGDan-tong OU¹,Yong-gang ZHANG¹,Liang ZHANG¹

¹ College of Computer Science and Technology, Jilin University, Changchun 130012,China
² Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education, Jilin University, Changchun 130012, China
³ College of Computer, Jilin Normal University, Siping 136000, China

Online:2013-06-25 Published:2017-07-20
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;Jilin Province Science and Technology Development Plan;Jilin Province Science and Technology Development Plan;Jilin Province Science and Technology Development Plan;Doctoral Fund of Ministry of Education of China

Abstract

Abstract:

Based on the state-of-the-art scheme of adaptive branching constraint solving, a novel algorithm named AdaptBranch^LVOwas proposed, combined with the look-ahead value ordering heuristics. To demonstrate the efficiency of AdaptBranch^LVO, sufficient experiments on the wide range of the problem instances in Benchmark were carried out, and the experiment results show that AdaptBranch^LVOoutperforms the existing adaptive branching constraint algorithm by a large margin.

Key words: constraint satisfaction problems, look-ahead value ordering heuristics, constraint solving, adaptive branching

Hai-yan WANG,YANGDan-tong OU,Yong-gang ZHANG,Liang ZHANG. Novel adaptive branching constraint solving algorithm with look-ahead strategy[J]. Journal on Communications, 2013, 34(6): 102-107.

Figures/Tables 6

问题实例	2-way	受限的2-way	H₁	H₂	$H_{12}^{\land}$	$H_{12}^{\lor}$
composed-25-10-20-5	47	63	31	32	46	32
composed-25-10-20-7	31	47	32	32	47	31
bqwh-15-106-3	1188	1031	938	969	938	953
bqwh-15-106-4	188	78	78	78	62	93
bqwh-15-106-7	156	47	31	31	31	47
domino-100-100	47	63	46	47	47	62
graph14	1000	3828	985	1 000	985	984

问题实例	技术指标	H₁	H₂	$H_{12}^{\land}$	$H_{12}^{\lor}$	$H_{1}^{L V O}$	$H_{2}^{L V O}$	$H_{12}^{\land L V O}$	$H_{12}^{\lor L V O}$
composed-25-10-20-1	CPU	78	78	94	93	15	31	15	16
	#ccks	75 714	78 512	78 948	78 721	20 465	20 773	19 924	20 465
	#nodes	688	670	657	646	129	130	123	129
composed-25-10-20-3	CPU	93	125	110	78	15	32	16	16
	#ccks	85 757	85 212	87 722	80 270	23 259	22 723	22 494	23 259
	#nodes	813	765	800	727	147	142	138	147
bqwh-15-106-3	CPU	938	969	938	953	47	47	63	47
	#ccks	575 169	565 715	601 714	575 169	22 895	22 897	22 897	22 895
	#nodes	6 533	6 784	6 492	6 533	394	394	388	394
driverlogw-08c-sat_ext	CPU	20 078	19 453	20 266	20 750	18 828	18 188	18 828	19 109
	#ccks	570 795	570 795	570 767	570 795	586 193	586 193	586 165	586 193
	#nodes	3 749	3 749	3 728	3 749	3 901	3 901	3 881	3 901
scen10_w1_f3	CPU	203	250	266	203	172	172	203	188
	#ccks	80 739	86 889	87 405	80 739	83 032	83 715	84 458	83 032
	#nodes	142	206	209	142	129	131	136	129
scen9_w1_f3	CPU	203	250	265	234	187	172	203	188
	#ccks	80 739	86 889	87 405	80 739	83 032	83 715	84 458	83 032
	#nodes	142	206	209	142	129	131	136	129

问题实例	H₁	H₂	$H_{12}^{\land}$	$H_{12}^{\lor}$	$H_{1}^{L V O}$	$H_{2}^{L V O}$	$H_{12}^{\land L V O}$	$H_{12}^{\lor L V O}$
composed-25-10-20	57.9	70.6	78.1	79.6	26.6	32.9	25.1	26.5
bqwh15_106	315.7	311.1	279.6	315.9	287.5	270.1	297	299.8
driver	10 060.3	9 493.29	9 736.71	10 123	9 276.71	9 051.29	9 111.71	9 263.29
frb30-15	965.8	959.4	912.4	981	343.8	447	712.6	674.8
frb35-17	4 506.2	5 500	4 293.4	4 328.2	3 787.6	3 806.2	3 394	4 084.6
rlfapGraphs	1 369.5	1 046.75	1 476.625	1 250	777.5	654.375	640.625	648.375
geom	4 248.125	4 173.75	3 949.25	3 218.75	1 781.25	1 609.375	1 730.625	1 837.875

问题实例	H₁	H₂	$H_{12}^{\land}$	$H_{12}^{\lor}$	$H_{1}^{L V O}$	$H_{2}^{L V O}$	$H_{12}^{\land L V O}$	$H_{12}^{\lor L V O}$
composed-25-1-2	12.5	12.5	15.7	12.5	12.3	12.5	15.9	9.4
ehi-85	5 175.2	11 603.2	5 732.6	11 417.2	4 021.7	9 714	2 393.7	3 551.4
QCP-10	35.25	43	39	34.75	35.25	31.25	35.25	35.5
rlfapModScens	10 795.11	2 449.56	4 395.8	10 767.4	10 119.7	3 531.11	16 131.7	7 043.56

References 8

[1]	BALAFOUTIS T , PAPARRIZOU A , STERGIOU K . Experimental evaluation of branching schemes for the CSP[A]. CoRR[C]. 2010.
[2]	BALAFOUTIS T , STERGIOU S . Adaptive branching for constraint satisfaction problems[A]. IEEE VTC Fall[C]. Lisbon, Portugal, 2010. 1-5.
[3]	HARALICK R M , ELLIOTT G L . Increasing tree search efficiency for constraint satisfaction problems[J]. Artificial Intelligence, 1980,14(3): 263-313.
[4]	BOUSSEMART F , HEREMY F , LECOUTRE C , et al. Boosting systematic search by weighting constraints[A]. Proceedings of ECAI[A]. Proceedings of ECAI[C]. Valencia, Spain, 2004. 482-486.
[5]	DANIEL FROST , RINA DECHTER . look-ahead value ordering for constraint satisfaction problems[A]. Proceedings of IJCAI[C]. Montréal, Québec, Canada, 1995. 572-578.
[6]	LIKITVIVATANAVONG C , ZHANG Y L , BOWEN J , et al. Arc consistency during search[A]. Proceedings of IJCAI[C]. Hyderabad, India, 2007. 137-142.
[7]	STAMATATOS E , STERGIOU K . Learning how to propagate using random probing[A]. Proceedings of CPAIOR[C]. Pittsburgh, USA, 2009. 263-278.
[8]	GRIMES D , WALLACE R J . Sampling strategies and variable selection in weighted degree heuristics[A]. Proceedings of CP[C]. Providence, USA, 2007. 831-838.

Metrics

Recommended 0

No Suggested Reading articles found!

Novel adaptive branching constraint solving algorithm with look-ahead strategy

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 8

Related Articles 2

Metrics

Recommended 0

[1]	HANGYong-gang Z,HANGSi-bo Z,UEQiu-shi X. Improved ant colony optimization algorithm for solving constraint satisfaction problem [J]. Journal on Communications, 2015, 36(5): 40-46.
[2]	. Novel adaptive branching constraint solving algorithm with look-ahead strategy [J]. Journal on Communications, 2013, 34(6): 12-107.