ABSTRACT

A combinatorial optimization problem (COP) P consists of a collection of its instances. An instance of P can be represented as an ordered pair (F, f), where F is the family of feasible solutions and f https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_10339.tif"/> is the objective function, which is used to compare two feasible solutions. The family F is formed by subsets of a finite set E = {1, 2, …, m} called the ground set. The objective function f : F → Q + ∪ { 0 } https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_10340.tif"/> assigns a nonnegative cost to every feasible solution S https://s3-euw1-ap-pe-df-pch-content-public-u.s3.eu-west-1.amazonaws.com/9781351236423/7ef10423-eda9-42b3-a9ea-761fc7500b5b/content/equ_10341.tif"/> in F. The Traveling Salesman Problem (TSP) and the Minimum Spanning Tree Problem are typical examples of COPs.