Постановки задач целочисленного программирования
Пример. Задача целочисленного линейного программирования ( ЦЛП ).
Задачей ЦЛП называют следующую задачу оптимизации:
- целочисленно.
Здесь 
, 
, 
. Элементы матрицы 
и векторов 
и 
предполагаются целыми. На рис.1 приведен пример двумерной задачи ЦЛП.
Рис.1. Четыре целочисленные точки, ближайшие к оптимуму задачи ЛП, недопустимы.
В некоторых приложениях дробные решения недопустимы, например, в приложении, где 
- число самолетов, назначаемых на маршрут 
. Задачи ЛП, формулируемые как задачи ЦЛП, как правило, по своей природе не допускают подхода, основанного на округлении. Один из эффектов округления - это потеря допустимости решения (см. рис.1).
Пример. (Задача коммивояжера (ЗК)). Коммивояжеру необходимо объехать 
городов 
, начиная с города 1, и посещая каждый город ровно 1 раз, по самому короткому маршруту.
Обозначим 
матрицу расстояний между городами. Сопоставим дуге 
переменную 
и, положив 
, если дуга содержится в обходе, и в противном случае, можно сформулировать ЗК следующим образом:
(a) 
(4.1.1)
(б) 
- целые 
Равенства (а) выражают тот факт, что в каждую вершину входит ровно одна дуга, а равенства (б) - тот факт, что из каждой вершины выходит ровно одна дуга.
В действительности, задача (4.1.1) описывает задачу о назначении и содержит в своем допустимом множестве маршрутов маршруты, состоящие из нескольких замкнутых циклов. Нужны дополнительные ограничения для исключения подобных решений.