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

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