ebook img

Operations Research and Artificial Intelligence: The Integration of Problem-Solving Strategies PDF

502 Pages·1990·26.562 MB·English
Save to my drive
Quick download
Download
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview Operations Research and Artificial Intelligence: The Integration of Problem-Solving Strategies

Operations Research and Artificial Intelligence: The Integration of Problem-Solvi ng Strateg ies Operations Research and Artificial Intelligence: The Integration of Problem-Salvi ng Strateg ies edited by Donald E. Brown Chelsea C. White, III University of Virginia Kluwer Academic Publishers BostonlDordrechtlLondon Distributors for North America: Kluwer Academic Publishers 101 Philip Drive Assinlppi Park Norwell, Massachusetts 02061 USA Distributors for all other countries: Kluwer Academic Publishers Group Distribution Centre Post Office Box 322 3300 AH Dordrechf. THE NETHERLANDS Library of Congress Cataloging-in-Publication Data Operations research and artificial intelligence: the integration of problem-solving strategies / edited by Donald E. Brown, Chelsea C. White, III p cm. Includes bibliographical references and Index ISBN-13: 978-94-010-7488-9 e-ISBN-13: 978-94-009-2203-7 001: 10.1007/978-94-009-2203-7 1. Artificial intelligence. 2. Operations research. 3. Decision -making. I. Brown, Donald E. II. White, Chelsea C., 1945- 0335.064 1990 006.3-dc20 90-39443 CIP Copyright © 1990 by Kluwer Academic Publishers All rights reserved. No part of thiS publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher, Kluwer Academic Publishers, 101 Philip Drive, Assinippi Park, Norwell, Massachusetts 02061 Contents Contributors vii Preface ix Introduction D.E. Brown and C.C. White, III I. Search 7 Toward the Modeling, Evaluation and Optimization of Search Algorithms 11 O. Hansson, G. Holt and A. Mayer Genetic Algorithms Applications to Set Covering and Traveling Salesman Problems 29 G.E. Liepins, M.R. Hilliard, J. Richardson and M. Palmer Discovering and Refining Algorithms Through Machine Learning 59 M.R. Hilliard, G.E. Liepins and M. Palmer II. Uncertainty Management 79 USing Probabilities as Control Knowledge to Search for Relevant Problem Models in Automated Reasoning 83 R.K. Bhatnagar and L.N. Kanal On the Marshalling of Evidence and the Structuring of Argument 105 D.A. Schum Hybrid Systems for Failure Diagnosis 141 E. Pate-Cornell and H. Lee III. Imprecise Reasoning 167 Default Reasoning Through Integer Linear Programming 171 S.D. Post and C.E. Bell The Problem of Determining Membership Values in Fuzzy Sets in Real World Situations 197 E. Triantaphyllou, P.M. Pardalos and S.H. Mann v vi CONTENTS IV. Decision Analysis and Decision Support 215 Applications of Utility Theory in Artificial Intelligence Research 219 P.H. Farquhar A Multicriteria Stratification Framework for Uncertainty and Risk Analysis 237 J. Barlow and F. Glover Dispute Mediation: A Computer Model 249 K. Sycara V. Mathematical Programming and AI 275 Eliciting Knowledge Representation Schema for Linear Programming Formulation 279 M.M. Sklar, RA Pick, G.B. Vesprani and J.R. Evans A Knowledge Base for Integer Programming-A Meta-OR Approach 317 F. Zahedi VI. Performance Analysis and Complexity Management of Expert Systems 369 Validator, A Tool for Verifying and Validating Personal Computer Based Expert Systems 373 M. Jafar and A.T. Bahill Measuring and Managing Complexity in Knowledge-Based Systems: A Network and Mathematical Programming Approach 387 D.E. O'Leary Pragmatic Information-Seeking Strategies for Expert Classification Systems 427 LA Cox, Jr. VII. Applications 449 A Knowledge- and Optimization-Based Approach to Scheduling in Automated Manufacturing Systems 453 A. Kusiak An Integrated Management Information System for Wastewater Treatment Plants 481 W. Lai, P.M. Berthouex and D. Hindle About the Authors 497 Index 507 Contributors Professor A. Terry Bahill, Systems and Industrial Engineering, University of AIizona, Tucson, AZ 85721 Professor Colin E. Bell, College of Business Administration, Department of Management Sciences, The University of Iowa, Iowa City, IA 52242 Professor P.M. Berthouex, Department of Civil & Environmental Engineering, University of Wisconsin-Madison, Madison, WI 53706 Mr. Tony Cox, US WEST Advanced Technologies, 6200 South Quebec Street, Englewood, CO 80111 Professor Peter H. Farquhar, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA 15213-3890 Professor Fred Glover, Graduate School of Business, University of Colorado, Boulder, CO 80309-0419 Dr. Michael R. Hilliard, Research Associate, Martin Marietta Energy Systems, Inc., P.O. Box 2008, Oak Ridge, TN 37831- 6366 Professor Laveen N. Kanal, Department of Computer Science, The University of Maryland, College Park, MD 20742 Professor Andrew Kusiak, Industrial & Management Engineering, The University of Iowa, Iowa City, IA 52242 Dr. Gunar Liepins, Oak Ridge National Laboratory, P.O. Box 2008, Oak Ridge, TN 37831 Professor Andrew Mayer, Computer Science Division, University of California at Berkeley, Berkeley, CA 94720 Professor Daniel E. O'Leary, Graduate School of Business, University of Southern California, Los Angeles, CA 90089-1421 Professor Panos M. Pardalos, Department of Computer Science, The Pennsylvania State University, University Park, PA 16802 Professor M.E. Pate-Cornell, Industrial Engineering & Engineering Management, Stanford University, Stanford, CA 94305 Professor David A. Schum, Operations Research & Applied Statistics, George Mason University, Fairfax, VA 22030 Professor Margaret M. Sklar, Department of Management, Marketing, and CIS, School of Business, Northern Michigan University, Marquette, MI 49855 Professor Katia Sycara, The Robotics Institute, Carnegie-MeHon University, Pittsburgh, PA 15213-3890 Professor Fatemeh Zahedi, Management Sciences Department, University of Massachusetts - Boston, Harbor Campus, Boston, MA 02125-3393 vii Preface The purpose of this book is to introduce and explain research at the boundary between two fields that view problem solving from different perspectives. Researchers in operations research and artificial intelligence have traditionally remained separate in their activities. Recently, there has been an explosion of work at the border of the two fields, as members of both communities seek to leverage their activities and resolve problems that remain intractable to pure operations research or artificial intelligence techniques. This book presents representative results from this current flurry of activity and provides insights into promising directions for continued exploration. This book should be of special interest to researchers in artificial intelligence and operations research because it exposes a number of applications and techniques, which have benefited from the integration of problem solving strategies. Even researchers working on different applications or with different techniques can benefit from the descriptions contained here, because they provide insight into effective methods for combining approaches from the two fields. Additionally, researchers in both communities will find a wealth of pointers to challenging new problems and potential opportunities that exist at the interface between operations research and artificial intelligence. In addition to the obvious interest the book should have for members of the operations research and artificial intelligence communities, the papers here are also relevant to members of other research communities and development activities that can benefit from improvements to fundamental problem solving approaches. Included in this category are engineers and physical and social scientists, who require improved decision making techniques or greater understanding of processes involved in problem solving in complex domains. Most of the papers in this book were presented at the Joint National Meetings of the Operations Research Society of America and The Institute for Management Science. Over the past three years there were roughly 400 papers presented at these meetings that incorporated results from artificial intelligence. Officers and council members of the Artificial Intelligence Technical Section of the Operations Research Society of America decided to organize and ix x present significant results from among these papers. It was decided early in this process, that rather than simply collect papers and bind them, a formal review process should be instituted. Hence, the papers collected here represent the results of a two tiered review process, designed to distill and present the more significant results from these meetings. We acknowledge the support received in the preparation of this work from the members of the Artificial Intelligence Technical Section of the Operations Research Society of America. The project was particularly encouraged by the first chairperson of the Technical Section (at the time it was a Special Interest Group), Frank Morisano, and received the complete support of his successors, Jerry May and Gunar Liepens. We also appreciate the support of the referees, who assisted us in reviewing the submitted papers. We experienced a very high return rate on review requests for this volume, which made it much easier to compile the papers. Finally, we owe special thanks to Annelise Tew, who assisted us throughout the preparation of this book: maintaining files, calling referees, calling authors, reviewing formats, and generally ensuring our plans were well executed. Donald E. Brown Chelsea C. White, III Charlottesville, Virginia Operations Research and Artificial Intelligence: The Integration of Problem-Solvi ng Strateg ies Introduction Donald E. Brown and Chelsea C. White, III Department of Systems Engineering University of Virginia Charlottesville, Va. 22901 This book contains papers that demonstrate some of the important results from integrating problem solving techniques typically associated with operations research (OR) with those typically associated with artificial intelligence (AI). The papers presented here exemplify what we believe is a stage in the natural evolution of both fields toward more powerful strategies of problem solving. These strategies will find usefulness for both decision aiding, a goal of OR, and automatic decision making, which is the pursuit of AI. Historically, the OR and AI research communities worked in relative isolation from one another. On the one hand this separation is remarkable, because both disciplines are deeply concerned with questions of human problem solving and decision making, both are highly computer dependent, and both share some common conceptual frameworks (e.g graphs, probability theory, and heuristics). On the other hand, the separation is understandable in that OR has sought optimal methods in decision making through formal mathematical structures. AI has emphasized goal seeking and the use of workable, although suboptimal, strategies more closely associated with human performance. While the fields do share some common conceptual frameworks, there are many more that are distinct to each field. For example, AI has a strong foundation in logic with work that emphasizes automatic theorem proving, while OR has instead emphasized the mathematics of optimization and the quantification of preference through utility and value functions. These differences aside, the complexity of many, if not most real world decision problems has exposed the limitations of OR and AI tools, and has caused the two communities to seek solution approaches that integrate these tools. Perhaps the most significant call for integrative approaches to complexity came from Simon (1987), who stressed the common problem solving foundations of the fields. From the OR perspective a more formal organizational statement supporting the general contention that significant advances in problem solving strategies are attainable through the 1

See more

The list of books you might like

Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.