nach oben

2012 | Buch

Kapitel lesen Erstes Kapitel lesen

Deterministic Global Optimization

Geometric Branch-and-bound Methods and their Applications

verfasst von: Daniel Scholz

Verlag: Springer New York

Buchreihe : Springer Optimization and Its Applications

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This monograph deals with a general class of solution approaches in deterministic global optimization, namely the geometric branch-and-bound methods which are popular algorithms, for instance, in Lipschitzian optimization, d.c. programming, and interval analysis.It also introduces a new concept for the rate of convergence and analyzes several bounding operations reported in the literature, from the theoretical as well as from the empirical point of view. Furthermore, extensions of the prototype algorithm for multicriteria global optimization problems as well as mixed combinatorial optimization problems are considered. Numerical examples based on facility location problems support the theory. Applications of geometric branch-and-bound methods, namely the circle detection problem in image processing, the integrated scheduling and location makespan problem, and the median line location problem in the three-dimensional space are also presented.

The book is intended for both researchers and students in the areas of mathematics, operations research, engineering, and computer science.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Principles and basic concepts

Abstract

In this chapter, our main goal is to summarize principles and basic concepts that are of fundamental importance in the remainder of this text, especially in Chapter 3 where bounding operations are presented.We begin with the definition of convex functions and some generalizations of convexity in Section 1.1. Some fundamental but important results are given before we discuss subgradients. Next, in Section 1.2 we briefly introduce distance measures given by norms. Distance measures are quite important in the subsequent Section 1.3 where we give a very brief introduction to location theory. Furthermore, we show how to solve theWeber problem for the rectilinear and Euclidean norms. Moreover, d.c. functions are introduced in Section 1.4 and basic properties are collected. Finally, we give an introduction to interval analysis in Section 1.5 which leads to several bounding operations later on.

Daniel Scholz

Chapter 2. The geometric branch-and-bound algorithm

Abstract

The aim of this chapter is the presentation of the fundamental geometric branch-and-bound algorithm including a general convergence theory. To this end, we start with a literature review of these approaches and their applications to facility location problems in Section 2.1. Next, we give some notations and formally define bounding operations in Section 2.2 before the geometric branch-and-bound prototype algorithm is presented and discussed in Section 2.3. The main contribution of the present chapter can be found in Sections 2.4 and 2.5. Therein, we define the rate of convergence and results about the termination of the algorithm are given. Note that parts of these sections have been published in Schöbel and Scholz (2010b).

Daniel Scholz

Chapter 3. Bounding operations

Abstract

In the previous chapter, the geometric branch-and-bound prototype algorithm was formulated and discussed. However, the most important choice for fast branch-and-bound algorithms is good bounding operations; see Example 2.2. Therefore, several bounding operations are derived in this chapter; see Sections 3.1 to 3.9, and for all bounding operations we prove the theoretical rate of convergence as defined in Section 2.4. Apart from our theoretical results, all findings are justified by numerical experiments in Section 3.10. We remark that almost all results collected in this chapter can be found in Sch¨obel and Scholz (2010b) and Scholz (2011b).

Daniel Scholz

Chapter 4. Extension for multicriteria problems

Abstract

In this chapter, our goal is to generalize the geometric branch-and-bound algorithm to multicriteria optimization problems. To this end, after a short introduction in Section 4.1 we summarize the fundamental definitions and results about multicriteria optimization in Section 4.2. We remark that most of the results in the following sections can also be found in Scholz (2010). However, we introduce the concept of multicriteria bounding operations in Section 4.3 which has not been used therein. Next, in Section 4.4 we prove the convergence of the proposed algorithm as well as properties of the output set. The method is demonstrated on bicriteria facility location problems in Section 4.5 and some numerical results are given in Section 4.6.

Daniel Scholz

Chapter 5. Multicriteria discarding tests

Abstract

Under the assumption that the objective functions for a multicriteria optimization problem are differentiable, this chapter presents some general discarding tests that can be used throughout the algorithm presented in the previous chapter. The idea of these discarding tests is to obtain a sharp outer approximation of the set of Pareto optimal solutions. To this end, we recall the well-known Fritz John necessary conditions for Pareto optimality in Section 5.1 before the multicriteria discarding tests are presented in Section 5.2. The theoretical results are again illustrated on two bicriteria location problems introduced in Section 5.3. Some particular instances for these problems are solved in Section 5.4 twice, one time without multicriteria discarding tests and one time using these tests. We show that the second run yields a very sharp outer approximation of the set of all Pareto optimal solutions compared to the first run.

Daniel Scholz

Chapter 6. Extension for mixed combinatorial problems

Abstract

All techniques presented in the previous chapters are dealing with pure continuous objective functions, therefore we now extend the geometric branch-andbound algorithm to mixed continuous and combinatorial optimization problems.We are not only taking continuous variables into account but also some combinatorial variables. The extended algorithm is suggested in Section 6.1 and the rate of convergence again leads to a general convergence theory as shown in Section 6.2. Next, in Section 6.3 we derive some mixed bounding operations using techniques already discussed in Chapter 3 for pure continuous problems. Moreover, we show in Section 6.4 how to find exact optimal solutions under certain conditions which is demonstrated on some facility location problems in Section 6.5. Finally, we conclude the chapter with some numerical results in Section 6.6.

Daniel Scholz

Chapter 7. The circle detection problem

Abstract

In the previous chapters we discussed the theory of geometric branch-andbound methods and several extensions were given. In this chapter, we now present an application of the suggested techniques. To be more precise, we show how global optimization can be used in image processing to detect imperfect instances of shapes such as lines, circles, or ellipses. We introduce the problem in Section 7.1 and some useful notations are collected in Section 7.2. Before the general problem can be formulated, we have to detect edges in images. To this end, Canny’s edge detection algorithm is briefly summarized in Section 7.3. Next, we can formulate the detection problem as a global optimization problem in Section 7.4. In the following, we also discuss the circle detection problem in detail. Some lower bounds are suggested in Section 7.5 before Section 7.6 illustrates the proposed circle detection problem on several examples.

Daniel Scholz

Chapter 8. Integrated scheduling and location problems

Abstract

As a second application of geometric branch-and-bound methods we present an integrated scheduling and location problem, namely the ScheLoc makespan problem. ScheLoc problems are location problems where we want to find an optimal location as well as an optimal schedule in an integrated model. Therefore, geometric branch-and-bound methods with mixed continuous and combinatorial variables are appropriate solution techniques for ScheLoc problems. In Section 8.1, we give a short introduction to ScheLoc problems before the ScheLoc makespan problem is presented explicitly in Section 8.2. In the following Sections 8.3 and 8.4, we show how to calculate lower bounds on the objective function as well as finite dominating sets for the combinatorial variables as required throughout the algorithm if we want to find an exact optimal solution. Some numerical experiences with comparisons to results reported in the literature are given in Section 8.5 before the chapter ends with a brief discussion in Section 8.6.

Daniel Scholz

Chapter 9. The median line problem

Abstract

As the last application considered in this text, we treat a facility location problem where we want to find an optimal location for a straight line. To be more precise, we want to locate a line in such a way that the sum of distances between that line and some given demand points is minimized. Although this problem is easy to solve in two dimensions, things become much more complicated in the threedimensional case. Therefore, our aim is to apply the geometric branch-and-bound solution algorithm to the median line problem in the three-dimensional Euclidean space. To this end, after a short introduction and a literature review in Section 9.1, some theoretical results as well as a suitable problem formulation are given in Section 9.2. Furthermore, some bounding operations are suggested in Section 9.3 and numerical results can be found in Section 9.4.

Daniel Scholz

Chapter 10. Summary and discussion

Abstract

We conclude this book with a summary of the previous chapters, a discussion of the presented algorithms and techniques, and an outlook on further research as well as possible extensions. We start with the summary in Section 10.1 before a discussion of the suggested methods in Section 10.2. Finally, the work ends with an overview of further research ideas in Section 10.3.

Daniel Scholz

Backmatter

Titel: Deterministic Global Optimization
verfasst von: Daniel Scholz
Verlag: Springer New York
Electronic ISBN: 978-1-4614-1951-8
Print ISBN: 978-1-4614-1950-1
DOI: https://doi.org/10.1007/978-1-4614-1951-8