Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения А.А. Колоколов, Т.В. Леванова, Институт информационных технологий и прикладной математики СО РАН 1. Введение
    В [1] описаны алгоритмы для решения частично целочисленных задач производственно-транспортного типа, основанные на идее декомпозиции Бендерса и метода направленного перебора. В данной работе предлагаются декомпозиционные алгоритмы для простейшей задачи размещения (ПЗР), задачи о p-медиане [2, 8] и некоторых других постановок, в которых наряду с отсечениями Бендерса для решения целочисленной подзадачи используется лексикографический перебор L-классов [?]. Краткое сообщение о них имеется в [7].
    Рассмотрим ПЗР в следующей постановке. Дано конечное множество пунктов возможного размещения предприятий и список клиентов. Предприятия производят однородный продукт в неограниченном количестве. Известны стоимости размещения предприятий в указанных пунктах и затраты на удовлетворение спроса каждого клиента. Требуется разместить предприятия и прикрепить к ним клиентов так, чтобы суммарные производственно-транспортные затраты были минимальны. Введем некоторые обозначения:
    m - число пунктов возможного размещения предприятий, i - номер предприятия,
    n - число клиентов, j - номер клиента,
    ci - стоимость размещения предприятия в пункте i;
    tij - затраты на удовлетворение спроса клиента j предприятием i (включающие издержки на производство и транспортировку);
    xij - часть всей продукции, которую необходимо доставить с предприятия i клиенту j;
    
    Обозначим .
    Мы используем следующую модель ПЗР: (1) (2) (3) (4) 2. Алгоритм перебора L - классов
    В [?] и других работах развивается подход к анализу и решению задач целочисленного программирования, основанный на регулярных разбиениях пространства Rn. Много результатов было получено с помощью L-разбиения.
    Дадим определение L-разбиения. Пусть , - символы лексикографического порядка. Точки являются L-эквивалентными, если не существует , такой что . Это отношение разбивает любое множество на классы эквивалентности, которые называются L-классами. L-разбиение обладает рядом важных свойств.
    1) Каждая точка образует отдельный L - класс. Остальные классы состоят только из нецелочисленных точек и называются дробными.
    2) Если X ограниченное множество, то фактор-множество X/L - конечно.
    3) L - разбиение согласовано с лексикографическим порядком, то есть для любого X все элементы X/L могут быть линейно упорядочены следующим образом: для всех .
    Если X ограничено, то X/L можно представить в виде
    
    Рангом L - класса V называется число , если V дробный L - класс и r(V) = n+1 для любой целой точки.
    Алгоритм перебора L - классов основан на идее поиска элемента L - разбиения, непосредственно следующего за данным L - классом в порядке лексикографического возрастания (для задачи на минимум).
    Пусть . Рассмотрим этот метод более подробно для многогранника . Задача булева программирования (БП) имеет вид:
     (5) Соответствующая задача линейного программирования (ЛП) состоит в нахождении лексикографически минимального элемента множества M. ............