An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming when some but not all the variables are restricted to be integers.
Integer programming is NP-hard. A special case, 0-1 integer linear programming, in which unknowns are binary, is one of Karp's 21 NP-complete problems. However, integer programs with a constant number of variables may be solved in linear time as an LP-type problem. In variable dimension, iterative methods using the Graver basis of the matrix defining the system, enable the solution of broad classes of linear and nonlinear integer programming problems in polynomial time, and provide a parametrization of all integer programming problems.
Famous quotes containing the word programming:
“If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.”
—Melinda M. Marshall (20th century)