# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**3**> 4 5 6 7 8 9 .. 156 >> Next

The fundamental point to be made here is that the basic branch and bound concept is so simple that it allows ample room for the inclusion of many heuristic rules which can be devised for any particular instance of a combinatorial problem. These rules tend to be of little theoretical interest, but along with the cleverness of the implementation they are often the key elements in determining success or failure of these techniques. A large portion of this chapter will be devoted to discussion of rules which have been proposed for the milp and the reasons for their success or failure.

In most commercial codes, the details of the algorithm are adjustable. That is, there are options for performing many of the steps. The options used in solving a particular milp may be chosen internally by the program or externally by the user. The way in which these matters are handled by various codes is mentioned throughout the paper. The reader is directed to Land and Powell (1977) for more details.

Branch and bound algorithms are almost always primal in the sense that they proceed from one feasible solution to another until optimality is verified. In fact they often find optimal or near optimal solutions early in the enumeration process and spend the majority of the time verifying optimal-

Branch and Bound Methods for Integer Programming

3

ity. Thus the user can be comforted by the expectation that termination before proof of optimality will likely yield a very good solution if not an optimal one. This contrasts to other approaches, for example Gomorys fractional cutting plane algorithm (Gomory, 1958), where a feasible solution is not found until termination.

Branch and bound was first proposed for milps by Land and Doig (1960). Since then a vast number of papers and books have appeared on the subject. Some other surveys include: Tomlin (1970), Garfinkel and Nemhauser (1972a), Geoffrion and Marsten (1972), and Land and Powell (1977). In Land and Powell (1977), eleven commercial codes are analysed with respect to specific techniques used and options available. Some of this work is briefly summarized in Section 1.13. The codes are numbered in Table 1.1 and will be referred to by these numbers throughout the text.

The special branch and bound methods which have been developed for binary ilps by Balas, Geoffrion, Glover, and others and are often termed implicit enumeration will not be discussed in this paper. In general, these methods are so specialized that they are often distinguished from branch and bound. The reader is referred to Breu and Burdet (1974) for a computational study of these problems.

1.2 Elements of Branch and Bound Algorithms

In this section we distinguish four fundamental elements of a branch and bound algorithm. These are: separation (partition) into subproblems; relaxation (upper bounding); fathoming of subproblems (lower bounding); and selection of subproblems (branching). Each of these elements is explored in detail in a later section. Here we give an overview of the elements and the relation between them.

Denote the set of feasible solutions to (1.1) by

S = {x | Ax =s i>, x 2= 0, x, integer, j e I}.

Instead of attempting to solve the problem directly over S, the set is successively divided into smaller and smaller sets which have the property that any optimal solution must be in at least one of the sets. This is called separation and is often illustrated by an enumeration tree such as that of Figure 1.1 (see Section 1.6 for an alternative representation of the tree).

Each node of the enumeration tree corresponds to a subproblem of (1.1). That is, node k is the problem

max z, xeSk (I lk)

where Sk c s. As the enumeration proceeds farther down the tree, the sets Sk become progressively smaller until it finally becomes possible to solve

4

Robert S. Garfi.nk.el

Figure 1.1

(1.1k) or at least to determine whether or not it contains a potentially optimal solution. The enumeration process will be sucessful if this happens before the tree becomes impossibly large.

Upper bounds zk on zk, the maximum value of z0 over Sk, will be calculated. As will be seen below, the quality of these bounds will be critical. By the quality of zk, we mean its closeness to zk. zk will generally be

calculated by solving a relaxation of (l.lk). That is, a problem of the form

maxw(x), xeTk (l-2k)

where Sk s Tk and w(x)s*cx for all x e Sk. Typically (1.2k) will be a linear program (lp).

Subproblems are discarded or fathomed when (l.lk) is solved, or when it is determined that Sk does not contain a solution which can improve on the best known solution to (1.1). Denoting the latter as the incumbent, and its value by z, we can certainly fathom Sk if z* =? z.

If z* is unknown, as is generally the case, it suffices to have

zkz (1.3)

for fathoming Sk. Thus it becomes clear that not only is the quality of the bound zk of critical importance, but also the quality of z. More will be said about achieving good lower bounds later.

**3**> 4 5 6 7 8 9 .. 156 >> Next