Combinatorial optimization

Combinatorial optimization studies how to find the best feasible choice among discrete possibilities, such as subsets, routes, schedules, or assignments.

Integer programming: Mathematical optimization in which some or all decision variables must take integer values. It expresses discrete choices as variables, constraints, and an objective function.
Feasible region: The set of all choices satisfying the constraints of an optimization problem. Discrete constraints determine which combinations can compete for optimality.
Traveling salesperson problem: The problem of finding a shortest tour that visits each city once and returns to the start. It is a defining example of selecting an optimal permutation under a global cost.
Continuous optimization: Optimization over variables that can take values from continuous domains, such as real numbers. Its variable domains differ from the discrete choices central to combinatorial optimization.
Branch and bound: An exact search method that divides a problem into subproblems and prunes regions using bounds. It can prove optimality without examining every feasible combination.
Objective function: A function assigning a value to each candidate solution, which an optimization problem seeks to maximize or minimize. It defines what makes one feasible discrete choice better than another.
Knapsack problem: The problem of choosing items with given values and weights to maximize value within a capacity limit. It captures discrete selection under a resource constraint.
Convex optimization: Optimization of a convex objective over a convex feasible set, with strong guarantees for local optima. Convex structure often permits efficient global optimization unlike general discrete search.
Linear programming relaxation: A relaxation of an integer program formed by allowing variables to take fractional values. Its bounds help branch-and-bound discard discrete regions that cannot improve the incumbent.
NP-hardness: A classification for problems at least as hard as every problem in NP under polynomial-time reductions. Many general combinatorial optimization problems resist known polynomial-time exact algorithms.

Linked from 17 pages