The Impact Of Knowledge On Algorithm Performance In Discrete Optimization

This book is a compilation of a selected subset of research articles presented at the Eighth INFORMS Computing Society Conference, held in Chandler, Arizona, from January 8 to 10, 2003. The articles in this book represent the diversity and depth of the interface between ORiMS (operations research and the management sciences) and CS/AI (computer science and artificial intelligence ). This volume starts with two papers that represent the reflective and integrative thinking that is critical to any scientific discipline. These two articles present philosophical perspectives on computation, covering a variety of traditional and newer methods for modeling, solving, and explaining mathematical models. The next set includes articles that study machine learning and computational heuristics, and is followed by articles that address issues in performance testing of solution algorithms and heuristics. These two sets of papers demonstrate the richness of thought that takes place at the ORiMS and CSI AI interface. The final set of articles demonstrates the usefulness of these and other methods at the interface towards solving problems in the real world, covering e-commerce, workflow, electronic negotiation, music, parallel computation, and telecommunications. The articles in this collection represent the results of cross-fertilization between ORiMS and CSI AI, making possible advances that could have not been achieved in isolation. The continuing aim ofthe INFORMS Computing Society and this research conference is to invigorate and further develop this interface.

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.

Rich in publications, the well-established field of discrete optimization nevertheless features relatively few books with ready-to-use computer programs. This book, geared toward upper-level undergraduates and graduate students, addresses that need. In addition, it offers a look at the programs' derivation and performance characteristics. Subjects include linear and integer programming, packing and covering, optimization on networks, and coloring and scheduling. A familiarity with design, analysis, and use of computer algorithms is assumed, along with knowledge of programming in Pascal. The book can be used as a supporting text in discrete optimization courses or as a software handbook, with twenty-six programs that execute the most common algorithms in each topic area. Each chapter is self-contained, allowing readers to browse at will.

One of the most frequently occurring types of optimization problems involves decision variables which have to take integer values. From a practical point of view, such problems occur in countless areas of management, engineering, administration, etc., and include such problems as location of plants or warehouses, scheduling of aircraft, cutting raw materials to prescribed dimensions, design of computer chips, increasing reliability or capacity of networks, etc. This is the class of problems known in the professional literature as "discrete optimization" problems. While these problems are of enormous applicability, they present many challenges from a computational point of view. This volume is an update on the impressive progress achieved by mathematicians, operations researchers, and computer scientists in solving discrete optimization problems of very large sizes. The surveys in this volume present a comprehensive overview of the state of the art in discrete optimization and are written by the most prominent researchers from all over the world. This volume describes the tremendous progress in discrete optimization achieved in the last 20 years since the publication of Discrete Optimization '77, Annals of Discrete Mathematics, volumes 4 and 5, 1979 (Elsevier). It contains surveys of the state of the art written by the most prominent researchers in the field from all over the world, and covers topics like neighborhood search techniques, lift and project for mixed 0-1 programming, pseudo-Boolean optimization, scheduling and assignment problems, production planning, location, bin packing, cutting planes, vehicle routing, and applications to graph theory, mechanics, chip design, etc. Key features: • state of the art surveys • comprehensiveness • prominent authors • theoretical, computational and applied aspects. This book is a reprint of Discrete Applied Mathematics Volume 23, Numbers 1-3

This monograph develops an algorithmic theory of nonlinear discrete optimization. It introduces a simple and useful setup, which enables the polynomial time solution of broad fundamental classes of nonlinear combinatorial optimization and integer programming problems in variable dimension. An important part of this theory is enhanced by recent developments in the algebra of Graver bases. The power of the theory is demonstrated by deriving the first polynomial time algorithms in a variety of application areas within operations research and statistics, including vector partitioning, matroid optimization, experimental design, multicommodity flows, multi-index transportation and privacy in statistical databases. This monograph is intended for graduate students and researchers. It is accessible to anyone with standard undergraduate knowledge and mathematical maturity.

This book constitutes the refereed proceedings of the 4th Mexican International Conference on Artificial Intelligence, MICAI 2005, held in Monterrey, Mexico, in November 2005. The 120 revised full papers presented were carefully reviewed and selected from 423 submissions. The papers are organized in topical sections on knowledge representation and management, logic and constraint programming, uncertainty reasoning, multiagent systems and distributed AI, computer vision and pattern recognition, machine learning and data mining, evolutionary computation and genetic algorithms, neural networks, natural language processing, intelligent interfaces and speech processing, bioinformatics and medical applications, robotics, modeling and intelligent control, and intelligent tutoring systems.

Discrete Optimization I

This proceedings volume highlights the state-of-the-art knowledge related to optimization, decisions science and problem solving methods, as well as their application in industrial and territorial systems. It includes contributions tackling these themes using models and methods based on continuous and discrete optimization, network optimization, simulation and system dynamics, heuristics, metaheuristics, artificial intelligence, analytics, and also multiple-criteria decision making. The number and the increasing size of the problems arising in real life require mathematical models and solution methods adequate to their complexity. There has also been increasing research interest in Big Data and related challenges. These challenges can be recognized in many fields and systems which have a significant impact on our way of living: design, management and control of industrial production of goods and services; transportation planning and traffic management in urban and regional areas; energy production and exploitation; natural resources and environment protection; homeland security and critical infrastructure protection; development of advanced information and communication technologies. The chapters in this book examine how to deal with new and emerging practical problems arising in these different fields through the presented methodologies and their applications. The chapter topics are applicable for researchers and practitioners working in these areas, but also for the operations research community. The contributions were presented during the international conference “Optimization and Decision Science” (ODS2017), held at Hilton Sorrento Palace Conference Center, Sorrento, Italy, September 4 – 7, 2017. ODS 2017, was organized by AIRO, Italian Operations Research Society, in cooperation with DIETI (Department of Electrical Engineering and Information Technology) of University “Federico II” of Naples.