Skip to main content
main-content

## Über dieses Buch

There have been significant developments in the theory and practice of combinatorial optimization in the last 15 years. This progress has been evidenced by a continuously increasing number of international and local conferences, books and papers in this area. This book is also another contribution to this burgeoning area of operations research and optimization. This volume contains the contributions of the participants of the recent NATO Ad­ vanced Study Institute, New Frontiers in the Theory and Practice of Combinatorial Op­ timization, which was held at the campus of Bilkent University, in Ankara, Turkey, July 16-29, 1990. In this conference, we brought many prominent researchers and young and promising scientists together to discuss current and future trends in the theory and prac­ tice of combinatorial optimization. The Bilkent campus was an excellent environment for such an undertaking. Being outside of Ankara, the capital of Turkey, Bilkent University gave the participants a great opportunity for exchanging ideas and discussing new theories and applications without much distraction. One of the primary goals of NATO ASIs is to bring together a group of scientists and research scientists primarily from the NATO countries for the dissemination of ad­ vanced scientific knowledge and the promotion of international contacts among scientists. We believe that we accomplished this mission very successfully by bringing together 15 prominent lecturers and 45 promising young scientists from 12 countries, in a university environment for 14 days of intense lectures, presentations and discussions.

## Inhaltsverzeichnis

### Variable Decomposition, Constraint Decomposition and Cross Decomposition in General Mathematical Programming

Decomposition has been recognized as a fundamental technique in optimization ever since the seminal papers of Benders (1962) and Dantzig & Wolfe (1960). The literature abounds with theoretical extensions of these two basic approaches, as well as with reports of successful applications (for references, see Flippo (1991)). In this paper, Variable and Constraint Decomposition will be introduced as proper generalizations of Benders Decomposition and Dantzig-Wolfe Decomposition respectively. Under fairly mild conditions, these methods can be prevented from exhibiting cyclic behavior, and under much stronger conditions, they can be proven to converge asymptotically or even finitely. Special attention will be paid to Cross Decomposition, which is intermediate between the two decomposition methods mentioned above. A number of convergence criteria will be shown to prevent the procedure from cycling, or even to enforce asymptotic or finite convergence.

Olaf E. Flippo, Alexander H. G. Rinnooy Kan

### Surrogate Constraint Methods for Linear Inequalities

Systems of linear inequalities and equations are very important in optimization. Recent applications of mathematical programming in areas such as computerized tomography (CAT scan) lead to very large and sparse systems of linear equations and inequalities which need to be solved approximately within reasonable time. Traditional Phase I linear programming approaches are not appropriate for these problems because of the very large size of the systems and irregular sparsity structure. Iterative relaxation methods can be used to solve these problems, but they tend to be too slow.We developed new iterative methods based on the generation of a surrogate constraint from the violated inequalities in each step. These methods have nice convergence properties and are amenable to both sequential and highly parallel implementations. Computational experience with these methods is very encouraging.

Kai Yang, Katta G. Murty

### An Evaluation of Algorithmic Refinements and Proper Data Structures for the Preflow-Push Approach for Maximum Flow

Following the milestone paper by Goldberg on the preflow-push algorithm for solving maximum flow problems on networks, quite a number of refinements have been suggested in literature which reduce the computational complexity of this approach. One of these streams is based on ”scaling”.In this paper we shortly review some recently published scaling approaches, and we develop an appropriate data structure by which an efficient storage and use of the additional information on feasible subnetworks etc. is possible. Finally, we report extensive computational results.

U. Derigs, W. Meier

### A Cutting Plane Algorithm for the Single Machine Scheduling Problem with Release Times

We propose a mixed integer programming formulation for the single machine scheduling problem with release times and the objective of minimizing the weighted sum of the start times. The basic formulation involves start time and sequence determining variables, and lower bounds on the start times. Its linear programming relaxation solves problems in which all release times are equal. For the general problem, good lower bounds are obtained by adding additional valid inequalities that are violated by the solution to the linear programming relaxation. We report computational results and suggest some modifications based on including additional variables that are likely to give even better results.

G. L. Nemhauser, M. W. P. Savelsbergh

### The Linear Assignment Problem

We present a broad survey of recent polynomial algorithms for the linear assignment problem. They all use essentially alternating trees and/or strongly feasible trees. Most of them employ Dijkstra’s shortest path algorithm directly or indirectly. When properly implemented, each has the same complexity: O(n3) for dense graphs with simple data structures and O(n2 log n + nm) for sparse graphs using Fibonacci Heaps.

Mustafa Akgül

### Cost Allocation In The Oil Industry: An Example

We consider the problem of allocating the costs among the potential users of a gas processing system. The cost allocation problem is solved using cooperative game theory. We show how the cost allocation problem can be solved when the characteristic function is given implicitely as the solution of a mathematical programming problem.

Kurt O. Jørnsten

### On Preference Orders for Sequencing Problems Or, What Hath Smith Wrought?

When in 1956 W. E. Smith proposed the ratio rule for solving the unconstrained weighted completion time problem, he suggested an abstraction in the form of a preference order. Over the years, the concept of a preference order has been much elaborated. It is now applied to abstract problems in optimal sequencing, with general precedence constraints being dealt with by the technique of modular decomposition. This paper provides a unified and self contained exposition of these results, with some new material on the treatment of contiguity constraints.

E. L. Lawler

### Dynamic Basis Partitioning for Network Flows with Side Constraints

This paper deals with the network flow modeling of emergency evacuation problems in densely populated buildings or geographical areas. The underlying optimization model is a dynamic network flow model with side constraints. We propose a new dynamic basis partitioning procedure for the primal partitioning simplex algorithm. The proposed algorithm is used in solving very large size network flow problems with many side constraints. Our experimental results show that the proposed dynamic basis partitioning algorithm is up to 36 times more efficient than a regular basis partitioning algorithm on the problems encountered in solving emergency evacuation problems.

Wonjoon Choi, Süleyman Tüfekçi

### Combinatorial Optimization Models Motivated by Robotic Assembly Problems

In this paper some results are summarized which were motivated by modeling the assembly of printed circuit boards using robots. First we consider an iterative traveling salesman — location model for sequencing the insertion points and locating the storage bins. The restricted location problem used in this model is generalized and some algorithms for solving this general problem are described. Finally, we discuss max-linear combinatorial optimization problems as models for multi objective problems.Emphasis will be on results obtained by the author in cooperation with various collaborators. It is not intended to give a complete overview on the literature in this area.

Horst W. Hamacher

### Job Shop Scheduling

The job shop scheduling problem is described as follows. Given are a set of jobs and a set of machines. Each machine can handle at most one job at a time. Each job consists of a chain of operations, each of which needs to be processed during an uninterrupted time period of a given length on a given machine. The purpose is to find a schedule, i.e., an allocation of the operations to time intervals on the machines, that has minimum length.

J. K. Lenstra

### On the Construction of the Set of K-best Matchings and Their Use in Solving Constrained Matching Problems

For constructing the set of K-best solutions for a combinatorial optimization problem so-called partitioning schemes have been developed in literature which require the iterative solution of the basic optimization problem over a restricted groundset, i.e. a restricted set of variables. In this paper we discuss the application of these schemes to the problem of finding the set of K-best perfect matchings in a graph. We show that the use of those features which make the basic shortest augmenting path matching algorithm efficient, like the assignment start-procedure, are essential to also reduce the computational effort for the K-best procedure.Constructing the set of K-best matchings has been used recently in an approach for solving matching problems with side-constraints. Here we show how the K-best strategy can be customized for this special purpose.

U. Derigs, A. Metz

### Solving Large Scale Multicommodity Networks Using Linear—Quadratic Penalty Functions

In this report we summarize current research towards the development of an algorithm for the solution of very large multicommodity network flow problems (MCNFP). The algorithm combines linear—quadratic penalty forms with a linearization technique that takes advantage of the block structure of the constraint set. The resultant procedure solves a sequence of smaller problems and can also be executed in parallel. Complete papers discuss the algorithm, Zenios, Pinar and Dembo [1990], and its parallel implementation, Pinar and Zenios [1990]. We consider the multicommodity network flow problem (MCNFP) with the following structure: commodities flow over a network such that the aggregate flow on each arc does not exceed some joint capacity. Let $$\mathcal{G} = \{ \mathcal{V},\varepsilon \}$$ be a graph with a set of vertices $$\mathcal{V} = \langle m\rangle$$ (where the notation $$\langle \operatorname{m} \rangle$$ represents the set {1, 2,..., m}) and a set of edges $$\varepsilon= \{ (i,j)|i,j \in \mathcal{V}\}$$, where $$\left| \varepsilon \right| = \operatorname{n}$$. Let $$\langle K\rangle$$ be the set of commodities flowing on $$\mathcal{G}$$. We will use the notation $$v'$$ to denote the transpose of a vector or matrix $$\upsilon$$.

Mustafa Ç Pinar, Stavros A. Zenios

### An Analysis of the Minimal Spanning Tree Structure

In this paper the minimal spanning tree (MST) structure is analyzed by means of the distance random variable and Wroclaw Taxonomy algorithm [2].

Elzbieta Trybus

### Genetic Algorithms: A New Approach to the Timetable Problem

In this paper we present the results of a research relative to the ascertainment of limits and potentials of genetic algorithms [4, 3, 6] in addressing highly constrained optimization problems, where a minimal change to a feasible solution is very likely to yield an infeasible one. As a test problem, we have chosen the timetable problem (TTP), a problem that is known to be NP-hard [5], which has been intensively investigated for its practical relevance [2, 1]

Alberto Colorni, Marco Dorigo, Vittorio Maniezzo

### A New Approximation Technique for Hypergraph Partitioning Problem

The partitioning of the nodes of a hypergraph arises in many different design/layout applications. In particular, the netlist partitioning problem in VLSI design, c.f. [2, 5, 9], can be represented as a hypergraph partitioning problem. The modules in the netlist correspond to nodes of the hypergraph and the nets correspond to the hyperedges.

Scott W. Hadley

### Optimal Location of Concentrators in a Centralized Teleprocessing Network

Centralized networks with a tree structure generally arise in the context of the design of local access networks, which are linked to a large distributed network at gateway backbone nodes. In some cases, however, even large-scale networks are centralized systems. The terminals are linked together in groups sharing a multidrop line and connected to the host computer or to the backbone switch through a concentrator. By assuming that the terminals are identical in terms of the amount of data flow they may generate, line and concentrator capacities may then be expressed as the maximum number of terminals they can accommodate. The problem to solve consists of determining the optimal number and location of the concentrators and of linking the facilities in tree hierarchical structure at minimum cost, without exceeding line and concentrator capacities.

M. G. de Oliveira

### A Column Generation Algorithm for the Vehicle Routing Problem with Time Windows

Let G = (N, A) be a network where A is the set of arcs or route segments and N is the set of nodes or customers. Associated with each arc (i,j) ∈ A there is a cost c ij , and a duration t ij . We assume that the service time of customer i is included in the duration of each arc (i, j). In this paper, the cost is taken to be the distance between i and j. The vehicle routing problem with time windows (VRPTW) involves the design of a set of minimum cost routes originating and terminating at a central depot, d, for a fleet of vehicles which services a set of customers with known demands q i . Each customer is serviced exactly once. The service of a customer, involving pick-up (delivery) of goods or services, can begin at T i within the time window defined by the earliest time, a i , and the latest time, b i , when the customer will permit the start of service. If a vehicle arrives at a customer too early, it will wait. In addition, due dates cannot be violated. Furthermore, all the customers must be assigned to vehicles such that the vehicle capacities, Q, are not exceeded.

Martin Desrochers, Jacques Desrosiers, Marius Solomon

### The Linear Complementary Problem, Sufficient Matrices and the Criss-Cross Method

Linear Complementarity Problems (LCP) will be considered in this paper. Let us start with fixing our notations. Let q be an n-dimensional vector, M be an n × n square matrix. The pair (q,M) defines the LCP as follows: 1$$- Mz + w = q,z \geqslant 0,w \geqslant 0,{z^T}w = 0.$$ Variables w i and z i for i = 1,...,n are called complementary variables. The coefficient in row i and column j of matrix M will be denoted by m ij . The solvability of LCP depends on the special properties of the coefficient matrix M.

D. den Hertog, C. Roos, T. Terlaky

### A Characterization of Lifted-Cover Facets of Knapsack Polytope with GUB Constraints

Facet-defining inequalities lifted from minimal covers are used as strong cutting planes in algorithms for solving 0–1 integer programming problems. We extend the results of Balas [1] and Balas and Zemel [2] by giving a set of inequalities that determines the lifting coefficients of facet-defining inequalities for any ordering of the variables to be lifted. We further extend these results to obtain facet-defining inequalities for the 0–1 knapsack problem with mutually exclusive generalized upper bound (GUB) constraints.

George L. Nemhauser, Gabriele Sigismondi, Pamela Vance

### On Pleasant Knapsack Problems

In this paper the following knapsack problems will be considered 1$$\max (\min )\{ \sum\nolimits_{j = 1}^n {cjx} j:\sum\nolimits_{j = 1}^n {ajxj} = b,x \in z_ + ^n\}$$ The maximization problem is MAXKP and the other one is MINKP. The constraints are formally the same. We assume that the following regularity conditions are satisfied.

Béla Vizvári

### Extensions of Efficient Exact Solution Procedures to Bicriterion Optimization

There exists a wide variety of decision making situations in which trading off one objective against another is involved, such as time versus cost. Bicriterion mathematical programming has been successfully applied in such situations. Examples of such works include nutrition planning, portfolio analysis, resource allocation, transportation and assignment problems, project scheduling, production planning, etc. In this paper an interactive algorithm is given for a bicriterion problem in the most general sense, namely, the bicriterion nonconvex mixed integer programming problem that maximizes two objective functions over a compact nonempty set.

Yasemin Aksoy

### Combinatorial Aspects in Single Junction Control Optimization

In recent years the evaluation by mathematical programming techniques of optimal values for junction control variables (green timing, green scheduling and cycle time) has been carried out by various methods. These methods adopt as possible objectives of opti­mization: the capacity factor maximization (linear); the total rate of delay minimization (non linear but convex or linear using piecewise linearization of delay functions); the cycle time minimization (linear).

Giuseppe Bruno, Gennaro Improta

### Approximation Algorithms for Constrained Scheduling

In this paper we consider several constrained machine scheduling problems. The first model consists of n jobs and m identical machines that operate in parallel. Each job j has a processing time pj and must be processed without interruption for time pj on any one of the m machines. In addition, each job j has a release date rj, when it becomes available for processing, and a delivery time qj. Each job’s delivery begins immediately after its processing has been completed, and all jobs may be delivered simultaneously. A schedule consists of a set of starting times σ1,..., σn with σj≥rj, j = 1,...,n, and an assignment of jobs to machines so that each machine processes at most one job at a time. For a given schedule, we define Cj:= σj + pj+ qj to be the completion time of job j,and the object of the problem is to minimize, over all possible schedules, Cmax:= max j Cj. The problem as stated is equivalent to that with release dates and due dates, dj, rather than delivery times, in which case the objective is to minimize the maximum lateness,Lj:= σj + pj+ dj, of any job j. When considering the performance of approximation algorithms, the delivery-time model is preferable (see [6, 4]). Because of this equivalence, we shall denote the problem as P|rj|Lmax, using the notation of Graham et al. [1]. The special case of a single machine is denoted 1|rj|Lmax.

Leslie A. Hall, David B. Shmoys

### An Analogue of Hoffman’s Circulation Conditions for Max-Balanced Flows

Let G = (V, A) be a directed graph. A real-valued vector x defined on the arc set A is a max-balanced flow for G if for every cut W the maximum weight over arcs leaving W equals the maximum weight over arcs entering W. This instance of algebraic flows, which have been studied by Hamacher [2] in the more general setting of regular matroids, was re-introduced by Schneider and Schneider [3] under the name max-balanced graphs. For vectors l ≤ u defined on A, an analogue of Hoffman’s circulation conditions holds for max-balanced flows: There exists a max-balanced flow x satisfying l ≤ x ≤ u if and only if maxa∈δ-(W)l a ≤ maxa∈δ-(W)l a u a for all 0⊂W⊂V. Both of these are equivalent to the existence of an (l, u) cycle cover for G, which is a collection of directed circuits Ca: a ∈ A such that a∈C a and u e ≥l a for all e ∈ Ca. Analogous results are shown to hold for algebraic flows in oriented regular matroids in [2], where the cutsets +δ+(W) and δ−(W) are replaced by the positive and negative parts D+ and D− of the cocircuits D of the oriented regular matroid and a directed circuit is any circuit C with C = C+. In the case of max-balanced flows, these characterizations can easily be shown to hold for any oriented matroid using an extension of Minty’s painting lemma [1, Proposition 3.4]. We give a simple graph-theoretic proof for directed graphs, which yields other equivalent conditions that point to a relationship between max-balanced graphs and bottleneck paths.

Mark Hartmann, Michael H. Schneider

### Some Telecommunications Network Design Problems and the Bi-Steiner Problem

We present two network design problems arising in telecommunications. First we discuss the subscriber network extensions problem which consists in designing a telephone network connecting certain subscribers to some switching point. Next we mention a similar problem in the design of cable television networks. Finally we briefly discuss the bi-Steiner problem, which is a generalization of the Steiner problem in directed graphs in which directed two-connectedness to each terminal node is required.

Geir Dahl

### Parallel Machine Scheduling to Minimize Costs for Earliness and Number of Tardy Jobs

We discuss the problem of scheduling a set N of n independent jobs on m parallel machines to minimize costs for earliness, due date assignment and weighted number of tardy jobs. We restrict the due dates to the common due date case and distinguish between two different models, namely an externally given common due date or an adjustable common due date. The latter model usually includes due date assignment costs since moderate due dates represent a high level of service quality. An extensive survey of scheduling research involving the due date assignment decision has been conducted by Cheng & Gupta[2], and a survey of scheduling research involving both due date models has been written by Baker & Scudder[1].

H. G. Kahlbacher, T. C. E. Cheng

### Exact Solution of Multiple Traveling Salesman Problems

This paper presents a method developed for the multiple traveling salesman problem (m-TSP), which is a generalization of the well known TSP [6]. In the m-TSP, there are m salesmen who are required to visit n customers in such a way that all customers are visited exactly once by exactly one of the salesmen. Hence, each salesman leaves from and returns to the same point, the depot, and each one of them completes a tour visiting a subset of the customers.

J. Gromicho, J. Paixão, I. Bronco

### A Nonlinear Two-Stage Cutting Stock Problem

In this communication, we present a two-stage cutting stock system that arises in a make-to-order steel industry. Orders are accepted on a monthly basis, and planning and production must be completed within a month. Client specifications include weight, width, thickness, hardness, etc. According to the characteristics, the orders are split into different groups of raw materials. For each final product there is a well-defined sequence of operations.

J. M. Valério de Carvalho, A. J. Guimarães Rodrigues

### The Probabilistic Behavior of the Generalized HARMONIC Algorithm for the On-Line Multi-Dimensional Bin Packing

In the classical one-dimensional bin-packing problem, we are given a list of numbers (items) in the interval (0,1], which must be packed into a minimum number of unit-capacity bins (i.e. bins that can contain items totalling at most 1). It is well known that this problem is NP-hard, and accordingly a number of approximations have been developed for its solution. These algorithms can be analysed from the worst-case and the probabilistic points of view. One such algorithm is the HARMONIC r algorithm. In this case the items are classified into r categories, according to how many items of the same size may be packed into a bin. The r-th, i.e. the last category will contain all the items which are less than or equal to 1/r. This algorithm is efficient from both points of view, and it has the further important advantage that it is an O(n)-time and O(1)-space online algorithm. The worst-case behaviour of this algorithm was analysed in [3], and some improvements are given in [4] and [5]. The probabilistic analysis of the one-dimensional case was performed in [1] and [2].

J. Csirik, E. Máté

### Efficient Labelling Algorithms for the Maximum Noncrossing Matching Problem

Consider a bipartite graph G = (O, D, E) where O and D are origin and destination node sets respectively (O = D = n), and E is a set of edges (i, j), i ∈ O and j ∈ D(E=m). Suppose we draw the origin nodes and the destination nodes arranged in two columns and the edges as straight line segments between origins and destinations. A noncrossing matching is a subset of edges M ⊑ E such that no two edges of M intersect (including intersections at nodes). The Maximum Non Crossing Matching (MNCM) is the problem of finding the noncrossing matching of maximum cardinality. Let p denote the cardinality of the MNCM. Problems arising in several fields can be modelled as MNCM: for example the 3-Side Switch Box in VLSI design has been presented in [2] where an O(n2) time algorithm is proposed. The problem can be reduced to the one of finding the longest increasing subsequence in a permutation of size m [1]. An algorithm for this problem has been proposed by Fredman and slightly improved by Widmayer and Wong[7]; in our case the algorithm complexity is O(m + (m - p) log (p). In this paper some labeling algorithms for the MNCM, which work directly on the bipartite graph, will be proposed. The overall complexity is improved to O(m log log n) or to O(m + minnp, (m - p) log p). Finally the weighted case is considered.

Federico Malucelli, Daniele Pretolani

### A Phase I That Solves Transportation Problems

Recently, a number of exterior point simplex algorithms for assignment problems have been developed [1, 2, 6, 7]. Preliminary computational results on assignment problems [2] indicate that the algorithms are efficient in practice. These algorithms are initialized with a dual feasible basis. Then dual feasibility is destroyed to be restored again at optimality.

Konstantinos Paparrizos

### A Polynomially Bounded Dual Simplex Algorithm for Capacitated Minimum Cost Flow Problem

In this paper, we present a dual simplex algorithm for solving the capacitated minimum cost flow problem.

Canan A. Sepil, Ayşegül Altaban

### Formulation and a Lagrangean Relaxation Procedure for Solving Part Scheduling and Tool Loading Problems in FMS

The growth of the metal-working industry spawned improvements in computer integrated manufacturing technology. One result of such improvements was the development of Flexible Manufacturing Systems (FMS). A Flexible Manufacturing System typically consists of versatile numerically controlled machines, connected by an automated material handling system, all under a central computer control. The FMS’s achieve the enviable results of effectively combining the efficiency of transfer lines and flexibility of job shops by eliminating or reducing set-up or change over times between manufacturing operations. Although FMS’s can offer a wide variety of benefits, the flexibility of these systems has resulted in making the design and subsequent operation of FMS’s very complex.

Kannan Sethuraman, Marshall L. Fisher, Alexander H. G. Rinnooy Kan

### Euclidean Steiner Minimal Trees with Obstacles and Steiner Visibility Graphs

Suppose that we are given a set Z = z1, z2,..., z p of terminals in the plane together with a set of disjoint polygonal obstacles Ω = wl, w2,...,w k The Euclidean Steiner tree problem with obstacles (ESTPO) is to determine the shortest network spanning Z while avoiding all obstacles. Such a network is called the obstacle-avoiding Euclidean Steiner minimal tree (ESMTO).

Pawel Winter

### A Set Covering Formulation of the Matrix Equipartition Problem

This paper is concerned with a certain NP-hard matrix decomposition problem (Matrix Equipartition). Given a (0, 1)-matrix M with a row set R, Matrix Equipartition consists of finding two equicardinality subsets R1 and R2 of R with maximum size such that every row of R1 is disjoint from every row of R2. Call R3 the set of the remaining rows.

S. Nicoloso, P. Nobili

### Maximizing a Submodular Function by Integer Programming: A Polyhedral Approach

Let N = {1, 2,..., n} be a finite set. A real-valued function f whose domain is all of the subsets of N is said to be submodular if $$f\left( S \right) + f\left( T \right) \geqslant f\left( {S \cup T} \right) + f\left( {S \cap T} \right)for all S,T$$.The problem of maximizing a submodular function includes many NP-hard combinatorial optimization problems, for example the max-cut problem, the uncapacitated facility location problem and some network design problems. Thus, this research is motivated by the opportunity of providing a unified approach to many NP-hard combinatorial optimization problems whose underlying structure is submodular.

Heesang Lee, George L. Nemhauser

### New Bounds for the Asymmetric Traveling Salesman Problem

Recently new techniques for producing lower bounds have appeared in the literature: bound improvement sequences [1, 2, 3] and Lagrangean decomposition [6, 5].

A. I. Barros, P. Bárcia

### A Lagrangean Heuristic for Set Covering Problems

The set covering problem (SCP) is the problem of covering the rows of a m row, n column, zero-one matrix by a subset of the columns at minimum cost.

J. E. Beasley

### Backmatter

Weitere Informationen