In Operational Research, problems are modeled mathematically consisting of objective functions, decision variables, and constraints. Combinatorial Optimization is the type of model in which its decision variables are discrete such as scheduling problems, traveling salesman problems, knapsack problems, etc.
Each problem has its own computational complexity: a measurement of how difficult a problem in terms of resources required, and each problem are categorized based on its complexity: P Problems or NP-hard problems.
P-hard problems are optimization problems where an exact solution approach that could solve optimality (for any size) in polynomial time exists. On the other hand, NP-hard problems are optimizations problems where an exact solution approach that can solve optimality (for any size) in polynomial time are still undiscovered.
Polynomial time means the computational time required for solving the algorithm is a polynomial function (e.g., f(x) = x2+5 or O(n2 )), whereas exponential time contains exponential elements (e.g., f(x) = 3x or O(3 n )). Therefore, applying exact algorithms for NP-hard problems are limited to certain size and another approach is required to solve the problems with larger size.
Comments