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 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 } 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.