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 the 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.^[1][2] 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 ^[3], and provide a parametrization of all integer programming problems.

References

Further reading

• George L. Nemhauser; Laurence A. Wolsey (1988). Integer and combinatorial optimization. Wiley. ISBN 9780471828198. 
• Alexander Schrijver (1998). Theory of linear and integer programming. John Wiley and Sons. ISBN 9780471982326. 
• Laurence A. Wolsey (1998). Integer programming. Wiley. ISBN 9780471283669. 
• Dimitris Bertsimas; Robert Weismantel (2005). Optimization over integers. Dynamic Ideas. ISBN 9780975914625. 
• John K. Karlof (2006). Integer programming: theory and practice. CRC Press. ISBN 9780849319143. 
• H. Paul Williams (2009). Logic and Integer Programming. Springer. ISBN 9780387922799. 
• Michael Jünger, Thomas M. Liebling, Denis Naddef, George Nemhauser, William R. Pulleyblank, et al., ed. (2009). 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer. ISBN 9783540682745. 
• Der-San Chen; Robert G. Batson; Yu Dang (2010). Applied Integer Programming: Modeling and Solution. John Wiley and Sons. ISBN 9780470373064. 

External links

• A Tutorial on Integer Programming

Optimization: Algorithms, methods, and heuristics   Unconstrained nonlinear: Methods calling ... ... functions Golden section search Interpolation methods Line search Successive parabolic interpolation ... and gradients Convergence Trust region Wolfe conditions Quasi–Newton BFGS and L-BFGS DFP Symmetric rank-one (SR1) Other methods Gauss–Newton Gradient Levenberg–Marquardt Conjugate gradient ... and Hessians Newton's method   Constrained nonlinear General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming   Convex optimization Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-Exchange Simplex algorithm of Dantzig Criss-cross algorithm Principal pivoting algorithm of Lemke   Combinatorial Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch & bound or cut Graph algorithms Minimum spanning tree Bellman–Ford Borůvka Dijkstra Floyd–Warshall Johnson Kruskal Network flows Dinic Edmonds–Karp Ford–Fulkerson Push-relabel maximum flow   Metaheuristics Evolutionary algorithm Hill climbing Local search Simulated annealing Tabu search Categories Algorithms and methods Heuristics Software