Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Local Search Techniques and Tools for Scheduling Problems

L'anteprima di questa tesi è scaricabile in PDF gratuitamente.
Per scaricare il file PDF è necessario essere iscritto a Tesionline.
L'iscrizione non comporta alcun costo. Mostra/Nascondi contenuto.

1.1. Combinatorial Problems 5 composed of the valid colorings only, i.e., the functions c such that c(v) 6= c(w) if (v, w) ∈ E. The objective function simply accounts for the overall number of colors used by c, i.e., f(c) = |{c(v) : v ∈ V }|. The decision variables correspond to the vertices of the graph (i.e., the domain of c), and can assume values in the set {1, . . . , |V |}. 1.1.2 Decision Problems Given a combinatorial optimization problem, a family of related (and possibly easier) problems is the class of so-called decision problems. In this case we are not interested in optimizing a cost criterion, but we look for a solution for which the cost measure remains under a reasonable level. The formal definition of this class of problems is as follows. Definition 1.2 (Decision Problems) Under the same hypotheses of combinatorial optimization problems, once fixed a bound k on the value of the objective function, the decision problem 〈S,F , f, k〉 is the problem of stating whether there exists an element x? ∈ F such that f(x?) ≤ k. An example of a decision problem related to the Graph Coloring problem presented above is the following: Example 1.2 (The k-Graph Coloring problem) The decision problem corresponding to the min-Graph Coloring problem is known as k -Graph Coloring. In the decision problem formulation, we are interested in solutions where the number of colors used by the function c is less than or equal to k. All the other components of the problem remain unchanged. It is worth noticing that a given optimization problem can be translated into a sequence of decision problems. The translation strategy employs a binary search for the optimal bound k on the cost function, and it introduces a small overhead that is logarithmic in the size of the optimal solution value f(x∗). 1.1.3 Search Problems The class of search problems differs from the other classes of combinatorial problems presented so far, by the absence of a cost criterion. In fact, in this case we are only interested in finding a solution that meets a set of prespecified conditions. The formal definition of search problems is as follows. Definition 1.3 (Search Problems) Given a pair 〈S,F〉 where S is the set of solutions and F ⊆ S is the set of feasible solutions, a search problem consists in finding a feasible solution, i.e., an element x¦ ∈ F . Notice that a search problem can also be viewed as an instance of a decision problem, where the cost function f(x) = c is constant. The k -Graph Coloring problem can alternatively be viewed as an instance of a search prob- lem, once fixed the possible colors to be used. Its statement is as follows. Example 1.3 (The k-Graph Coloring problem as a Search Problem) In the search formulation of k -Graph Coloring we restrict the colors to the set {0, . . . , k − 1}. As in the previous cases, the set of variables corresponds to the set of vertices to be colored (S = {v|v ∈ V }) and the feasible set is {c : V → {0, . . . , k − 1}|c(u) 6= c(v)∀(u, v) ∈ E}.

Anteprima della Tesi di Luca Di Gaspero

Anteprima della tesi: Local Search Techniques and Tools for Scheduling Problems, Pagina 7

Tesi di Dottorato

Dipartimento: Dipartimento di Matematica e Informatica

Autore: Luca Di Gaspero Contatta »

Composta da 136 pagine.

 

Questa tesi ha raggiunto 658 click dal 20/03/2004.

 

Consultata integralmente una volta.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.