Skip to main content
main-content

Über dieses Buch

Location, scheduling and design problems are assignment type problems with quadratic cost functions and occur in many contexts stretching from spatial economics via plant and office layout planning to VLSI design and similar prob­ lems in high-technology production settings. The presence of nonlinear inter­ action terms in the objective function makes these, otherwise simple, problems NP hard. In the first two chapters of this monograph we provide a survey of models of this type and give a common framework for them as Boolean quadratic problems with special ordered sets (BQPSs). Special ordered sets associated with these BQPSs are of equal cardinality and either are disjoint as in clique partitioning problems, graph partitioning problems, class-room scheduling problems, operations-scheduling problems, multi-processor assign­ ment problems and VLSI circuit layout design problems or have intersections with well defined joins as in asymmetric and symmetric Koopmans-Beckmann problems and quadratic assignment problems. Applications of these problems abound in diverse disciplines, such as anthropology, archeology, architecture, chemistry, computer science, economics, electronics, ergonomics, marketing, operations management, political science, statistical physics, zoology, etc. We then give a survey of the traditional solution approaches to BQPSs. It is an unfortunate fact that even after years of investigation into these problems, the state of algorithmic development is nowhere close to solving large-scale real­ life problems exactly. In the main part of this book we follow the polyhedral approach to combinatorial problem solving because of the dramatic algorith­ mic successes of researchers who have pursued this approach.

Inhaltsverzeichnis

Frontmatter

1. Location Problems

Abstract
This monograph analyzes various classes of Boolean quadratic problems with special ordered set constraints (BQPSs) in order to develop a practical approach to solving these problems. The BQPS provides a framework of mathematical abstraction for a variety of scheduling, design and assignment problems with a combination of linear assignment and quadratic interaction cost, not necessarily nonnegative, that arise in a wide variety of real-life contexts. We start with a detailed discussion of quadratic assignment problems which appear to have their roots in three separate spheres of scientific interest — in spatial economics which has a long history of its own, see e.g. Weber [1909], and in industrial engineering and computer science, both of which are comparatively young disciplines.
Manfred Padberg, Minendra P. Rijal

2. Scheduling and Design Problems

Abstract
In addition to location problems, a truly amazing variety of scheduling and design problems has been formulated by numerous professionals in industrial engineering, management science, computer science and the social sciences as Boolean quadratic problems with special ordered set constraints (BQPSs). These include notorious problems such as the traveling salesman problem and seemingly innocuous, but NP-hard optimization problems such as the unconstrained quadratic zero-one optimization problem. In this chapter we collect a representative number of these problems with the aim of classifying them into a schema that will permit us to detect commonalities and differences for further in-depth study of the essential problem classes. Right from the outset, we wish, however, to make clear that we do not advocate the exclusive treatment of every zero-one optimization problem that fits into our framework within the classes of BQPSs that we consider. Additional structural properties of a combinatorial optimization problem — if present — must be exploited fully in order to achieve numerical success and while we subscribe to the often heard maxim “...as global as possible, as local as necessary ...”, we do it with the right amount of caution.
Manfred Padberg, Minendra P. Rijal

3. Solution Approaches

Abstract
The quadratic assignment problem (QAP) has attracted a surpassing algorithmic research interest since its introduction in 1957 by Koopmans and Beckmann. A wide variety of algorithms and heuristics have been developed to solve the QAP exactly or approximately. Moreover, since all the problems described in Chapter 2 are closely related to the QAP, one could modify the available exact and approximate techniques for the QAP and utilize them to “solve” every one of these problems. While this is conceptually correct, we do not recommend to solve e.g. traveling salesman problems this way, because the largest size QAP solved to optimality, so far, has n = 30; see Clausen [1994], Mans et al. [1992], Pardalos et al. [1994], and Resende et al. [1994]. More to the point, this means that existing algorithms for QAPs are nowhere close to solving practical problems arising from real-life applications to optimality. This state of affairs is unsatisfactory, but not surprising since very little is known about the mathematical properties of QAPs. A straight-forward application of the appropriately modified QAP algorithms to solve its variants can thus not be expected to solve large-scale instances of these problems. While many authors propose (different) mixed zero-one formulations of QAPs, they are hardly exploited in the numerical computations and the facial structure of the associated integer polyhedra has not been studied in any detail.
Manfred Padberg, Minendra P. Rijal

4. Locally Ideal LP Formulations I

Abstract
In this chapter and the next one we discuss linear programming (LP) formulations of the scheduling, design and assignment problems described in Chapters 1 and 2 as classes of BQPSs (Boolean quadratic problems with specially structured special ordered set (SOS) constraints). A formulation of a combinatorial optimization problem is any system of equations and/or inequalities the integer, mixed-integer, zero-one or mixed zero-one solutions of which are in one-to-one correspondence with the “feasible” configurations or objects over which we wish to optimize. In most cases of practical interest many, seemingly different formulations of a combinatorial optimization problem exist if it can be formulated at all in this sense. The LP formulations of the BQPSs that we derive in this chapter are based on the concept of a “locally ideal” linearization. A locally ideal linearization is a linearization that yields an ideal, i.e., minimal and complete, linear description of the polytope corresponding to each pair or certain sets of pairs of variables in the quadratic interaction terms of the objective function; see Padberg [1995] for a complete treatment of polyhedral/polytopal theory and any definitions that we leave unexplained in this monograph. In a way, using the concept of local idealization to formulate BQPSs is analogous to investigating thoroughly a few threads of a cobweb as a starting point for a full-fledged study of the entire cobweb.
Manfred Padberg, Minendra P. Rijal

5. Locally Ideal LP Formulations II

Abstract
In this chapter we continue our investigations into the locally ideal linearization of the major problem classes from Chapters 1 and 2. In particular, we study here the VLSI circuit layout design problem, a general model that comprises all BQPSs considered so far, the quadratic assignment problem and its symmetric relative. Except for the symmetric quadratic assignment problem, complete characterizations of the associated local polytopes are obtained. Like in the case of our results of Chapter 4, these local polytopes are of interest on their own whenever the substructures that we study occur in a quadratic zero-one optimization problem. In all cases we obtain from the locally ideal linearization formulations of the respective problems that in most cases improve on existing formulations for these problems.
Manfred Padberg, Minendra P. Rijal

6. Quadratic Scheduling Problems

Abstract
As noted in Chapter 4.2, the operations scheduling problem (OSP) with machine independent quadratic interaction costs is identical with the graph partitioning problem (GPP). We compare in this chapter these alternative formulations for the OSP in this special case. By comparing the two formulations we do not mean an empirical comparison, but rather an analytical comparison such as the one carried out by Padberg and Sung [1991] for four different formulations of the traveling salesman problem. This guarantees that our results have validity for any numerical calculations based on the formulations that we propose in Chapters 4.2 and 4.3. In the second half of this chapter we derive some results on the facial structure of the OSP.
Manfred Padberg, Minendra P. Rijal

7. Quadratic Assignment Polytopes

Abstract
In this chapter we present various results and partial results on the facial structure of the quadratic assignment polytope QAP n and its symmetric relative, the polytope SQP n . We address primarily the questions of finding the affine hull and the dimension of the respective polytopes, but give also some valid inequalities for QAP n . Some of these problems are left open and suggested in the form of conjectures for future work on this difficult, but interesting class of combinatorial optimization problems.
Manfred Padberg, Minendra P. Rijal

8. Solving Small QAPs

Abstract
Psychologically it is, of course, disadvantageous to start the last chapter with a disclaimer, but this is exactly what we are going to do. The software system that we are going to describe here is of a preliminary nature and our computational results should by no means be interpreted as limiting the potential of branch-and-cut algorithms for the solution of quadratic assignment and related quadratic zero-one optimization problems. The software system came about from our desire to write an interesting introductory chapter for this monograph dealing with the fascinating world of location, scheduling and design problems -see Chapters 1.3, 1.4 and 1.5. As an afterthought came then the idea to test the software system on a somewhat larger sample of the problems from QAPLIB. In spite of our reservations we have included this material in the book because it seems to fill a gap in the literature on how to solve quadratic assignment problems. Our efforts in locating suitable references notwithstanding and despite the fact that every author that we have read on quadratic assignment calls the problem a (mixed) zero-one programming problem, nobody seems to have taken the pain to solve QAPs via a standard mixed integer programming code using ordinary branch-and-bound. The development effort that is necessary to actually write such a software system for QAP is minimal — it took one of the authors about seven days of intense programming work to “string it all together and get the job done.”
Manfred Padberg, Minendra P. Rijal

Backmatter

Weitere Informationen