• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On the Exact Solutionof the Three-Matching Problem

Gábor Magyar, Mika Johnsson, Olli Nevalainen, On the Exact Solutionof the Three-Matching Problem. TUCS Technical Reports 199, Turku Centre for Computer Science, 1998.

Abstract:

The Three-Matching Problem (3MP) is an NP-complete graph problem arising from the field of inserting electronic components on a printed circuit board. In the 3MP we want to partition a set of n=3l points into l 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); this comes from the nature of the practical problems. In this paper we discuss the optimal solution of the 3MP. We 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 build up branch-and-bound procedures for solving the 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. These comparisons involve Euclidean cases and problem instances with more general cost matrices.

<p>Contact Mika Johnsson (johnsson@cs.utu.fi) for the complete report.

BibTeX entry:

@TECHREPORT{tMaJoNe98b,
  title = {On the Exact Solutionof the Three-Matching Problem},
  author = {Magyar, Gábor and Johnsson, Mika and Nevalainen, Olli},
  number = {199},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {1998},
  ISBN = {952-12-0266-1},
}

Edit publication