Handbook of Combinatorial Optimization

The use of networks allows the representation of a variety of important engineering problems. The treatment of a particular class of network applications, the process synthesis problem, is exposed in this paper. Process Synthesis seeks to develop systematically process flowsheets that convert raw materials into desired products. In recent years, the optimization approach to process synthesis has shown promise in tackling this challenge. It requires the development of a network of interconnected units, the process superstructure, that represents the alternative process flowsheets. The mathematical modeling of the superstructure has a mixed set of binary and continuous variables and results in a Mixed-Integer optimization model. Due to the nonlinearity of chemical models, these problems are generally classified as Mixed-Integer Nonlinear Programming (MINLP) problems.A number of local optimization algorithms, developed for the solution of this class of problems, are presented in this paper: Generalized Benders Decomposition (GBD), Outer Approximation (OA), Generalized Cross Decomposition (GCD), Branch and Bound (BB), Extended Cutting Plane (ECP), and Feasibility Approach (FA). Some recent developments for the global optimization of nonconvex MINLPs are then introduced. In particular, two branch-and-bound approaches are dis-cussed:the Special structure Mixed Integer Nonlinear αBB (SMIN-αBB), where the binary variables should participate linearly or in mixed-bilinear terms, and the General structure Mixed Integer Nonlinear αBB (GMIN- αBB), where the continuous relaxation of the binary variables must lead to a twice-differentiable problem. Both algorithms are based on the αBB global optimization algorithm for nonconvex continuous problems.Once the theoretical issues behind local and global optimization algorithms for MINLPs have been exposed, attention is directed to their algorithmic development and implementation. The framework MINOPT is discussed as a computational tool for the solution of process synthesis problems. It is an implementation of a number of local optimization algorithms for the solution of MINLPs. The use of MINOPT is illustrated through the solution of a variety of process network problems. The synthesis problem for a heat exchanger network is then presented to demonstrate the global optimization SMIN-αBB algorithm.

In the Maximum Satisfiability (MAX-SAT) problem one is given a Boolean formula in conjunctive normal form, i.e., as a conjunction of clauses, each clause being a disjunction. The task is to find an assignment of truth values to the variables that satisfies the maximum number of clauses.

Given a set X,a function f: X→ℝ and a subset S of X–we consider the problem: 1$$\min f(x)s.t.x \in S$$Problem (1) is usually called a combinatorial optimization problem when S is finite and a discrete optimization problem when the points of S are isolated in some topology, i.e., every point of S has a neighbourhood which does not contain other points of S. Obviously, all combinatorial optimization problems are also discrete optimization problems but the converse is not true. A simple example is the problem of minimizing a function on the set of integer points contained in an unbounded polyhedron.

Interior-point methods, originally invented in the context of linear programming, have found a much broader range of applications, including discrete problems that arise in computer science and operations research as well as continuous computational problems arising in the natural sciences and engineering. This chapter describes the conceptual basis and applications of interior-point methods for discrete problems in computing.

Knapsack Problems are the simplest NP-hard problems in Combinatorial Optimization, as they maximize an objective function subject to a single resource constraint. Several variants of the classical 0–1 Knapsack Problem will be considered with respect to relaxations, bounds, reductions and other algorithmic techniques for the exact solution. Computational results are presented to compare the actual performance of the most effective algorithms published.

An instance of a fractional combinatorial optimization problem F consists of a specification of a set $$\chi\subseteq{\left\{{0,1}\right\}^p}$$, and two functions f : χ → R and g : χ → R. The task is to $$F:maximize\frac{{f(x)}}{{g(x)}},forx \in X$$

Discrete and continuous nonconvex programming problems arise in a host of practical applications in the context of production, location-allocation, distribution, economics and game theory, process design, and engineering design situations. Several recent advances have been made in the development of branch-and-cut algorithms for discrete optimization problems and in polyhedral outer-approximation methods for continuous nonconvex programming problems. At the heart of these approaches is a sequence of linear programming problems that drive the solution process. The success of such algorithms is strongly tied in with the strength or tightness of the linear programming representations employed.

Recently, application of the theory of Gröbner bases to integer programming has given rise to new tools and results in this field. Here we present this algebraic theory as the natural integer analog of the simplex approach to linear programming Although couched in algebra, the theory of Gröbner bases and its consequences for integer programming are intimately intertwined with polyhedral geometry and lattice arithmetic which are staples of the traditional approach to this subject.

Set covering, set packing and set partitioning models are a special class of linear integer programs. These models and their variants have been used to formulate a variety of practical problems in such areas as capital budgeting, crew scheduling, cutting stock, facilities location, graphs and networks, manufacturing, personnel scheduling, vehicle routing and timetable scheduling among others. Based on the special structure of these models, efficient computational techniques have been developed to solve large size problems making it possible to solve many real world applications. This paper is a survey of the applications of the set covering, set packing, set partitioning models and their variants, including generalizations.

Computing shortest paths in a geometric environment is a fundamental topic in computational geometry and finds applications in many other areas. The problem of processing geometric shortest path queries is concerned with constructing an efficient data structure for quickly answering on-line queries for shortest paths connecting any two query points in a geometric setting. This problem is a generalization of the well-studied problem of computing a geometric shortest path connecting only two specified points. This paper covers the newly-developed algorithmic paradigms for processing geometric shortest path queries and related problems. These general paradigms have led to efficient techniques for designing algorithms and data structures for processing a variety of queries on exact and approximate shortest paths in a number of geometric and graphical settings. Some open problems and promising directions for future research are also discussed.

Comparing objects to find their similarities or, equivalently, dissimilarities, is a fundamental issue in many fields including pattern recognition, image analysis, drug design, the study of thermodynamic costs of computing, cognitive science, etc. Various models have been introduced to measure the degree of similarity or dissimilarity in the literature. In the latter case the degree of dissimilarity is also often referred to as the distance. While some distances are straightforward to compute, e.g. the Hamming distance for binary strings, the Euclidean distance for geometric objects; some others are formulated as combinatorial optimization problems and thus pose nontrivial challenging algorithmic problems, sometimes even uncomputable, such as the universal information distance between two objects [4].

Studies on games in coalition form deal with the power of cooperation among its participants. In this sense it is often referred to as cooperative game theory. In a simple mathematical formulation, we have a set N of agents, and a value function υ : 2N → R where, for each subset S ⊆ N, , υ (S) represents the value obtained by the coalition of agents of the subset S without assistance of other agents, with υ(ø) = 0. Individual income can be represented by a vector x : N → R. We consider games with side payments. The main issue here is how to fairly distribute the income collectively earned by a group of cooperating participants in the game. For simplicity, we write x(S) = Σ _i∈S x _i . A vector x is called an imputation if x(N) = υ(N), and ∀i∈ N : x _i ≥ υ({i}) (individual rationality).

Minimizing a network’s length is one of the oldest optimization problems in mathematics and, consequently, it has been worked on by many of the leading mathematicians in history. In the mid-seventeenth century a simple problem was posed: Find the point P that minimizes the sum of the distances from P to each of three given points in the plane. Solutions to this problem were derived independently by Fermat, Torricelli, and Cavaliers. They all deduced that either P is inside the triangle formed by the given points and that the angles at P formed by the lines joining P to the three points are all 120°, or P is one of the three vertices and the angle at P formed by the lines joining P to the other two points is greater than or equal to 120°.

The resource allocation problem seeks to find an optimal allocation of a fixed amount of resources to activities so as to minimize the cost incurred by the allocation. A simplest form of the problem is to minimize a separable convex function under a single constraint concerning the total amount of resources to be allocated. The amount of resources to be allocated to each activity is treated as a continuous or integer variable, depending on the cases. This can be viewed as a special case of the nonlinear programming problem or the nonlinear integer programming problem.

Clustering is a mathematical technique designed for revealing classification structures in the data collected on real-world phenomena. A cluster is a piece of data (usually, a subset of the objects considered, or a subset of the variables, or both) consisting of the entities which are much “alike”, in terms of the data, versus the other part of the data. The term itself was coined in psychology back in thirties when a heuristical technique was suggested for clustering psychological variables based on pair-wise coefficients of correlation. However, two more disciplines also should be credited for the outburst of clustering occurred in the sixties: numerical taxonomy in biology and pattern recognition in machine learning. Among relevant sources are Hartigan (1975), Jain and Dubes (1988), Mirkin (1996). Simultaneously, industrial and computational applications gave rise to graph partitioning problems which are touched below in 6.2.4.

In this chapter G = (V,E) denotes an arbitrary undirected graph without loops, where V = {v₁, v₂,…, v _n } is its vertex set and E = {e₁,e₂,…, e _m } ⊂ (E ×E) is its edge set. Two edges are adjacent if they connect to a common vertex. Two vertices v _i and v _j are adjacent if there is an edge e = (v _i ,v _j ) ∈ E. Finally, if e = (v _i ,v _j ) ∈ E,we say e is incident to vertices v _i , v _j .

Let’s say that you are going to design a new electronic circuit at the molecular/atomic level where you know beforehand the basic number of atomic elements of the circuit and you wish to arrange them so that they achieve an optimal configuration that is both compact, stable, and integrated electrically. How would you configure the atoms? If one assumes that the cost of putting together the molecular structure is proportional to distance i.e. the potential energy in the system, then you would want to minimize the overall interconnecting distance between the atoms. This is fundamentally the Steiner problem in E3. Figure 1 demonstrates a geometric construction for the Steiner Minimal Tree of N=6 vertices in E3.

This article describes and compares several dynamical system approaches to combinatorial optimization problems. These include penalty methods, the approach of Hopfield and Tank, self-organizing maps, i.e., Kohonen networks, coupled selection equations, and hybrid methods. Many of them are investigated analytically and the costs of the solutions are compared numerically with those of solutions obtained by simulated annealing and the costs of a global optimal solution. In order to get reproducible simulation results, a pseudo-random number generator with integer arithmetic is used to produce the data sets.Using dynamical systems, a solution to the combinatorial optimization problem emerges in the limit of large times as an asymptotically stable point of the dynamics. These are often not global optimal solutions but good approximations of it. Dynamical system and neural network approaches are appropriate methods for distributed and parallel processing. Because of the parallelization, these techniques are able to compute a given task much faster than algorithms which are using a traditional sequentially working digital computer.The analysis focuses on the linear two-dimensional (two-index) assignment problem and the NP-hard three-dimensional (three-index) assignment problem. These and other assignment problems can be used as models for many industrial problems like manufacturing planning and optimization of flexible manufacturing systems (FMS).

A dominating set of a graph G = (V, E) is a subset V’ of V such that for each vertex u ∈ V — V’ there is a vertex v ∈ V’ so that (u, v) ∈ E. The minimum dominating set problem is to find a set V’ of minimum cardinality, which is denoted by ø(G). It is well known that the minimum dominating set problem is NP-complete [9]. In this paper we consider on-line dominating set problems for general and permutation (simple) graphs.

The huge potential of optical networks for satisfying the skyrocketing needs of broadband telecommunication services while meeting rigid quality of service requirements has long been acknowledged. However, although fiber has become the medium of choice in telecommunication networks, its vast resources are severely under-used, due to the much slower electronics that are interfaced with the optical medium. For instance, transceivers operate at speeds that are several orders of magnitude below the actual usable capacity of the fiber (several Gbps versus hundreds of Gbps). In order to achieve higher rates, Wavelength Division Multiplexing (WDM) techniques have been widely suggested. The concept behind WDM is to partition the optical spectrum into multiple non-overlapping wavelength channels, each modulated at electronic speed. WDM networks offer potential advantages, including higher aggregate bandwidth per fiber, new flexibility for automated network management and control, noise immunity, transparency to different data formats and protocols, low bit-error rates, and better network configurability and survivability-all leading to more cost-effective networks.

Suppose A = {a_l, a₂, ... , a _n } is a point set in a metric space M. The shortest network problem asks for a minimum length network S(A) that interconnects all points of A (called terminals), possibly with some additional points to shorten the network. S(A) must be a tree since it cannot contain any cycle for minimality. In the literature this problem is called the Steiner tree problem, and S(A) is called a Steiner minimal tree for A [9]. If no additional points are added, then the network, denoted by T(A), is called a minimal spanning tree on A. Sometimes these networks are simply denoted by S and T if no confusion is caused.

A triangulation of a given set S of n points in the plane is a maximal set of non-crossing line segments (called edges) which have both endpoints in S. A triangulation partitions the interior of the convex hull of the given point set into triangles. It is used in many areas of engineering and scientific applications such as finite element methods, approximation theory, numerical computation, computer-aided geometric design, and etc.

The quality of an airline’s product is measured by its timeliness, accuracy, functionality, quality, and price. For the air transportation customers, these criteria translate into flexible schedules, on-time flights, safety, satisfactory in-flight services, proper baggage handling, reasonable prices, and convenient ticket purchases To provide this high-quality, low-cost product, airlines rely on optimization-based decision support systems to generate profitable and cost-effective fare classes, flight schedules, fleet plans, aircraft routes, crew pairings, gate assignments, maintenance schedules, food service plans, training schedules, and baggage handling procedures.

Given the symmetric matrix $$Q = \left\{ {qij} \right\} \in {R^{n \times n}}$$ and the constraint matrix $$A = \left\{ {{a_{ij}}} \right\} \in {R^{m \times n}}$$, we consider the quadratic programming (QP) problem with linear and boolean constraintsQP$$\begin{array}{l} Maximize q\left( x \right): = x'Qx\\ subject to \left| {\sum\limits_{j = 1}^n {{a_{ij}}{x_j}} } \right| = {b_i} = 1,...,m,\\ x_j^2 = 1,j = 1,...,n. \end{array}$$ Note that the constraint x _j 2=1 will force x _j = 1 or x _j = −1, making it a boolean variable.

The scheduling of computer and manufacturing systems has been the subject of extensive research for over forty years. In addition to computers and manufacturing, scheduling theory can be applied to many areas including agriculture, hospitals and transport. The main focus is on the efficient allocation of one or more resources to activities over time. Adopting manufacturing terminology, a job consists of one or more activities, and a machine is a resource that can perform at most one activity at a time. We concentrate on deterministic machine scheduling for which it is assumed that all data that define a problem instance are known with certainty.

The need of high speed networks, for applications incorporating high performance distributed computing, multimedia communication and real time network services, has provided the impetus for the study of optical networks. Wavelength Division Multiplexing (WDM) has been used widely for studying the throughput performance of optical networks. We studied WDM lightwave networks with tunable transceivers including designs for lightwave networks with limited tuning ranges for transceivers.

The quadratic assignment problem (QAP) was introduced by Koopmans and Beckmann in 1957 as a mathematical model for the location of a set of indivisible economical activities [113]. Consider the problem of allocating a set of facilities to a set of locations, with the cost being a function of the distance and flow between the facilities, plus costs associated with a facility being placed at a certain location. The objective is to assign each facility to a location such that the total cost is minimized. Specifically, we are given three n x n input matrices with real elements F = (f _ij ), D = (d _kl ) and B = (b _ik ), where f _ij is the flow between the facility i and facility j, d _kl is the distance between the location k and location l, and b _ik is the cost of placing facility i at location k. The Koopmans-Beckmann version of the QAP can be formulated as follows: Let n be the number of facilities and locations and denote by N the set N = {1, 2,..., n}.

Graph theory was founded by Euler [78] in 1736 as a generalization to the solution of the famous problem of the Könisberg bridges. From 1736 to 1936, the same concept as graph, but under different names, was used in various scientific fields as models of real world problems, see the historic book by Biggs, Lloyd and Wilson [19]. This chapter intents to survey the domination problem in graph theory, which is a natural model for many location problems in operations research, from an algorithmic point of view.

The use of parallel algorithms for solving computationally hard problems becomes attractive as parallel systems, consisting of a collection of powerful processors, offer large computing power and memory storage capacity. Even though parallelism will not be able to overdue the assumed worst case exponential time or memory complexity of those problems (unless an exponential number of processors is used) [11], the average execution time of heuristic search algorithms which find good suboptimal solutions for many hard problems is polynomial. Consequently, parallel systems, possibly with hundreds or thousands of processors, give us the perspective of efficiently solving relatively large instances of hard problems.

Search problems are ubiquitous. The search process is an adaptive process of cumulative performance selection. The structure of a given problem and the environment impose constraints. With the given constraints, a search process transforms a given problem from an initial state to a solution state.

Let the vertices of a graph G be colored with k colors such that no adjacent vertices receive the same color and the sizes of the color classes differ by at most one. Then G is said to be equitably k-colorable. The equitable chromatic number x₌ (G) is the smallest integer k such that G is equitably k-colorable. In this article, we survey recent progress on the equitable coloring of graphs. We pay more attention to work done on the Equitable ∆-Coloring Conjecture. We also discuss related graph coloring notions and their problems. The survey ends with suggestions for further research topics.

In this paper we show some important randomization techniques for the parallel processing of discrete problems. In particular, we present several parallel randomized algorithms frequently used for sorting, packet routing, shortest paths problems, matching problems, depth first search, minimum cost spanning trees, and maximal independent set problems. We also discuss the connection between randomization and approximation, showing how randomization yields approximate solutions and we illustrate this connection by means of network flow problems.

Faced with the challenge of solving hard optimization problems that abound in the real world, classical methods often encounter great difficulty. Vitally important applications in business, engineering, economics and science cannot be tackled with any reasonable hope of success, within practical time horizons, by solution methods that have been the predominant focus of academic research throughout the past three decades (and which are still the focus of many textbooks).