𝔖 Scriptorium
✦   LIBER   ✦

πŸ“

Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach (Studies in Fuzziness and Soft Computing, 228)

✍ Scribed by Adam Kasperski


Publisher
Springer
Year
2008
Tongue
English
Leaves
225
Category
Library

⬇  Acquire This Volume

No coin nor oath required. For personal study only.

✦ Synopsis


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 stochastic optimization is actually a signi?cant 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 stochastic formulation, a problem may becomeintractable. Agoodexampleiswhengoingfromdeterministictostoch- 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 stochastic PERT was launched quite early. Even if the power of today’s computers enables the stochastic PERT to be addressed to a large extent, still its solutions often require simplifying assumptions of some kind. Another di?culty is that stochastic 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 ?rst principles by Savage. In his view, the subjective probability distribution was - sically an artefact useful to implement a certain ordering of solutions.

✦ Table of Contents


Title Page
Foreword
Preface
Contents
Part I: Minmax Regret Combinatorial Optimization Problems with Interval Data
Problem Formulation
Deterministic Combinatorial Optimization Problem
Matroidal Problem
Minmax Regret Combinatorial Optimization Problem with Interval Data
Some Related Problems
Other Robustness Criteria
Problem with Maximization Objective Function
Problem with Bottleneck Objective Function
Central Combinatorial Optimization Problem
Notes and References
Evaluation of Optimality of Solutions and Elements
Evaluation of Optimality of Solutions
Evaluation of Optimality of Elements
Possibly Optimal Elements and the Optimal Robust Solutions
Necessarily Optimal Elements and the Optimal Robust Solutions
Matroidal Problems
Notes and References
Exact Algorithms
Mixed Integer Programming Formulation
Branch and Bound Algorithm
Notes and References
Approximation Algorithms
2-Approximation Algorithms
Algorithm for Midpoint Scenario
Algorithm for Midpoint and Upper Scenarios
Algorithm Enumerate
Fully Polynomial Time Approximation Scheme
Notes and References
Minmax Regret Minimum Selecting Items
Evaluation of Optimality
Possibly Optimal Items
Necessarily Optimal Items
Polynomial Algorithm for the Problem
Notes and References
Minmax Regret Minimum Spanning Tree
Computational Complexity
Evaluation of Optimality
Possibly and Necessarily Optimal Edges
Mixed Integer Programming Formulation
Computational Results
Branch and Bound Algorithm
Branching Method
Reduction Rules
Deriving a Feasible Solution
Computational Results
Local Search Algorithms
Neighborhood Function
Iterative Improvement
Local Minimum
Tabu Search Algorithm
Computational Results
Notes and References
Minmax Regret Shortest Path
Some Special Classes of Graphs
Minmax Regret Longest Path in Acyclic Graphs
Computational Complexity
Evaluation of Optimality
Possibly Optimal Arcs
Necessarily Optimal Arcs
Mixed Integer Programming Formulation
MIP Formulation for Directed Graphs
MIP Formulation for Undirected Graphs
Computational Results
Branch and Bound Algorithm
Branching Rule
Reduction Rules
Deriving a Feasible Solution
Computational Results
Series-Parallel Multidigraphs
Pseudopolynomial Algorithm
Fully Polynomial Time Approximation Scheme
Notes and References
Minmax Regret Minimum Assignment
Computational Complexity
Evaluation of Optimality
Mixed Integer Programming Formulation
Computational Results
Notes and References
Minmax Regret Minimum $s βˆ’ t$ Cut
Computational Complexity
Evaluation of Optimality
Mixed Integer Programming Formulation
MIP Formulation for Directed Graphs
MIP Formulation for Undirected Graphs
Computational Results
Series-Parallel Multidigraphs
Polynomially Solvable Version of the Problem
Notes and References
Fuzzy Combinatorial Optimization Problem
Fuzzy Interval and Its Possibilistic Interpretation
Combinatorial Optimization Problem with Fuzzy Weights
Fuzzy Evaluation of Optimality
Computing the Degrees of Optimality
Computing Fuzzy Deviations
Choosing a Solution under Fuzzy Weights
Notes and References
Conclusions and Open Problems
Part II: Minmax Regret Sequencing Problems with Interval Data
Problem Formulation
Deterministic Sequencing Problem
Minmax Regret Sequencing Problem with Interval Data
Notes and References
Sequencing Problem with Maximum Lateness Criterion
Deterministic Problem and Lawler’s Algorithm
Polynomial Algorithm for the Problem
Notes and References
Sequencing Problem with Weighted Number of Late Jobs
Matroidal Structure of the Problem
Possibly and Necessarily Optimal Jobs
Mixed Integer Programming Formulation
Computational Results
Notes and References
Sequencing Problem with the Total Flow Time Criterion
Characterization of the Worst Case Scenario
Computational Complexity and Preprocessing Rules
A 2-Approximation Algorithm
Local Search Algorithm
Mixed Integer Programming Formulation
Computational Results
Notes and References
Conclusions and Open Problems
Discrete Scenario Representation of Uncertainty
MIP Formulation
Complexity Results
Approximation
References
Index


πŸ“œ SIMILAR VOLUMES


Discrete Optimization with Interval Data
✍ Adam Kasperski (auth.) πŸ“‚ Library πŸ“… 2008 πŸ› Springer-Verlag Berlin Heidelberg 🌐 English

<p><P>In operations research applications we are often faced with the problem of incomplete or uncertain data. This book considers solving combinatorial optimization problems with imprecise data modeled by intervals and fuzzy intervals. It focuses on some basic and traditional problems, such as mini

Monte Carlo Methods in Fuzzy Optimizatio
✍ James J. Buckley, Leonard J. Jowers πŸ“‚ Library πŸ“… 2008 πŸ› Springer 🌐 English

<span>1. 1 Introduction The objective of this book is to introduce Monte Carlo methods to ?nd good approximate solutions to fuzzy optimization problems. Many crisp (nonfuzzy) optimization problems have algorithms to determine solutions. This is not true for fuzzy optimization. There are other things

Fuzzy Probabilities: New Approach and Ap
✍ James J. Buckley πŸ“‚ Library πŸ“… 2005 πŸ› Springer 🌐 English

<span>In probability and statistics we often have to estimate probabilities and parameters in probability distributions using a random sample. Instead of using a point estimate calculated from the data we propose using fuzzy numbers which are constructed from a set of confidence intervals. In probab

Fuzzy Engineering Economics with Applica
✍ Cengiz Kahraman (editor) πŸ“‚ Library πŸ“… 2008 πŸ› Springer 🌐 English

<span>Fuzzy set approaches are suitable to use when the modeling of human knowledge is necessary and when human evaluations are needed. Fuzzy set theory is recognized as an important problem modeling and solution technique. It has been studied ext- sively over the past 40 years. Most of the early in

Fuzzy Probability and Statistics (Studie
✍ James J. Buckley πŸ“‚ Library πŸ“… 2006 πŸ› Springer 🌐 English

<span>This book combines material from our previous books FP (Fuzzy Probabilities: New Approach and Applications,Physica-Verlag, 2003) and FS (Fuzzy Statistics, Springer, 2004), plus has about one third new results. From FP we have material on basic fuzzy probability, discrete (fuzzy Poisson,binomia

Recent Developments in Fuzzy Logic and F
✍ Shahbazova πŸ“‚ Library πŸ“… 2020 πŸ› Springer 🌐 English

<p></p><p><span>This book provides a timely and comprehensive overview of current theories and methods in fuzzy logic, as well as relevant applications in a variety of fields of science and technology. Dedicated to Lotfi A. Zadeh on his one year death anniversary, the book goes beyond a pure commemo