Editing Integer programming (section)

===Heuristic methods===
Since integer linear programming is [[NP-hard]], many problem instances are intractable and so heuristic methods must be used instead.  For example, [[tabu search]] can be used to search for solutions to ILPs.<ref>{{cite journal|last=Glover|first=F.|author-link=Fred W. Glover|title=Tabu search-Part II|journal=ORSA Journal on Computing|year=1989|volume=1|issue=3|pages=4–32|doi= 10.1287/ijoc.2.1.4 |s2cid=207225435}}</ref>  To use tabu search to solve ILPs, moves can be defined as incrementing or decrementing an integer constrained variable of a feasible solution while keeping all other integer-constrained variables constant.  The unrestricted variables are then solved for. Short-term memory can consist of previously tried solutions while medium-term memory can consist of values for the integer constrained variables that have resulted in high objective values (assuming the ILP is a maximization problem). Finally, long-term memory can guide the search towards integer values that have not previously been tried.

Other heuristic methods that can be applied to ILPs include
*[[Hill climbing]]
*[[Simulated annealing]]
*Reactive search optimization
*[[Ant colony optimization algorithms|Ant colony optimization]]
*[[Hopfield network|Hopfield neural networks]]

There are also a variety of other problem-specific heuristics, such as the [[Travelling salesman problem#Iterative improvement|k-opt heuristic]] for the traveling salesman problem. A disadvantage of heuristic methods is that if they fail to find a solution, it cannot be determined whether it is because there is no feasible solution or whether the algorithm simply was unable to find one.  Further, it is usually impossible to quantify how close to optimal a solution returned by these methods are.