Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach / Edition 1

by Adam Kasperski

Overview

Operations research often solves deterministic optimization problems based on elegantand conciserepresentationswhereall parametersarepreciselyknown. In the face of uncertainty, probability theory is the traditional tool to be appealed for, and shastic optimization is actually a significant sub-area in operations research. However, the systematic use of prescribed probability distributions so as to cope with imperfect data is partially unsatisfactory. First, going from a deterministic to a shastic formulation, a problem may becomeintractable. A good example is when going from deterministic tosh- tic scheduling problems like PERT. From the inception of the PERT method in the 1950’s, it was acknowledged that data concerning activity duration times is generally not perfectly known and the study of shastic PERT was launched quite early. Even if the power of today’s computers enables the shastic PERT to be addressed to a large extent, still its solutions often require simplifying assumptions of some kind. Another difficulty is that shastic optimization problems produce solutions in the average. For instance, the criterion to be maximized is more often than not expected utility. This is not always a meaningful strategy. In the case when the underlying process is not repeated a lot of times, let alone being one-shot, it is not clear if this criterion is realistic, in particular if probability distributions are subjective. Expected utility was proposed as a rational criterion from first principles by Savage. In his view, the subjective probability distribution was - sically an artefact useful to implement a certain ordering of solutions.

Product Details

ISBN-13:	9783540784838
Publisher:	Springer Berlin Heidelberg
Publication date:	06/04/2008
Series:	Studies in Fuzziness and Soft Computing , #228
Edition description:	2008
Pages:	220
Product dimensions:	6.40(w) x 9.30(h) x 0.80(d)

Table of Contents

Minmax Regret Combinatorial Optimization Problems with Interval Data.- Problem Formulation.- Evaluation of Optimality of Solutions and Elements.- Exact Algorithms.- Approximation Algorithms.- Minmax Regret Minimum Selecting Items.- Minmax Regret Minimum Spanning Tree.- Minmax Regret Shortest Path.- Minmax Regret Minimum Assignment.- Minmax Regret Minimum s???t Cut.- Fuzzy Combinatorial Optimization Problem.- Conclusions and Open Problems.- Minmax Regret Sequencing Problems with Interval Data.- Problem Formulation.- Sequencing Problem with Maximum Lateness Criterion.- Sequencing Problem with Weighted Number of Late Jobs.- Sequencing Problem with the Total Flow Time Criterion.- Conclusions and Open Problems.- Discrete Scenario Representation of Uncertainty.