integer programming
In plain wordsFinding the best plan when some decisions must be whole numbers or yes-or-no choices — you cannot open half a warehouse or send 2.7 trucks. That small change makes the best plan far harder to find.
Optimization in which at least some decision variables must take whole-number values, as needed for indivisible quantities and yes-or-no choices. Usually the rest of the problem is linear (integer linear programming); with both integer and continuous variables it is a mixed-integer program (MIP or MILP), and binary 0–1 variables can encode logic such as 'if this machine runs, that one must stop'. Integrality transforms the difficulty: linear programminglinear programming, n.: A mathematical way to find the best use of limited resources, such as a factory's machines or an airline's crews, when every cost and limit scales in simple proportion: twice the output needs twice the input. is solvable in polynomial time, but integer programming is NP-hard, its 0–1 form being one of Richard Karp's 21 NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all. problems (1972). Solvers nonetheless handle many large industrial instances by combining branch and boundbranch and bound, n.: A method for finding the provably best answer to a hard puzzle: divide the possibilities into groups, quickly estimate the best any group could offer, and throw out every group that cannot beat the best answer already in hand. — solving linear relaxations that drop integrality in order to bound and prune a search tree — with cutting planes that tighten those relaxations (branch and cut), presolve reductions and primal heuristics. Integer programming is used for scheduling, routing, network design and resource allocation. In AI it is used to verify the robustness of neural networksneural network, n.: A kind of computer program that learns a task from examples by tuning thousands to billions of connections between simple number-crunching units, an arrangement loosely inspired by nerve cells in the brain. with piecewise-linear activations such as ReLUReLU, abbr.: The most common rule a neuron uses to produce its output: keep the number if it is positive, replace it with zero if it is negative. Simple, fast and surprisingly effective., to solve combinatorial planning problems, and as a testbed for learned heuristics, such as neural networks that choose which variable to branch on.
Each GPU is either assigned to a job or not, so the scheduler is really a mixed-integer program.
Origin
George Dantzig, Ray Fulkerson and Selmer Johnson solved a traveling-salesman instance through US cities in 1954 by adding cutting planes to a linear program. Ralph Gomory's cutting-plane method (1958) gave the first finite algorithm for integer linear programs, and Ailsa Land and Alison Doig introduced branch and bound for them in 1960.
Usage note
Most practical models mix integer and continuous variables, so 'MIP' is the everyday term; 'ILP' also abbreviates inductive logic programminginductive logic programming, n.: A kind of machine learning that discovers general logical rules — such as 'X is a grandparent of Z if X is a parent of a parent of Z' — from examples and background knowledge.. Constraint programmingconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes. and SATBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions. solvers attack many of the same combinatorial problems with different methods.
Related
- linear programminglinear programming, n.: A mathematical way to find the best use of limited resources, such as a factory's machines or an airline's crews, when every cost and limit scales in simple proportion: twice the output needs twice the input.
- branch and boundbranch and bound, n.: A method for finding the provably best answer to a hard puzzle: divide the possibilities into groups, quickly estimate the best any group could offer, and throw out every group that cannot beat the best answer already in hand.
- NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all.
- constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes.
- traveling salesman problemtraveling salesman problem, n.: The puzzle of planning a round trip through a list of cities that stops at each one once and covers the least distance. It is easy to state, but the number of possible routes explodes as cities are added.
- optimizationoptimization, n.: Finding the best possible choice according to some score, such as the lowest error or the highest reward. Training an AI is optimization: adjusting its settings until its mistakes are as small as possible.
- linear programminglinear programming, n.: A mathematical way to find the best use of limited resources, such as a factory's machines or an airline's crews, when every cost and limit scales in simple proportion: twice the output needs twice the input.
Sources
- Gomory, R. E. (1958). Outline of an Algorithm for Integer Solutions to Linear Programs. Bulletin of the American Mathematical Society 64(5), 275–278.
- Land, A. H. & Doig, A. G. (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica 28(3), 497–520.
Mentioned in
linear programminglinear programming, n.: A mathematical way to find the best use of limited resources, such as a factory's machines or an airline's crews, when every cost and limit scales in simple proportion: twice the output needs twice the input.