# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**75**> 76 77 78 79 80 81 .. 156 >> Next

In this section we discuss one such method (see Balas and Samuelsson, 1973, 1974a). We first discuss the procedure for the unweighted node covering problem, then its extension to the weighted case.

The unweighted node covering problem can be stated as

nc min {e„x | ATx ^ eq, x, = 0 or 1, j e N}

where N = {1,..., n}, A is the nxq node-edge incidence matrix of a graph G = (N, E), T means transpose, and en, eq are vectors of ones of appropriate dimensions.

Set Partitioning—A Survey

201

A minimum partial cover N is a subset of nodes which is a minimum cover in the subgraph obtained from G by removing all edges not incident with N. For the purposes of this section, a clique will be defined as a set of pair wise adjacent nodes (i.e. a set of nodes inducing a complete subgraph; however, the set does not have to be maximal, and the term refers to the node set instead of the subgraph itself).

The algorithm starts with a minimum partial cover and uses a labelling procedure to increase the number of edges that are covered. This procedure ends after at most n(q + 1) steps. If all edges are covered, the solution is optimal. Otherwise the problem is partitioned, i.e. G is replaced by two proper subgraphs, and the procedure is applied to the latter.

The key concept behind the labelling procedure is that of a dual nodeclique set. If K is the set of all cliques (in the above sense) in G, then (N, K), where N <= N, K c K, is defined to be a dual node-clique set if

(i) the cliques of K are pairwise node-disjoint;

(ii) each node in N belongs to some clique in K;

(hi) each clique in K contains exactly one node not in N.

It can be shown that if (JV, K) is a dual node-clique set, then IV is a minimum partial cover, which defines a dual-feasible solution to the linear program obtained from nc by removing the integrality requirement and adding a constraint of the form

I *,^101-1

/eQ

for each clique in G. (When the cliques are maximal, this constraint is a facet—the complement of the corresponding clique-facet for the node packing or set packing problem, discussed in Section 7.2.1.)

These properties are used in the algorithm to perform implicitly, via a clique-labelling procedure, what in fact amounts to sequences of pivots in all-integer dual cutting plane method, where the cuts are the above inequalities. Dual feasibility is preserved by the fact that the partial covers generated by the labelling procedure are all associated with dual node-clique sets, i.e. are all minimal. A statement of the algorithm follows.

Step 0 Finding an initial solution Any edge matching (set of disjoint 2-cliques) can be used to generate an associated minimal partial node cover (and dual node-clique set). The larger the size of the edge-matching, the better the starting solution. An heuristic is used to find a good matching rapidly.

Let (N, K) be the current dual node-clique set (K is the set of labelled cliques).

Step 1 Improving the solution (Labelling procedure) Scan E for edges not

202

Egon Balas and. Manfred W. Padberg

covered by N, and for each such edge (i, j) attempt to perform one of the following steps in order:

(a) (First labelling step) If neither i nor j belongs to a labelled clique (i.e. a clique in K), label the 2-clique {i, /}, and put into N either i or j, whichever covers more new edges.

(b) (Reassignment step) If either i or j can replace in N one of the members of the labelled clique to which it belongs without uncovering an edge, make the switch to cover (i, j).

(c) (Second labelling step) Find a largest unlabelled clique Q* containing i and j, if it exists, such that |Q*|s=3 and

(i) if any h e Q. belongs to some QeK, then Q <=? Q* or Q is a 2-clique;

(ii) Q* contains a labelled clique or a node j e N.

If found, then

(«) label (put into K) Q*, and ‘unlabel’ (remove from K) all labelled cliques contained in Q* and labelled 2-cliques incident with Q*;

((3) put into N all but one of the nodes in Q*, and remove from N all nodes not in Q*, belonging to labelled 2-cliques incident with Q*. If, when no more applications of (a), (b), (c) are possible, the current N is a cover, then it is optimal (for its subproblem). Otherwise go to Step 2.

Step 2 Partitioning (Branching and bounding) Choose i* e N having a maximum number of adjacent nodes not in N, and partition the feasible set by '

(*„ = l)V[*i. = 0 and Xj = 1, V/:(i*, j)eE].

This gives rise to two subproblems, whose associated graphs are the subgraphs of G induced by the node sets N-{i%} and N — [{<*} U {/ e N | (;*, j) e E}], respectively. For each of the two subgraphs, a dual node-clique set can be obtained from the dual node-clique set of the parent graph, by local modifications only.

Calculate a lower bound on the value of each subproblem (the cardinality of the minimal partial cover N defined by the new dual node-clique set is one such bound; solving a structured linear program yields another, often stronger bound).

Select a subproblem and go to Step 1.

**75**> 76 77 78 79 80 81 .. 156 >> Next