Среди приближенных методов решения задач дискретного математического программирования и задач структурного синтеза часто используемым является метод локальной оптимизации. Так как пространство 
метризовано, то можно использовать понятие 
-окрестности 
текущей точки поиска 
. Вместо перебора точек во всем пространстве осуществляется перебор только в . Если 
( 
) < ( 
) для всех 
€ 
( ), то считается, что найден локальный минимум целевой функции в точке . В противном случае точку 
, в качестве достигается минимум ( 
) в ( ), принимают в качестве новой текущей точки поиска.
Недостатком метода является его явно выраженная локальность — "застревание" в окрестностях локальных экстремумов. Повысить эффективность поиска можно с помощью метода поиска с запретами (Tabu Search). Для этого в вводят запреты на попадание в некоторые точки. Обычно это запреты на повторное исследование точек, пройденных на нескольких последних шагах оптимизации. Запрет распространяется и на лучшую точку предыдущего шага, которая может оказаться точкой локального минимума. Тогда на данном шаге перемещение происходит в лучшую незапрещенную точку 
, несмотря на то, что 
. Тем самым появляется тенденция к выходу из области притяжения локального экстремума.
