Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2000 | Buch

Multi-Start and Strategic Oscillation Methods — Principles to Exploit Adaptive Memory Kapitel lesen Erstes Kapitel lesen

Computing Tools for Modeling, Optimization and Simulation

Interfaces in Computer Science and Operations Research

herausgegeben von: Manuel Laguna, José Luis González Velarde

Verlag: Springer US

Buchreihe : Operations Research/Computer Science Interfaces Series

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Computing Tools for Modeling, Optimization and Simulation reflects the need for preserving the marriage between operations research and computing in order to create more efficient and powerful software tools in the years ahead. The 17 papers included in this volume were carefully selected to cover a wide range of topics related to the interface between operations research and computer science. The volume includes the now perennial applications of rnetaheuristics (such as genetic algorithms, scatter search, and tabu search) as well as research on global optimization, knowledge management, software rnaintainability and object-oriented modeling. These topics reflect the complexity and variety of the problems that current and future software tools must be capable of tackling. The OR/CS interface is frequently at the core of successful applications and the development of new methodologies, making the research in this book a relevant reference in the future.
The editors' goal for this book has been to increase the interest in the interface of computer science and operations research. Both researchers and practitioners will benefit from this book. The tutorial papers may spark the interest of practitioners for developing and applying new techniques to complex problems. In addition, the book includes papers that explore new angles of well-established methods for problems in the area of nonlinear optimization and mixed integer programming, which seasoned researchers in these fields may find fascinating.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Multi-Start and Strategic Oscillation Methods — Principles to Exploit Adaptive Memory
A Tutorial on Unexplored Opportunities
Abstract
We propose approaches for creating improved forms of constructive multi-start and strategic oscillation methods, based on the search principles of persistent attractiveness and marginal conditional validity. These approaches embody adaptive memory processes by drawing on combinations of recency and frequency information, which can be monitored to encompass varying ranges of the search history. In addition, we propose designs for investigating these approaches empirically, and indicate how a neglected but important kind of memory called conditional exclusion memory can be implemented within the context of these methods.
Fred Glover
Chapter 2. Building a High-quality Decision Tree with a Genetic Algorithm
A Computational Study
Abstract
In dealing with a very large data set, it might be impractical to construct a decision tree using all of the points. To overcome this impracticality, subsets of the original data set can be extracted, a tree can be constructed on each subset, and then parts of individual trees can be combined in a smart way to produce a final set of feasible trees. In this paper, we take trees generated by a commercial decision tree package and allow them to crossover and mutate (using a genetic algorithm) in order to generate trees of better quality. We conduct a computational study of our approach using a real-life marketing data set and find that our approach produces uniformly high-quality decision trees.
Zhiwei Fu, Bruce L. Golden, Shreevardhan Lele, S. Raghavan, Edward A. Wasil
Chapter 3. Sequential Testing of Series-Parallel Systems of Small Depth
Abstract
We consider the problem of testing sequentially the components of a multi-component system, when testing the components is costly. We consider a polynomial time testing policy for series-parallel systems, and prove, generalising earlier results that it is cost-minimal in the average case sense, for two sub-families of series-parallel systems. We also demonstrate via examples that neither this algorithm nor some of its improved versions are optimal for general series-parallel systems, disproving some published claims.
Endre Boros, Tonguc Unluyurt
Chapter 4. Conveying Problem Structure from an Algebraic Modeling Language to Optimization Algorithms
Abstract
Optimization algorithms can exploit problem structures of various kinds, such as sparsity of derivatives, complementarity conditions, block structure, stochasticity, priorities for discrete variables, and information about piecewise-linear terms. Moreover, some algorithms deduce additional structural information that may help the modeler. We review and discuss some ways of conveying structure, with examples from our designs for the AMPL modeling language. We show in particular how “declared suffixes” provide a new and useful way to express structure and acquire solution information.
Robert Fourer, David M. Gay
Chapter 5. Solving General Ring Network Design Problems by Meta-Heuristics
Abstract
Ring network design problems have many important applications, especially in the field of telecommunications and vehicle routing. Those problems generally consist of constructing a ring network by selecting a node subset and corresponding direct links. Different requirements and objectives lead to various specific types of NP-hard ring network design problems reported in the literature, each with its own algorithms. We exploit the similarities in problems to produce a more general problem formulation and associated solution methods that apply to a broad range of problems. Computational results are reported for an implementation using a meta-heuristics framework with generic components for heuristic search.
Andreas Fink, Gabriele Schneidereit, Stefan Voß
Chapter 6. Lagrangean/Surrogate Heuristics for p-Median Problems
Abstract
The p-median problem is the problem of locating p facilities (medians) on a network so as to minimize the sum of all the distances from each demand point to its nearest facility. A successful approach to approximately solve this problem is the use of Lagrangean heuristics, based upon Lagrangean relaxation and subgradient optimization. The Lagrangean/surrogate is an alternative relaxation proposed recently to correct the erratic behavior of subgradient like methods employed to solve the Lagrangean dual. We propose in this paper Lagrangean/surrogate heuristics to p-median problems. Lagrangean and surrogate relaxations are combined relaxing in the surrogate way the assignment constraints in the p-median formulation. Then, the Lagrangean relaxation of the surrogate constraint is obtained and approximately optimized (one-dimensional dual). Lagrangean/surrogate relaxations are very stable (low oscillating) and reach the same good results of Lagrangean (alone) heuristics in less computational times. Two primal heuristics was tested, an interchange heuristic and a location-allocation based heuristic. The paper presents several computational tests which have been conducted with problems from the literature, a set of instances presenting large duality gaps, a set of time consuming instances and a large scale instance.
Edson L. F. Senne, Luiz A. N. Lorena
Chapter 7. An Introduction to Ant Systems
Abstract
This article introduces Ant Systems, a meta-heuristic based on an ant foraging metaphor. The presentation of Ant Systems has been somewhat generalized by adding a “Queen” process in charge of coordinating classical “Ant” processes, so that recent Ant Systems can be naturally included while remaining close to the metaphor. To illustrate how Ant Systems are practically implemented, a number of applications to the quadratic assignment problem are reviewed.
Éric D. Taillard
Chapter 8. Extremal Energy Models and Global Optimization
Abstract
The objective of global optimization (GO) is to find the absolutely best solution of nonlinear decision models that often have multiple—local and global—optima. Extremal energy point configuration models in computational chemistry and closely related areas provide a practically important, as well as numerically challenging area to test and apply GO strategies. First, we review several frequently used energy model forms. This is followed by a brief discussion related to one of these, the Lennard-Jones cluster (LJC) model posed as a GO problem. For illustration, LGO—an integrated model development and solver system for analyzing GO problems—is applied to solve small, yet non-trivial instances of the LJC model. We conclude by discussing the broad applicability of GO in this area, including possible energy model extensions.
János D. Pintér
Chapter 9. A Simulation-Based Policy Iteration Algorithm for Average Cost Unichain Markov Decision Processes
Abstract
In this paper, we propose a simulation-based policy iteration algorithm for Markov decision process (MDP) problems with average cost criterion under the unichain assumption, which is a weaker assumption than found in previous work. In this algorithm, 1) the problem is converted to a stochastic shortest path problem and a reference state can be chosen as any recurrent state under the current policy, in which case the reference state is not necessarily the same from iteration to iteration; 2) the differential costs are evaluated indirectly by a temporal-difference learning scheme; 3) transient states are selected as the initial states for sample paths and the inverse of the visit count is chosen as the stepsize to improve the performance. Numerical results using the algorithm for an inventory control problem are also provided.
Ying He, Michael C. Fu, Steven I. Marcus
Chapter 10. Knowledge Management and its Impact on Decision Support
A Knowledge Management System Architecture
Abstract
The purpose of decision support systems (DSS) is knowledge management, not numbers or algorithms. Knowledge management is the practice of adding actionable value to information; by capturing tacit knowledge and converting it to explicit knowledge; by filtering, storing, retrieving and disseminating explicit knowledge; and by creating and testing new knowledge. The purpose of this paper is to propose, as an extension to the model management system of a DSS, a knowledge management system (KMS) that provides storage and retrieval operations, as well as intelligent analysis of explicit knowledge in a DSS. The primary goal of the KMS is to provide the user with an easy-to-use, computer-assisted platform that enhances the articulation, integration and understanding of the knowledge management process in decision support.
Richard T. Herschel, Hamid R. Nemati, David M. Steiger
Chapter 11. Heuristics for Minimum Cost Steady-State Gas Transmission Networks
Abstract
In this paper we propose and present two heuristics for the problem of minimizing fuel cost on steady-state gas transmission problems on looped networks. One of the procedures is based on a two-stage iterative procedure, where, in a given iteration, gas flow variables are fixed and optimal pressure variables are found via dynamic programming in the first stage. In the second stage, the pressure variables are fixed and an attempt is made to find a set of flow variables that improve the objective function by exploiting the underlying network structure. The other proposed heuristic adapts some concepts from generalized reduced gradient methods to attempt to find the direction step. This work focuses on looped network topologies, that is, networks with at least one cycle containing two or more compressor stations. These topologies possess the highest degree of difficulty in real-world problems.
Seongbae Kim, Roger Z. Ríos-Mercado, E. Andrew Boyd
Chapter 12. Assigning Proctors to Exams with Scatter Search
Abstract
In this paper we present an algorithm to assign proctors to exams. This NP-hard problem is related to the generalized assignment problem with multiple objectives. The problem consists of assigning teaching assistants to proctor final exams at a university. We formulate this problem as an integer program (IP) with a weighted objective that combines a preference function and a workload-fairness function. We develop a scatter search procedure and compare its outcome with solutions found by solving the IP model with CPLEX 6.5. Our test problems are real instances from a University in Spain.
Rafael Martí, Helena Lourenço, Manuel Laguna
Chapter 13. Multi-Attribute Evaluation of Software Maintainability
Abstract
Software maintenance activities have become more than ever a heavy burden for many firms (Corbi 1989, Yourdon 1992). Moreover, the increase in maintenance costs is mostly due to the deterioration of the program’s intrinsic quality. The key to reducing these maintenance costs is to apply software renovation tools and methodologies that will improve the quality of programs. This paper discusses the construction of a quality model that can highlight outlying software components that might cause potential quality problems, and that can recommend a set of actions to be undertaken in order to improve the software quality (e.g., the program has to be formatted, restructured, rewritten or documented). These actions significantly reduce the maintenance burden of computer programs and freeing up human resources for the development of new applications. The problem of evaluating the quality of programs is formulated as a multi-attribute-sorting problem and consists of assigning each program to an appropriate pre-defined category. This classification is obtained by applying three different approaches: multivariate statistical methods, multicriteria decision aid methodology and the rough set analysis.
Nadine Meskens, Florence Lebon
Chapter 14. Explicit-Constraint Branching for Solving Mixed-Integer Programs
Abstract
This paper develops a new generalized-branching technique called “explicit-constraint branching” (ECB) to improve the performance of branch-and-bound algorithms for solving mixed-integer programs (MIPs). ECB adds structure to a MIP, in the form of auxiliary constraints and auxiliary integer variables, to allow branching on groups of (original) integer variables that would not otherwise be possible. Computational tests on three sets of real-world MIPs demonstrate that ECB often improves solution times over standard branch and bound, sometimes dramatically.
Jeffrey A. Appleget, R. Kevin Wood
Chapter 15. An Object-Oriented Graphical Modeler for Optimal Production Planning in a Refinery
Abstract
A visually interactive graphical modeling approach for process oriented production systems, with hidden generation of complex optimization models for production planning is presented. The concept is demonstrated with a linear programming prototype developed for a petroleum refinery, AREMOS. The system lets the users build a graphical model of the refinery through its interactive visual interface, accepts production-specific data for its components, and finally, internally generates and solves the mathematical programming model without any interaction with the user. The approach allows the continued use of optimization models without requiring any mathematical programming background, as the generation of mathematical models is hidden and automatic, therefore maintenance free: updating graphical production system models is enough for renewing internal optimization models.
Murat Draman, İ. Kuban Altinel, Nijaz Bajgoric, Ali Tamer Ünal, Burak Birgören
Chapter 16. Optimization of Water Distribution Systems by a Tabu Search Metaheuristic
Abstract
A Tabu Search optimisation technique is proposed for designing, planning and maintaining water distribution systems. As design and maintenance of pipe networks for water supply distribution require high costs, achieving the highest level of performance of existing networks at minimum costs is mandatory. The problem involves setting a lot of variables, as location and diameters of new pipes, operations on existing pipes, and so on. The domain of variables is discrete in nature, due to the fact that pipes are available with unified dimensions. Furthermore, the objective function to be minimised, i.e., the total cost of the plant, is non linear, non differentiable, highly ill-conditioned, and presents a huge amount of local minima. Recently, increasing attention has been paid to heuristic optimisation techniques, such as genetic algorithms (GA), simulated annealing (SA), and tabu-search (TS) for large combinatorial optimisation problems. In particular, GA has been applied to the problem of designing and maintaining water distribution networks. Results show good performance of the GA in terms of objective function values, but high computation time. One of the most promising approaches to combinatorial optimisation problems is the TS metaheuristic, that showed flexibility and effectiveness in a lot of applications. The aim of this paper is to present a TS based algorithm to the design of water distribution systems, and to demonstrate its validity in this field.
A. Fanni, S. Liberatore, G. M. Sechi, M. Soro, P. Zuddas
Chapter 17. Scatter Search to Generate Diverse MIP Solutions
Abstract
An objective function often is only a rough approximation of the actual goals of the organization and its stakeholders. Consequently, an optimal solution may be no more interesting than other solutions that provide good values. Beyond this, a set of “good” solutions whose members have diverse characteristics can be significantly more valuable for practical analysis and planning than any single, “best” solution. Yet the challenge of systematically uncovering such a diverse set of solutions, or even postulating what its defining features may be, has been conspicuously neglected. We address this challenge for 0-1 mixed integer programming problems and provide demonstrations of the computational efficiency of our approach.
Fred Glover, Arne LøKketangen, David L. Woodruff
Metadaten
Titel
Computing Tools for Modeling, Optimization and Simulation
herausgegeben von
Manuel Laguna
José Luis González Velarde
Copyright-Jahr
2000
Verlag
Springer US
Electronic ISBN
978-1-4615-4567-5
Print ISBN
978-1-4613-7062-8
DOI
https://doi.org/10.1007/978-1-4615-4567-5