Branch-and-bound technique for solving optimal clustering

被引：0

作者：

Fränti, P ^{[1
]}

Virmajoki, O ^{[1
]}

Kaukoranta, T ^{[1
]}

机构：

[1] Univ Joensuu, Dept Comp Sci, FIN-80101 Joensuu, Finland

来源：

16TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION, VOL II, PROCEEDINGS | 2002年

关键词：

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The problem of finding optimal clustering has not been well covered in literature. Solutions can be found only for special cases, which can be solved in polvnomial time. In this paper, we give solution for the general case. The method generates all possible clusterings by a series of merge steps. The clusterings are organized as a minimum redundancy search tree and the optimal clustering is found by a branch-and-bound technique. The result has theoretical interest and could also provide new insight to the problem itself.

引用

页码：232 / 235

页数：4

共 50 条

[31] Solving linear multiplicative programs via branch-and-bound: a computational experience [J].

R. Cambini ;

R. Riccardi ;

D. Scopelliti .

Computational Management Science, 2023, 20

[32] A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs [J].

Jeff Linderoth .

Mathematical Programming, 2005, 103 :251-282

[33] Solving the Time Dependent Chinese Postman Problem by Branch-and-Bound Algorithm [J].

Tan, Guozhen ;

Sun, Jinghao ;

Meng, Yakun .

INFORMATION-AN INTERNATIONAL INTERDISCIPLINARY JOURNAL, 2012, 15 (12A) :5263-5270

[34] Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm [J].

Haouari, M ;

Chaouachi, J ;

Dror, M .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2005, 56 (04) :382-389

[35] Bob++: Framework for solving optimization problems with branch-and-bound methods [J].

Djerrah, A. ;

Le Cun, B. ;

Cung, V-D. ;

Roucairol, C. .

HPDC-15: PROCEEDINGS OF THE 15TH IEEE INTERNATIONAL SYMPOSIUM ON HIGH PERFORMANCE DISTRIBUTED COMPUTING, 2005, :369-370

[36] Learning efficient branch-and-bound for solving Mixed Integer Linear Programs [J].

Du, Shuhan ;

Tong, Junbo ;

Fan, Wenhui .

APPLIED SOFT COMPUTING, 2025, 172

[37] Integrating frequent pattern clustering and branch-and-bound approaches for data partitioning [J].

Huang, Yin-Fu ;

Lai, Chen-Ju .

INFORMATION SCIENCES, 2016, 328 :288-301

[38] Solving linear multiplicative programs via branch-and-bound: a computational experience [J].

Cambini, R. ;

Riccardi, R. ;

Scopelliti, D. .

COMPUTATIONAL MANAGEMENT SCIENCE, 2023, 20 (01)

[39] A practicable branch-and-bound algorithm for globally solving linear multiplicative programming [J].

Wang, Chun-Feng ;

Bai, Yan-Qin ;

Shen, Pei-Ping .

OPTIMIZATION, 2017, 66 (03) :397-405

[40] BiqCrunch: A Semidefinite Branch-and-Bound Method for Solving Binary Quadratic Problems [J].

Krislock, Nathan ;

Malick, Jerome ;

Roupin, Frederic .

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2017, 43 (04)

← 1 2 3 4 5 →