On the exact solution of the Euclidean three-matching problem
Three-Matching Problem (3MP) is an NP-complete graph problem which has applications in the field of inserting electronic components on a printed circuit board. In 3MP we want to partition a set of n = 31 points into I disjoint subsets, each containing three points (triplets) so that the total cost o...
Elmentve itt :
| Szerzők: | |
|---|---|
| Testületi szerző: | |
| Dokumentumtípus: | Cikk |
| Megjelent: |
1999
|
| Sorozat: | Acta cybernetica
14 No. 2 |
| Kulcsszavak: | Számítástechnika, Kibernetika, Algoritmus |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12632 |
| LEADER | 01943nab a2200253 i 4500 | ||
|---|---|---|---|
| 001 | acta12632 | ||
| 005 | 20220614094629.0 | ||
| 008 | 161015s1999 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Magyar Gábor | |
| 245 | 1 | 3 | |a On the exact solution of the Euclidean three-matching problem |h [elektronikus dokumentum] / |c Magyar Gábor |
| 260 | |c 1999 | ||
| 300 | |a 357-366 | ||
| 490 | 0 | |a Acta cybernetica |v 14 No. 2 | |
| 520 | 3 | |a Three-Matching Problem (3MP) is an NP-complete graph problem which has applications in the field of inserting electronic components on a printed circuit board. In 3MP we want to partition a set of n = 31 points into I disjoint subsets, each containing three points (triplets) so that the total cost of the triplets is minimal. We consider the problem where the cost Cijk of a triplet is the sum of the lengths of the two shortest edges of the triangle (i, j, k)\ the reason for this assumption is the nature of the practical problems. In this paper we discuss the optimal solution of 3MP. W e give two different integer formulations and several lower bounds of the problem based on the Lagrangian relaxations of the integer programs. The different lower bounds are evaluated by empirical comparisons. We construct branch-andbound procedures for solving 3MP by completing the best lower bound with appropriate branching operations. The resulting procedures are compared to our previous exact method and to general MIP solvers. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika, Algoritmus | ||
| 700 | 0 | 1 | |a Johnsson Mika |e aut |
| 700 | 0 | 1 | |a Nevalainen Olli |e aut |
| 710 | |a Conference for PhD Students in Computer Science (1.) (1998) (Szeged) | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12632/1/cybernetica_014_numb_002_357-366.pdf |z Dokumentum-elérés |