ABSTRACT
A combinatorial optimization problem (COP) P consists of a collection of instances. An instance of P can be represented as an ordered pair (F, f ), where F is the family of feasible solutions and f 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} assigns a nonnegative cost to every feasible solution S in F. The Traveling Salesman Problem (TSP) and the Minimum Spanning Tree Problem are typical examples of COPs.
