Задача о покрытии множества (Set Covering Problem, SCP) — классическая и широко распространенная модель дискретной оптимизации. Она возникает каждый раз, когда необходимо выбрать минимальное количество ресурсов для удовлетворения заданного множества потребностей. SCP формирует математический фундамент для колоссальной индустрии составления расписаний экипажей авиакомпаний, оптимизации маршрутов мусоровозов, планирования смен медперсонала и размещения базовых станций сотовой связи.

Задача о раскрое (Cutting Stock Problem) является классической производственной задачей, цель которой — нарезать заготовки заданных размеров из исходных листов или рулонов так, чтобы минимизировать суммарные отходы. Это задача целочисленного линейного программирования с потенциально огромным числом вариантов раскроя, что требует использования специальных методов генерации столбцов.

Метод отсекающих плоскостей Ральфа Гомори стал прорывом в решении задач целочисленного линейного программирования в конце 50-х годов XX века. В отличие от метода ветвей и границ, который разделяет задачу на подзадачи, метод Гомори итеративно добавляет новые линейные ограничения (отсечения), которые "отрезают" нецелочисленные вершины области допустимых решений, не исключая при этом целочисленные точки.

Целочисленное программирование — это раздел математического программирования, в котором на некоторые или все переменные накладывается условие целочисленности. Это кардинально меняет природу задачи: если для линейного программирования существуют эффективные полиномиальные методы, то целочисленные задачи во многих случаях относятся к классу NP-трудных. Наиболее распространенным и эффективным подходом для их решения является метод ветвей и границ.