Search

This book addresses complex real-world problems with recent techniques. It comprises selected papers from the XX. congress APDIO held in Tomar, Portugal, in July 2019. The subject of the book is the application of operational research methodologies and techniques to address complex real problems. Readers will find interesting results and applications of operational research methods and techniques in the wide variety of the addressed problems. Of particular interest are the applications of, among others, linear, nonlinear and mixed-integer programing, multiobjective optimization, metaheuristics and hybrid heuristics, multicriteria decision analysis, data envelopment analysis, clustering techniques and decision support systems, in different areas such as supply chain management, scheduling problems, production management, logistics, energy, telecommunications and finance and health. In most chapters of the book, the described problems, methods and methodologies will be illustrated by auxiliary figures and tables, as well as algorithms. The main benefit of this book is to present the latest trends in operational research methods and methodologies by top Portuguese and international researchers. The book will present a wide scope of complex real-world applications addressed by recent theoretical techniques that aim to narrow the gap between academic researchers and practitioners.

In recent years global optimization has found applications in many interesting areas of science and technology including molecular biology, chemical equilibrium problems, medical imaging and networks. The collection of papers in this book indicates the diverse applicability of global optimization. Furthermore, various algorithmic, theoretical developments and computational studies are presented. Audience: All researchers and students working in mathematical programming.

The connected dominating set has been a classic subject studied in graph theory since 1975. Since the 1990s, it has been found to have important applications in communication networks, especially in wireless networks, as a virtual backbone. Motivated from those applications, many papers have been published in the literature during last 15 years. Now, the connected dominating set has become a hot research topic in computer science. In this book, we are going to collect recent developments on the connected dominating set, which presents the state of the art in the study of connected dominating sets. The book consists of 16 chapters. Except the 1st one, each chapter is devoted to one problem, and consists of three parts, motivation and overview, problem complexity analysis, and approximation algorithm designs, which will lead the reader to see clearly about the background, formulation, existing important research results, and open problems. Therefore, this would be a very valuable reference book for researchers in computer science and operations research, especially in areas of theoretical computer science, computer communication networks, combinatorial optimization, and discrete mathematics.

Written by an experienced operations research practitioner with a strong applied mathematics background, this book offers practical insights into how to approach optimization problems, how to develop intelligent and efficient mathematical models and algorithms, and how to implement and deliver software products to customers. With a focus on revealing the similarities and differences between academia and industry in mathematical modeling, the book provides useful tips and advice based on the author's extensive experience as a principal developer working to solve real-world optimization problems for several major high-tech companies.The book offers valuable food for thought for researchers and practical guidance for graduate students preparing for their future projects in the industry. It is also an essential resource for practitioners working in the industrial, business, and service sectors.

Interior Point Methods for Linear Optimization is a comprehensive, thorough textbook on interior point methods (IPMs). The era of IPMs was initiated by N. Karmarkar's 1984 paper, which triggered turbulent research and reshaped almost all areas of optimization theory and computational practice. This book gives a comprehensive review of the main results of more than a decade of IPM research. Numerous exercises are provided to aid in understanding the material.

This book introduces the fundamentals of probability, statistical, and reliability concepts, the classical methods of uncertainty quantification and analytical reliability analysis, and the state-of-the-art approaches of design optimization under uncertainty (e.g., reliability-based design optimization and robust design optimization). The topics include basic concepts of probability and distributions, uncertainty quantification using probabilistic methods, classical reliability analysis methods, time-variant reliability analysis methods, fundamentals of deterministic design optimization, reliability-based design optimization, robust design optimization, other methods of design optimization under uncertainty, and engineering applications of design optimization under uncertainty.

This textbook presents a wide range of tools for a course in mathematical optimization for upper undergraduate and graduate students in mathematics, engineering, computer science, and other applied sciences. Basic optimization principles are presented with emphasis on gradient-based numerical optimization strategies and algorithms for solving both smooth and noisy discontinuous optimization problems. Attention is also paid to the difficulties of expense of function evaluations and the existence of multiple minima that often unnecessarily inhibit the use of gradient-based methods. This second edition addresses further advancements of gradient-only optimization strategies to handle discontinuities in objective functions. New chapters discuss the construction of surrogate models as well as new gradient-only solution strategies and numerical optimization using Python. A special Python module is electronically available (via springerlink) that makes the new algorithms featured in the text easily accessible and directly applicable. Numerical examples and exercises are included to encourage senior- to graduate-level students to plan, execute, and reflect on numerical investigations. By gaining a deep understanding of the conceptual material presented, students, scientists, and engineers will be able to develop systematic and scientific numerical investigative skills.

This work reviews the most important results regarding the use of the α-point in Scheduling Theory. It provides a number of different LP-relaxations for scheduling problems and seeks to explain their polyhedral consequences. It also explains the concept of the α-point and how the conversion algorithm works, pointing out the relations to the sum of the weighted completion times. Lastly, the book explores the latest techniques used for many scheduling problems with different constraints, such as release dates, precedences, and parallel machines. This reference book is intended for advanced undergraduate and postgraduate students who are interested in scheduling theory. It is also inspiring for researchers wanting to learn about sophisticated techniques and open problems of the field.

Sebastian Goderbauer zeigt, dass das Einteilen von Wahlkreisen für die Deutsche Bundestagswahl aufgrund der gesetzlichen Vorgaben als ein mathematisches Optimierungsproblem angesehen werden kann. Er gibt eine detaillierte Komplexitätsanalyse des zugrundeliegenden Partitionsproblems an und untersucht, welches die beste Wahlkreisanzahl für Deutschland ist. Der Autor entwickelt einen optimierungsbasierten Algorithmus zum Einteilen von Wahlkreisen und wendet diesen auf deutsche Bevölkerungsdaten an.

People are facing more and more NP-complete or NP-hard problems of a combinatorial nature and of a continuous nature in economic, military and management practice. There are two ways in which one can enhance the efficiency of searching for the solutions of these problems. The first is to improve the speed and memory capacity of hardware. We all have witnessed the computer industry's amazing achievements with hardware and software developments over the last twenty years. On one hand many computers, bought only a few years ago, are being sent to elementary schools for children to learn the ABC's of computing. On the other hand, with economic, scientific and military developments, it seems that the increase of intricacy and the size of newly arising problems have no end. We all realize then that the second way, to design good algorithms, will definitely compensate for the hardware limitations in the case of complicated problems. It is the collective and parallel computation property of artificial neural net­ works that has activated the enthusiasm of researchers in the field of computer science and applied mathematics. It is hard to say that artificial neural networks are solvers of the above-mentioned dilemma, but at least they throw some new light on the difficulties we face. We not only anticipate that there will be neural computers with intelligence but we also believe that the research results of artificial neural networks might lead to new algorithms on von Neumann's computers.

Global optimization is concerned with the computation and characterization of global optima of nonlinear functions. During the past three decades the field of global optimization has been growing at a rapid pace, and the number of publications on all aspects of global optimization has been increasing steadily. Many applications, as well as new theoretical, algorithmic, and computational contributions have resulted. The Handbook of Global Optimization is the first comprehensive book to cover recent developments in global optimization. Each contribution in the Handbook is essentially expository in nature, but scholarly in its treatment. The chapters cover optimality conditions, complexity results, concave minimization, DC programming, general quadratic programming, nonlinear complementarity, minimax problems, multiplicative programming, Lipschitz optimization, fractional programming, network problems, trajectory methods, homotopy methods, interval methods, and stochastic approaches. The Handbook of Global Optimization is addressed to researchers in mathematical programming, as well as all scientists who use optimization methods to model and solve problems.

Computing has become essential for the modeling, analysis, and optimization of systems. This book is devoted to algorithms, computational analysis, and decision models. The chapters are organized in two parts: optimization models of decisions and models of pricing and equilibria.

Since I started working in the area of nonlinear programming and, later on, variational inequality problems, I have frequently been surprised to find that many algorithms, however scattered in numerous journals, monographs and books, and described rather differently, are closely related to each other. This book is meant to help the reader understand and relate algorithms to each other in some intuitive fashion, and represents, in this respect, a consolidation of the field. The framework of algorithms presented in this book is called Cost Approxi­ mation. (The preface of the Ph.D. thesis [Pat93d] explains the background to the work that lead to the thesis, and ultimately to this book.) It describes, for a given formulation of a variational inequality or nonlinear programming problem, an algorithm by means of approximating mappings and problems, a principle for the update of the iteration points, and a merit function which guides and monitors the convergence of the algorithm. One purpose of this book is to offer this framework as an intuitively appeal­ ing tool for describing an algorithm. One of the advantages of the framework, or any reasonable framework for that matter, is that two algorithms may be easily related and compared through its use. This framework is particular in that it covers a vast number of methods, while still being fairly detailed; the level of abstraction is in fact the same as that of the original problem statement.

This book deals with decision making in environments of significant data un­ certainty, with particular emphasis on operations and production management applications. For such environments, we suggest the use of the robustness ap­ proach to decision making, which assumes inadequate knowledge of the decision maker about the random state of nature and develops a decision that hedges against the worst contingency that may arise. The main motivating factors for a decision maker to use the robustness approach are: • It does not ignore uncertainty and takes a proactive step in response to the fact that forecasted values of uncertain parameters will not occur in most environments; • It applies to decisions of unique, non-repetitive nature, which are common in many fast and dynamically changing environments; • It accounts for the risk averse nature of decision makers; and • It recognizes that even though decision environments are fraught with data uncertainties, decisions are evaluated ex post with the realized data. For all of the above reasons, robust decisions are dear to the heart of opera­ tional decision makers. This book takes a giant first step in presenting decision support tools and solution methods for generating robust decisions in a variety of interesting application environments. Robust Discrete Optimization is a comprehensive mathematical programming framework for robust decision making.

Just as in its 1st edition, this book starts with illustrations of the ubiquitous character of optimization, and describes numerical algorithms in a tutorial way. It covers fundamental algorithms as well as more specialized and advanced topics for unconstrained and constrained problems. Most of the algorithms are explained in a detailed manner, allowing straightforward implementation. Theoretical aspects of the approaches chosen are also addressed with care, often using minimal assumptions. This new edition contains computational exercises in the form of case studies which help understanding optimization methods beyond their theoretical, description, when coming to actual implementation. Besides, the nonsmooth optimization part has been substantially reorganized and expanded.

This book presents models and algorithms for complex scheduling problems. Besides resource-constrained project scheduling problems with applications also job-shop problems with flexible machines, transportation or limited buffers are discussed. Discrete optimization methods like linear and integer programming, constraint propagation techniques, shortest path and network flow algorithms, branch-and-bound methods, local search and genetic algorithms, and dynamic programming are presented. They are used in exact or heuristic procedures to solve the introduced complex scheduling problems. Furthermore, methods for calculating lower bounds are described. Most algorithms are formulated in detail and illustrated with examples. In this second edition some errors were corrected, some parts were explained in more detail, and new material has been added. In particular, further generalizations of the RCPSP, additional practical applications and some more algorithms were integrated.

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.

The theory of Vector Optimization is developed by a systematic usage of infimum and supremum. In order to get existence and appropriate properties of the infimum, the image space of the vector optimization problem is embedded into a larger space, which is a subset of the power set, in fact, the space of self-infimal sets. Based on this idea we establish solution concepts, existence and duality results and algorithms for the linear case. The main advantage of this approach is the high degree of analogy to corresponding results of Scalar Optimization. The concepts and results are used to explain and to improve practically relevant algorithms for linear vector optimization problems.

This up-to-date book is on algorithms for large-scale unconstrained and bound constrained optimization. Optimization techniques are shown from a conjugate gradient algorithm perspective. Large part of the book is devoted to preconditioned conjugate gradient algorithms. In particular memoryless and limited memory quasi-Newton algorithms are presented and numerically compared to standard conjugate gradient algorithms. The special attention is paid to the methods of shortest residuals developed by the author. Several effective optimization techniques based on these methods are presented. Because of the emphasis on practical methods, as well as rigorous mathematical treatment of their convergence analysis, the book is aimed at a wide audience. It can be used by researches in optimization, graduate students in operations research, engineering, mathematics and computer science. Practitioners can benefit from numerous numerical comparisons of professional optimization codes discussed in the book.

Manufacturing systems work with scarce resources in dynamic environments. Managers need to assign production facilities to parallel activities, respecting operational constraints and deadlines while keeping costs low. Old scheduling approaches are inadequate when a task both requires a set of different resources and a trade-off between objectives. More sophisticated models and algorithms are needed by these managers. This book provides robust methods for achieving effective resource allocation. It also solves problems such as resource levelling, sizing of machines and production layouts, cost optimization in production planning and scheduling that occur daily and often generate cost overruns. The quantitative methods used cover both mathematical programming and algorithms, leading to high quality solutions. Details of experimentation put these techniques in a practical perspective. This book is a valuable resource for postgraduate students and researchers in business, engineering or computer science.

It is intended that this book be used in senior- to graduate-level semester courses in optimization, as offered in mathematics, engineering, com­ puter science and operations research departments. Hopefully this book will also be useful to practising professionals in the workplace. The contents of the book represent the fundamental optimization mate­ rial collected and used by the author, over a period of more than twenty years, in teaching Practical Mathematical Optimization to undergradu­ ate as well as graduate engineering and science students at the University of Pretoria. The principal motivation for writing this work has not been the teaching of mathematics per se, but to equip students with the nec­ essary fundamental optimization theory and algorithms, so as to enable them to solve practical problems in their own particular principal fields of interest, be it physics, chemistry, engineering design or business eco­ nomics. The particular approach adopted here follows from the author's own personal experiences in doing research in solid-state physics and in mechanical engineering design, where he was constantly confronted by problems that can most easily and directly be solved via the judicious use of mathematical optimization techniques. This book is, however, not a collection of case studies restricted to the above-mentioned specialized research areas, but is intended to convey the basic optimization princi­ ples and algorithms to a general audience in such a way that, hopefully, the application to their own practical areas of interest will be relatively simple and straightforward.

In 1995 the Handbook of Global Optimization (first volume), edited by R. Horst, and P.M. Pardalos, was published. This second volume of the Handbook of Global Optimization is comprised of chapters dealing with modern approaches to global optimization, including different types of heuristics. Topics covered in the handbook include various metaheuristics, such as simulated annealing, genetic algorithms, neural networks, taboo search, shake-and-bake methods, and deformation methods. In addition, the book contains chapters on new exact stochastic and deterministic approaches to continuous and mixed-integer global optimization, such as stochastic adaptive search, two-phase methods, branch-and-bound methods with new relaxation and branching strategies, algorithms based on local optimization, and dynamical search. Finally, the book contains chapters on experimental analysis of algorithms and software, test problems, and applications.

Although this may seem a paradox, all exact science is dominated by the idea of approximation. Bertrand Russell (1872-1970) Most natural optimization problems, including those arising in important application areas, are NP-hard. Therefore, under the widely believed con­ jecture that P -=/= NP, their exact solution is prohibitively time consuming. Charting the landscape of approximability of these problems, via polynomial time algorithms, therefore becomes a compelling subject of scientific inquiry in computer science and mathematics. This book presents the theory of ap­ proximation algorithms as it stands today. It is reasonable to expect the picture to change with time. This book is divided into three parts. In Part I we cover combinato­ rial algorithms for a number of important problems, using a wide variety of algorithm design techniques. The latter may give Part I a non-cohesive appearance. However, this is to be expected - nature is very rich, and we cannot expect a few tricks to help solve the diverse collection of NP-hard problems. Indeed, in this part, we have purposely refrained from tightly cat­ egorizing algorithmic techniques so as not to trivialize matters. Instead, we have attempted to capture, as accurately as possible, the individual character of each problem, and point out connections between problems and algorithms for solving them.