Integer programming

Integer programming optimizes a linear objective subject to linear constraints, with some or all decision variables restricted to integer values. Its discrete decisions make it generally harder than continuous linear programming.

Linear programming relaxation: A relaxation of an integer program formed by replacing integer restrictions with continuous bounds. It gives bounds and a tractable starting point for many integer-programming algorithms.
Linear programming: Optimization of a linear objective over a feasible region defined by linear constraints. Integer programming adds discrete restrictions to this continuous optimization framework.
Knapsack problem: A selection problem that maximizes value subject to a capacity limit. Binary integer variables represent whether each item is chosen.
Continuous optimization: Optimization in which decision variables can take values throughout continuous domains. Removing integrality usually makes the problem easier, but can permit impractical fractional decisions.
Branch and bound: An optimization method that partitions a problem into subproblems and prunes those that cannot improve the best known solution. It enforces integrality by splitting variable ranges while using relaxation bounds to prune.
Mixed-integer linear programming: Linear optimization in which some decision variables are integer-valued and others are continuous. This is the standard model when decisions combine discrete choices and continuous quantities.
Set covering problem: A problem of choosing the least costly collection of sets that covers every required element. Its binary formulation captures facility placement, crew assignment, and related choices.
Constraint programming: A modeling and solving approach that represents problems through variables, domains, and constraints. It handles discrete structure directly, often complementing integer-programming formulations.
Cutting-plane method: An optimization method that iteratively adds valid inequalities to exclude nonoptimal regions of a feasible set. Cuts remove fractional relaxation solutions without discarding any integer-feasible solutions.
0–1 integer programming: Integer programming in which every decision variable is restricted to zero or one. Binary variables encode yes-or-no choices, selections, and logical conditions.

Linked from 22 pages