# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**56**> 57 58 59 60 61 62 .. 156 >> Next

We assume some familiarity on the part of the reader with the basic concepts of graph theory. For background material in this field, the reader is referred to Harary (1969), Berge (1970), Roy (1969, 1970), Christofides (1975). For background in the general areas of linear and integer programming, see Dantzig (1963) and Simmonard (1966) for the former, and Garfinkel and Nemhauser [1972] for the latter.

Set PartitioningA Survey

7.1 Background

153

7.1.1 Set Partitioning and its Uses

Among all special structures in (pure) integer programming, there are three which have the most widespread applications: set paritioning, set covering, and the travelling salesman (or minimum length hamiltonian cycle) problem; if we were to rank the three, set partitioning would be a likely candidate for number one.

The (weighted) set partitioning (or equality-constrained set covering) problem is

spp min {oc | Ax = e, Xj = 0 or 1, V; e N)

where A is an m x n matrix of zeros and ones, c is an arbitrary n-vector, e (1,..., 1) is an m-vector, and N = {1,. .., n}. Its name comes from the following interpretation: if the rows of A axe associated with the elements of the set M = {1,..., m} and each column a, of A with the subset Mf of those i M such that a = 1, then spp is the problem of finding a minimum-weight family of subsets Mp j e N, which is a partition of M, each subset M, being weighted with cP

A partial list of applications described in the literature includes: railroad crew scheduling, truck deliveries, airline crew scheduling, tanker routing, information retrieval, switching circuit design, stock cutting, assembly line balancing, capital equipment decisions, location of offshore drilling platforms, some other facility location problems, and political districting. A special bibliography on applications is given as an Appendix to this chapter.

A great variety of scheduling problems can be formulated as follows. Given (i) a finite set M; (ii) a constraint set defining a family F of acceptable subsets of M; and (iii) a cost (real number) associated with each member of F; find a minimum-cost collection of members of F which is a partition of M

The usefulness and wide applicability of the set partitioning model follows from the simple observation that in most cases a problem of the above form can be solved to a satisfactory degree of approximation by the following two-stage procedure.

Stage 1 Using (ii), generate explicitly a subset F<=F, such that the probability of an optimal solution being contained in F is sufficiently high.

Stage 2 Replace the constraint set (ii) by a list of the members of F and solve the resulting spp.

The most widely used application to date of the set partitioning model seems to be the airline crew scheduling problem, in which M corresponds to

154

Egon Balas and Manfred W. Padberg

the set of flight legs (from city A to city B, at time r) to be covered during a planning period (usually a few days), while each subset M] stands for a possible tour (sequence of flight legs with the same initial and terminal point) for a crew. In order to be acceptable, a tour must satisfy certain regulations. To set up the problem, one starts with a given set of (usually several hundred) flight legs, and one generates by computer a set of (usually several thousand) acceptable tours, with their respective costs. This produces A (of density usually *?0.05) and c>0, after which one attempts to solve the set partitioning problem. If the attempt is successful, the solution yields a minimum-cost collection of acceptable tours such that each flight leg is included in exactly on tour of the collection.

Airline crew scheduling problems with 300-500 constraints and 2500-4000 variables are sometimes solved (to optimality), but often much smaller problems (with several hundred variables) defy solution within reasonable time limits.

7.1.2 Set Packing and Set Covering

The set partitioning problem (spp) has two seemingly close relatives; the set packing problem

sp max (c'x | Ax e, Xj = 0 or 1, V; e N}

and the set covering problem

sc min (c"x | Ax 2: e, x, = 0 or l,V/eN}

where A, e, and N are defined as in spp, while c' and c" are arbitrary n-vectors.

At a closer look, however, it turns out that sc is a much more distant relative than sp. Intuitively, one can guess this from the fact that sp, like spp, is a tightly constrained problem (each constraint requires at most one, or exactly one, of many variables to be 1), whereas sc is a loosely constrained problem (at least one of many variables is required to be 1). More precisely, the relationship is as follows. spp can be brought to the form sc by writing

min {cx + dey | Ax - y = e, y > 0, Xj = 0 or 1, j e N}

and then, using y = Ax e,

min{dm + c'x ] Ax3= e, x, = 0 or 1,/eN}

with c' = 6eA + c. For sufficiently large 6 (e.g. 0 c,), this problem has

the same set of optimal solutions as spp whenever the latter is feasible (see Lemke, Salkin, and Spielberg, 1971). The converse, however, is not true, i.e. sc cannot be brought to the form spp.

**56**> 57 58 59 60 61 62 .. 156 >> Next