Integer Programming and Network Models

This chapter will sketch the basic notions and essential results of linear programming that are needed in subsequent chapters of this book. For a full treatment, the reader is referred to the pertinent literature.

In this chapter we are not concerned with any specific model but will have a look at some common features shared by many solution techniques or algorithms. In order to avoid confusion, we will use the term problem to denote a general mathematical formulation such as a linear, nonlinear, integer etc., programming model, whereas an instance of a problem will be any specific numerical case or realization of this problem.

In this chapter we introduce some basic definitions and properties of graphs. As opposed to many other areas of combinatorial optimization or mathematical programming in general, the terminology in the field of graphs and networks is not a universally accepted one. In order to make the wide range of books and articles more accessible to the reader, we will—whenever possible—at least mention some of the more frequently used alternative terms even if they are not used in this book.

Richard Bellman is universally recognized as the father of dynamic programming. His research in the 1950’s led to the publication of his book Dynamic Programming; see Bellman (1957). Unfortunately, the name that he gave to this approach to optimization is somewhat misleading as a variety of static problems can be solved with it, but as it is generally accepted we will use it in this book. On the other hand, the term dynamic programming conveys some of the essence of the approach used in this very general technique. The term is used in the sense of recursive or multistage optimization, since the decomposition of a decision problem into interrelated stages lies at the heart of the dynamic programming principle. Unlike other areas of optimization, it is difficult to establish a “canonical” or “standard” form of dynamic programming into which all problems to be solved by this method can be cast. Rather, we may think of dynamic programming as a general computational approach. First a single-stage subproblem is solved, and then successively larger subproblems are solved, recursively, until finally a solution to the original problem has been found.

The subject of this part, the solution of mathematical problems in integer numbers, is not as new as the reader might believe. Certain problems were already known to the Greeks, e.g., Euclid (3rd century B.C.) and Diophantos (3rd century A.D.). Their achievement was the determination of the greatest common divisor (g.c.d.) of a set of numbers (accomplished by the Euclidean Algorithm) as well as some answers to the question: when does a given set of equalities have at least one integer solution? We provide some thoughts to the latter problem in the following section. In 1641 Fermat (1601–1665) in his famous “Last Theorem” considered the equation x ⁿ + y ⁿ = z ⁿ and conjectured that this equality has no integer solution x, y, z in the case of n < 2. Fermat claimed that he had found a proof of this theorem, but it has never been found. The theorem has defied efforts by mathematicians trying to prove it for 300 years, until it was finally proved in 1993 by Andrew Wiles. The proof is long and complicated and involves the so-called Taniyama-Shimura conjecture. A flaw in the proof was corrected a year later. For a full account of the problem, its long history and final solution, see Singh (1997). In the nineteenth century George Boole (1815–1864) expressed logical connections in terms of zero-one variables, i.e., variables that equal either zero or one. Finally, in the middle of the twentieth century after the development of linear programming, the stage was set for finding integral optimal solutions for practical problems.

In this chapter, we discuss how zero-one variables can be used to model conditions that cannot be modeled with the usual continuous variables. The techniques introduced in this chapter are later employed to model important applications.

The previous chapter demonstrated how zero-one variables can be used to model logical relationships. In this chapter we present a number of examples involving integer variables. The applications are selected to show the wide range and the versatility of integer programming. However, in order to avoid duplication, we will not describe problems related to network models that are treated in detail in Parts II and III of this volume. Although numerous applications of integer programming are reported in the literature, surprisingly few books devote much attention to applications. Notable exceptions are Taha (1997), Williams (1978), and Rardin (1998).

In this section we reconsider the task of modeling dealt with in previous chapters. As in linear programming, the basic task is that of defining appropriate variables and expressing the limitations or constraints on these variables in terms of linear relationships. However, straightforward modeling is not always adequate in integer and mixed integer programming. The practical user will soon find that much care needs to be expended in modeling, so that the final solution effort is acceptable. First we consider some common sense measures. Then we outline more complex steps, some of which are conceptual and may be useful at the very outset of creating a model. Finally we describe computational procedures that may be employed to transform a correctly, but poorly formulated model into a well formulated model. In other words, we will attempt to formulate models in such a way that they require less computational effort when solved with the standard procedures described in Chapters 5 and 6 of this part.

In this chapter, we introduce a class of methods that were among the first to be designed for the solution of integer programming problems. Throughout the past decades, however, computational evidence has revealed that cutting planes, while appealing from a theoretical point of view, do not appear to work very well if applied to general integer programming problems. They do find use, however, in some specialized problems and in conjunction with other methods.

The purpose of this chapter is to introduce and illustrate the most popular and successful computational approach to integer programming problems today. Rather than being a specific algorithm, branch and bound is a general principle that allows the user to finetune the procedure and adjust it to the problem under consideration. The first section introduces the general idea, the second section discusses some specific strategies, and Section 3 then describes a general algorithm. Section 4 demonstrates that while branch and bound procedures have been applied successfully to even rather large problems in practice, the algorithm may fail to converge within a reasonable time even if applied to some very simple problems. The fifth section introduces integer programming duality and general relaxation, and Section 6 explains the concepts of Lagrangean decomposition.

In mathematical programming, a heuristic method, or heuristic for short, is a procedure that determines good or near-optimal solutions to an optimization problem. Early heuristics were distinct methods developed to address specific optimization problems. As an example, consider the minimum makespan problem that arises in machine scheduling. In this problem, n given jobs with known processing times must be processed on m machines. The objective is to find a schedule which minimizes the latest finish time of the last job completed. This problem is known to be strongly NP-complete. A simple heuristic to solve this problem is the list heuristic. This method lists the jobs in some given order, then takes the first m jobs and assigns each to exactly one machine, so that at this point, the completion time of each machine corresponds to the processing time of the job assigned to it. Then, the remaining (n — m) jobs are selected in order of the list and assigned one by one to the machine that has currently the earliest finish time. This heuristic has the advantage of being computationally simple, and it can easily be implemented in real time. Better solutions to the problem, i.e., schedules with a shorter makespan, can be determined by improving on the heuristic in the following way: first sort the jobs on the list in nonincreasing order of processing time, and then apply the same machine selection process as presented above. Both heuristics solve the problem; the first is faster computationally, whereas the second is likely to produce better solutions.

One of the most important concepts of graph theory is that of a tree. Its importance is due to the fact that a tree structure enables the connection of a set of nodes using a minimal number of edges in such a way that any two nodes of the set are connected by a unique chain. As such, the tree is a fundamental structure in many fields of study: network theory, social science, computer science, transportation, and many others. The simple structure of trees can offer algorithmic advantages for efficiently solving network path problems. Garey and Johnson (1979) have shown this for certain combinatorial optimization problems. Indeed, a number of problems that are NP-complete when formulated on a general graph become polynomially solvable when the graph is a tree.

The Traveling Salesman Problem (TSP) is one of the most widely studied combinatorial optimization problems. While its statement is deceptively simple, it remains one of the most challenging problems in operations research. Hundreds of articles have been written on the problem. The book edited by Lawler et al. (1985) provides an insightful and comprehensive survey of major research results until that date. The purpose of this chapter is present some exact and approximate algorithms for the traveling salesman problem.

Arc routing problems are among the earliest problems known in the theory of graphs. The source is the Swiss mathematician Leonhard Euler and his famed Königsberg Bridge Problem posed in 1736. It concerns a walk across the seven bridges of Königsberg that lead across the Pregel River; see Figure II.35a. The question Euler asked was whether or not a walk would exist on which each of the bridges is crossed exactly once. When presenting the problem and its solution to the St. Petersburg Academy, Euler did not use the geographical picture of the city, river, and bridges, but a graph-theoretical representation of them which represents bridges as edges, and the ends of the bridges at an island or the banks of the river as nodes. This representation is shown in Figure II.35b.

This chapter first formulates some standard network flow problems. Subsequently, some transformations are explained that allow the reduction of a variety of problems to standard mathematical structures. We then introduce the dual problems, optimality conditions, and finally some results regarding feasibility and integrality.

This section first describes the general principle of augmenting flows as introduced by Ford and Fulkerson (1956) in their seminal contribution. Then a number of modifications and computational improvements are surveyed.

One of the assumptions in the previous chapters was that the flow units sent through the network under consideration were all of the same commodity. In this chapter, we drop this assumption. Clearly, doing so requires assurance that the inflow equals the outflow at all nodes for each commodity separately. Incorporating these requirements in a network flow model is the subject of this chapter.

This chapter examines a number of problems that frequently occur in traffic networks. The main difference between the models in this chapter and those discussed so far is that in traffic models, flows are related to time. In particular, the average amount of time taken by each of the x _tj flow units along arc a _tj is defined as t _ij ,(x _ij ). Sometimes, t _ij ,(x _ij ) is referred to as delay function. Typically, t _ij ,(x _ij ) is assumed to be increasing at an increasing rate, i.e., \( \frac{{d{t_{ij}}\left( {{x_{ij}}} \right)}}{{d{x_{ij}}}} > 0 \) and \( \frac{{{d^2}{t_{ij}}\left( {{x_{ij}}} \right)}}{{dx_{ij}^2}} > 0 \) . Obvious applications of network flow problems with delay functions are those involving road traffic, and telecommunication networks. Delay functions in road networks are frequently of the type \( {t_{ij}}\left( {{x_{ij}}} \right) = t_{ij}^0\left[ {1 + \alpha {{\left( {{x_{ij}}/{K_{ij}}} \right)}^\beta }} \right] \) with a capacity K _ij a transmission time under light traffic t _ij ⁰ , and constants a and β; a value of β = 4 is typical in practical applications. In telecommunication networks, we frequently encounter delay functions of the type \( {t_{ij}}\left( {{x_{ij}}} \right) = t_{ij}^0{K_{ij}}/\left( {{K_{ij}} - {x_{ij}}} \right) \) which can be derived from M/M/1 queues, given random arrivals and message lengths that follow a negative exponential distribution.