Discrete Optimization with Interval Data: Minmax Regret and by Adam Kasperski

By Adam Kasperski

In operations learn functions we're frequently confronted with the matter of incomplete or doubtful info. This e-book considers fixing combinatorial optimization issues of vague information modeled through periods and fuzzy periods. It specializes in a few easy and standard difficulties, similar to minimal spanning tree, shortest course, minimal project, minimal lower and numerous sequencing difficulties. The period established technique has develop into very hot within the contemporary decade. determination makers are frequently drawn to hedging opposed to the danger of negative (worst case) method functionality. this is often really very important for judgements which are encountered just once. in an effort to compute an answer that behaves quite less than any most likely enter information, the maximal remorse criterion is accepted. lower than this criterion we search an answer that minimizes the most important deviation from optimal over all attainable realizations of the enter data.

The minmax remorse method of discrete optimization with period information has attracted huge awareness within the fresh decade. This publication summarizes the state-of-the-art within the region and addresses a few open difficulties. moreover, it features a bankruptcy dedicated to the extension of the framework to the case whilst fuzzy periods are utilized to version doubtful facts. the bushy durations let a extra refined uncertainty evaluate within the environment of danger theory.

This e-book is a necessary resource of knowledge for all operations study practitioners who're attracted to sleek methods to challenge fixing. except the outline of the theoretical framework, it additionally provides a few algorithms that may be utilized to resolve difficulties that come up in practice.

Show description

Read or Download Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach PDF

Similar nonfiction_4 books

Nonfiction Comprehension Test Practice Gr. 5 W Answer Key

According to articles from TIME for children journal, actions supply examining comprehension perform in standardized try structure.

O Pioneers! (Webster's Thai Thesaurus Edition)

Webster's paperbacks make the most of the truth that classics are often assigned readings in English classes. by utilizing a working English-to-Thai word list on the backside of every web page, this version of O Pioneers! through Willa Cather used to be edited for 3 audiences. the 1st comprises Thai-speaking scholars enrolled in an English Language software (ELP), an English as a international Language (EFL) software, an English as a moment Language application (ESL), or in a TOEFL� or TOEIC� training software.

Functional Selectivity of G Protein-Coupled Receptor Ligands: New Opportunities for Drug Discovery

Practical selectivity refers back to the skill of alternative ligands performing at one receptor subtype to turn on a number of signaling pathways in specific combos; that's, one drug should be an agonist at pathway A and an antagonist or partial agonist at pathway B, and one other drug may have the opposite profile.

Extra resources for Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach

Sample text

1 Mixed Integer Programming Formulation Let us introduce a binary variable xi ∈ {0, 1} for every element ei ∈ E. This variable will express whether element ei is a part of the constructed optimal robust solution. A characteristic vector of a given subset of elements A ⊆ E is a binary vector x = (xi )ni=1 such that xi = 1 if and only if ei ∈ A. Let us associate with the set of feasible solutions Φ a set of binary vectors ch(Φ) ⊆ {0, 1}n , which satisfies the following two conditions: A. Kasperski: Discrete Optimization with Interval Data, STUDFUZZ 228, pp.

N Solving the above MIP we get an optimal robust solution to Minmax Regret Minimum Selecting Items. We will show in Chapter 5 that this particular model can be solved in polynomial time. 2 Branch and Bound Algorithm A branch and bound algorithm is one of the most widely used tools for solving NP-hard combinatorial optimization problems. It searches the complete solutions space using the bounds for the value of the objective function combined with the value of the current best solution. The search process is represented as a dynamically generated rooted tree whose leaves describe some unexplored subsets of the solutions space.

2. Let X ∈ Φ and Y ∈ Φ be two feasible solutions. Then the following inequality holds: we − Z(Y ) ≤ Z(X) + e∈Y \X we . 3) e∈X\Y Proof. The following equality is easy to verify: we − + F (Y, SY+ ) = F (X, SX )+ e∈Y \X we . 4) e∈X\Y We now show that + F ∗ (SY+ ) ≥ F ∗ (SX )− (w e − w e ). 5) is false. Let Y ∗ be a feasible solution such that F (Y ∗ , SY+ ) = F ∗ (SY+ ). We thus get + ) > F (Y ∗ , SY+ ) + F ∗ (SX + + (w e − w e ) ≥ F (Y ∗ , SX∪Y ) ≥ F (Y ∗ , SX ), e∈X\Y + which contradicts the definition of F ∗ (SX ).

Download PDF sample

Rated 4.15 of 5 – based on 8 votes