Matching and Edge Covering Algorithms.

Abstract

This study deals with the minimum weight 1-matching/covering problem defined here as follows: given an undirected network G = (N,A,c) where N is a nonempty set of n nodes, A is a set of m edges, and c is a vector of edge weights, find a 0-1 vector x = {x(i;j)} to minimize (SIGMA)(,ij) {c(i;j) x(i;j) : (i;j) (ELEM) A} (LESSTHEQ) 1 for i (ELEM) N('-) subject to (SIGMA)(,j) {x(i;j) : (i;j) (ELEM) A} = 1 for i (ELEM) N('1) (GREATERTHEQ) 1 for i (ELEM) N('+) unconstrained for i (ELEM) N('0) x(i;j) = 0, 1 for (i;j) (ELEM) A where N('-),N('1),N('+),N('0) is a given partition. The minimum weight 1-matching/covering problem is an extension of well known problems like the minimum weight 1-matching (N = N('-)), the minimum weight 1-perfect matching (N = N('1)), and the minimum weight 1-edge covering (N = N('+)). A primal dual algorithm with time complexity O(n('2)m) is developed for solving the problem; such time complexity can be further improved to O(n('3)). Like many other combinatorial optimization problems, appropriate constraints - blossom constraints - are introduced in the problem in order to obtain the optimality conditions through Linear Programming Theory. Computer results are discussed based on a PL1 implementation of the algorithm. As a remark, the computer program can be seen as a simple extension of a computer program for the minimum weight 1-matching problem. Another O(n('2)m) algorithm is developed in order to deal with sensitivity analysis; by sensitivity analysis is meant the study of the changes in the optimal solution when modifications are introduced either in the structure of the network or in the edge weights; furthermore, we discuss how to solve the modified problem starting from the old optimal solution. A very promising application of the minimum weight 1-matching/covering problem is proposed; it appears in a branch and bound approach for solving the set covering problem; the approach is based on the Lagrangian Relaxation of the c and idate problems into minimum weight 1-matching/covering problems, which are efficiently solved in order to obtain good lower bounds for the objective value of the original set covering problem. The Lagrangian Relaxation technique requires the c and idate problem to be solved with a sequence of different objective functions; these c and idate problems maintain a certain initial structure and change the cost coefficient of the objective function. The efficient computation of the c and idate problems with so many objective functions is made possible by the successive application of the sensitivity analysis results, because the changes in the objective function correspond to changes in the edge weights of the network.