Discrete optimization with interval data. Minmax regret and fuzzy approach (Q924859): Difference between revisions

The book is devoted to a suite of minmax regret problems studied in the context of interval data. The generic maximal regret of a given solution \(X\) comes in the form \[ Z(X)= \max_{S\in\Gamma}\{F(X, S)- F^*(S)\}. \] Where \(F^*(S)= \min_{X\in\Phi}F(X,S)\) is the weight of the optimal solution under scenario \(S\) and \(F(X,S)= \sum_{e\in X} w^S_e\) is the weight of a given solution \(X\in\Phi\) under scenario \(S\in\Gamma\). The optimization problem formulated above is extended by allowing the weights we to be represented in the form of intervals. The motivation behind this augmentation is motivated by practice as one may easily encounter imprecise input data (e.g., cost, lengths, speed, etc.) where imprecision (lack of knowledge) are present and can be quantified by some intervals. The reader is provided with a systematic and coherently organized subject matter. Part I starts with exact algorithms and then covers some approximation algorithms. In the sequel, presented are applications of minmax regret to a variety of problems including minimum spanning tree, shortest path, minimum assignment, and \(s\)-\(t\) cut. Part II brings a wealth of minmax regret sequencing problems in which interval data are encountered. The three chapters are focused on sequencing problems with (a) maximum lateness criterion, (b) weighted number of late jobs, and (c) total flow time criterion. Overall, this well-rounded and timely research monograph augments the body of knowledge on the subject of minmax regret by engaging non-numeric parameters, being predominantly quantified in terms of information granules such as interval quantities and fuzzy numbers.