Лексикографическая оптимизация максимума-минимума
Метод оптимизации

Лексикографическая оптимизация по максимуму и минимуму (также называемая lexmaxmin или leximin или leximax или лексикографической оптимизацией по максимальному порядку ) является разновидностью многоцелевой оптимизации . В общем, многоцелевая оптимизация имеет дело с задачами оптимизации с двумя или более целевыми функциями, которые оптимизируются одновременно. Оптимизация по lexmaxmin предполагает, что лицо, принимающее решения, хотело бы, чтобы наименьшее целевое значение было как можно выше; при этом вторая наименьшая целевая функция должна быть как можно выше; и так далее. Другими словами, лицо, принимающее решения, ранжирует возможные решения в соответствии с лексиминным порядком значений их целевых функций.

В качестве примера рассмотрим эгалитарных социальных планировщиков , которые хотят принять решение о политике, при которой полезность самого бедного человека будет максимально высокой; при этом они хотят максимизировать полезность второго самого бедного человека; и т. д. Этот планировщик решает задачу lexmaxmin, где целевая функция номер i является полезностью агента номер i .

Алгоритмы для оптимизации lexmaxmin (не используя это название) были разработаны для вычисления ядрышка кооперативной игры. [1] [2] Раннее применение lexmaxmin было представлено Мелвином Дрешером [3] в его книге по теории игр в контексте максимального использования ошибок противника в игре с нулевой суммой . Берингер [4] приводит много других примеров из теории игр, а также теории принятия решений .

Обозначение

Задача lexmaxmin может быть записана как: где — функции, которые необходимо максимизировать; — вектор переменных решения; и — допустимое множество — множество возможных значений . лекс ⁡ макс мин ф 1 ( х ) , ф 2 ( х ) , … , ф н ( х ) при условии х ∈ Х {\displaystyle {\begin{align}\operatorname {lex} \max \min &&f_{1}(x),f_{2}(x),\ldots ,f_{n}(x)\\{\text{subject to}}&&x\in X\end{align}}} ф 1 , … , ф н {\displaystyle f_{1},\ldots ,f_{n}} х {\displaystyle x} Х {\displaystyle X} х {\displaystyle x}

Сравнение с лексикографической оптимизацией

Оптимизация Lexmaxmin тесно связана с лексикографической оптимизацией . Однако в лексикографической оптимизации существует фиксированный порядок функций, такой что является самой важной, является следующей по важности и так далее. Напротив, в lexmaxmin все цели одинаково важны. Чтобы представить lexmaxmin как особый случай лексикографической оптимизации, обозначим через наименьшее целевое значение в x . Аналогично, обозначим через второе по величине целевое значение в x и так далее, так что . Тогда задачу оптимизации lexmaxmin можно записать как следующую задачу лексикографической максимизации: ф 1 {\displaystyle f_{1}} ф 2 {\displaystyle f_{2}} ф [ 1 ] ( х ) := мин ( ф 1 ( х ) , … , ф н ( х ) ) = {\displaystyle f_{[1]}(x):=\min(f_{1}(x),\ldots ,f_{n}(x))=} ф [ 2 ] ( х ) := {\displaystyle f_{[2]}(x):=} ф [ 1 ] ( х ) ≤ ф [ 2 ] ( х ) ≤ ⋯ ≤ ф [ н ] ( х ) {\displaystyle f_{[1]}(x)\leq f_{[2]}(x)\leq \cdots \leq f_{[n]}(x)} лекс ⁡ макс ф [ 1 ] ( х ) , … , ф [ н ] ( х ) при условии х ∈ Х {\displaystyle {\begin{align}\operatorname {lex} \max &&f_{[1]}(x),\ldots ,f_{[n]}(x)\\{\text{subject to}}&&x\in X\end{align}}}

Уникальность

В общем случае задача оптимизации lexmaxmin может иметь более одного оптимального решения. Если и являются двумя оптимальными решениями, то их упорядоченный вектор значений должен быть одинаковым, то есть для всех , [5] : Теор.2  то есть наименьшее значение одинаково, второе наименьшее значение одинаково и т. д. Однако несортированные векторы значений могут быть разными. Например, (1,2,3) и (2,1,3) могут быть оба оптимальными решениями одной и той же задачи. х 1 {\displaystyle x^{1}} х 2 {\displaystyle x^{2}} ф [ я ] ( х 1 ) = ф [ я ] ( х 2 ) {\displaystyle f_{[i]}(x^{1})=f_{[i]}(x^{2})} я ∈ [ н ] {\displaystyle я\в [н]}

Однако, если допустимая область представляет собой выпуклое множество , а цели — вогнутые функции , то векторы значений во всех оптимальных решениях должны быть одинаковыми, поскольку, если бы было два различных оптимальных решения, их среднее значение было бы другим допустимым решением, в котором целевые функции достигают более высокого значения, что противоречит оптимальности исходных решений. [5] : Теория 6 

Алгоритмы для непрерывных переменных

Алгоритм насыщения для выпуклых задач

Алгоритм насыщения работает, когда допустимое множество является выпуклым множеством , а цели являются вогнутыми функциями . Варианты этих алгоритмов появляются во многих работах. Самое раннее появление приписывается Александру Копеловицу [1] Элкиндом и Пасечником. [6] Другие варианты появляются в. [7] : 20–27  [8] [9] [5] : Alg.2  [10] [11 ] [12] [13] [14] [15]

Алгоритм сохраняет набор целей, которые считаются насыщенными (также называемыми: блокировками ). Это означает, что их значение не может быть улучшено без ущерба для менее значимых целей. Остальные цели называются свободными . Изначально все цели свободны. В целом алгоритм работает следующим образом:

  • Хотя некоторые цели бесплатны:
    • (P1) Решите следующую задачу с одной целью, где — значение насыщения цели : з к {\displaystyle z_{k}} ф к {\displaystyle f_{k}} макс       з при условии       х ∈ Х , ф к ( х ) = з к  для всех насыщенных целей  к , ф к ( х ) ≥ з  для всех бесплатных целей  к {\displaystyle {\begin{aligned}\max ~~~z\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)=z_{k}{\text{ для всех насыщенных целей }}k,\\&f_{k}(x)\geq z{\text{ для всех свободных целей }}k\end{aligned}}}
    • Если проблема неразрешима или не имеет границ, остановитесь и объявите, что решения нет.
    • В противном случае пусть будет максимальным значением первой задачи. з макс {\displaystyle z_{\макс }}
    • Найдите свободные цели, значение которых не может увеличиться выше без уменьшения какой-либо другой цели ниже . В любом решении lexmaxmin значение любой такой цели должно быть точно . Добавьте все такие цели в набор насыщенных целей, установите их значение насыщения равным , и вернитесь к (P1). з макс {\displaystyle z_{\макс }} з макс {\displaystyle z_{\макс }} з макс {\displaystyle z_{\макс }} з макс {\displaystyle z_{\макс }}

Осталось объяснить, как мы можем находить новые насыщенные цели в каждой итерации.

Метод 1: внутренние оптимизаторы . [1] [6] Внутренний оптимизатор линейной программы — это оптимальное решение, в котором минимально возможное количество ограничений является жестким. Другими словами, это решение внутри оптимальной грани. Внутренний оптимизатор (P1) может быть найден путем решения (P1) с использованием метода эллипсоида или методов внутренней точки .

Набор жестких ограничений во внутреннем оптимизаторе уникален. Доказательство : Предположим от противного, что есть два внутренних оптимизатора, x1 и x2, с разными наборами жестких ограничений. Поскольку допустимое множество выпукло, среднее решение x3 = (x1+x2)/2 также является оптимизатором. Каждое ограничение, которое не является жестким ни в x1, ни в x2, не является жестким и в x3. Следовательно, количество жестких ограничений в x3 меньше, чем в x1 и x2, что противоречит определению внутреннего оптимизатора.

Таким образом, набор жестких ограничений во внутреннем оптимизаторе соответствует набору свободных целей, которые становятся насыщенными. Используя этот метод, решение лексимина может быть вычислено с использованием максимум n итераций.

Метод 2: итерация по всем целям . [7] Можно найти хотя бы одну насыщенную цель, используя следующий алгоритм.

  • За каждую бесплатную цель : ф дж {\displaystyle f_{j}}
    • (P2) Решите следующую однокритериальную задачу: макс       ф дж ( х ) при условии       х ∈ Х , ф к ( х ) ≥ з к  для всех насыщенных целей  к , ф к ( х ) ≥ з макс  для всех бесплатных целей  к {\displaystyle {\begin{aligned}\max ~~~f_{j}(x)\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)\geq z_{k}{\text{ для всех насыщенных целей }}k,\\&f_{k}(x)\geq z_{\max }{\text{ для всех свободных целей }}k\end{aligned}}}
    • Если оптимальное значение равно , то с этого момента цель j становится насыщенной. з макс {\displaystyle z_{\макс }}
    • В противном случае оптимальное значение должно быть больше ; цель j пока остается свободной. з макс {\displaystyle z_{\макс }}
  • Конец для

На каждом шаге по крайней мере одна свободная цель должна стать насыщенной. Это происходит потому, что если бы ни одна цель не была насыщена, то среднее значение всех оптимальных решений для (P2) было бы допустимым решением, в котором все значения цели больше, чем - что противоречит оптимальности решения для (P1). Например, предположим , что цель 1 не насыщена, потому что существует решение с вектором значения (3,1), а цель 2 не насыщена, потому что существует решение с вектором значения и (1,3). Тогда существует решение с вектором значения по крайней мере (2,2), но должно было быть по крайней мере 2. з макс {\displaystyle z_{\макс }} з макс = 1 {\displaystyle z_{\max}=1} з макс {\displaystyle z_{\макс }}

Таким образом, после не более чем n итераций все переменные насыщаются и находится лексиминно-оптимальное решение. На каждой итерации t алгоритм решает не более чем n - t +1 линейных программ; поэтому время выполнения алгоритма не более чем в раз больше времени выполнения решателя LP. ( н + 2 ) ( н + 1 ) / 2 ∈ О ( н 2 ) {\displaystyle (n+2)(n+1)/2\in O(n^{2})}

В некоторых случаях время выполнения алгоритма насыщения может быть улучшено. Вместо того, чтобы находить все насыщенные цели, мы можем выйти из внутреннего цикла после нахождения одной насыщенной цели; алгоритм все равно остановится после максимум n итераций и может сократить количество линейных программ (P2), которые нам нужно решить. [5] : Alg.3 

Более того, вместо того, чтобы перебирать все цели для поиска насыщенной, алгоритм может найти насыщенную цель, используя двойственную задачу (P1). В некоторых случаях двойственные переменные задаются как побочный продукт решения (P1), например, когда цели и ограничения линейны, а решатель — симплексный алгоритм . В этом случае (P2) вообще не нужен, и время выполнения алгоритма в большинстве случаев равно времени выполнения решателя (P1). [5] : Alg.4  н {\displaystyle n}

Все эти варианты работают только для выпуклых задач. Для невыпуклых задач может не быть насыщенной цели, поэтому алгоритм может не остановиться.

Алгоритм упорядоченных результатов для общих проблем

Алгоритм упорядоченных результатов работает в произвольных областях (не обязательно выпуклых). Он был разработан Огрычаком и Сливинским [16] , а также представлен в контексте телекоммуникационных сетей Огрычаком, Пиоро и Томашевским [5] и в контексте проблем местоположения Огрычаком. [17] Алгоритм сводит оптимизацию lexmaxmin к более простой задаче лексикографической оптимизации . Лексикографическая оптимизация может быть выполнена с помощью простого последовательного алгоритма, который решает не более n линейных программ. Сведение начинается со следующего представления lexmaxmin: ( Л 1 ) лекс ⁡ макс ф [ 1 ] ( х ) , … , ф [ н ] ( х ) при условии х ∈ Х {\displaystyle {\begin{align}(L1)\\\operatorname {lex} \max &&f_{[1]}(x),\ldots ,f_{[n]}(x)\\{\text{subject to}}&&x\in X\end{align}}}

Эту задачу нельзя решить как есть, поскольку ( t -ое наименьшее значение в ) не является простой функцией x . Задача (L1) эквивалентна следующей задаче, где сумма t наименьших значений в : ф [ т ] ( х ) {\displaystyle f_{[t]}(x)} ф ( х ) {\displaystyle \mathbf {f} (x)} ф [ 1.. т ] ( х ) := ∑ я = 1 т ф [ я ] ( х ) = {\displaystyle f_{[1..t]}(x):=\sum _{i=1}^{t}f_{[i]}(x)=} ф ( х ) {\displaystyle \mathbf {f} (x)} ( Л 2 ) лекс ⁡ макс ф [ 1..1 ] ( х ) , ф [ 1..2 ] ( х ) , … , ф [ 1.. н ] ( х ) при условии х ∈ Х {\displaystyle {\begin{align}(L2)\\\operatorname {lex} \max &&f_{[1..1]}(x),f_{[1..2]}(x),\ldots ,f_{[1..n]}(x)\\{\text{subject to}}&&x\in X\end{align}}}

Эту задачу можно решить итеративно, используя лексикографическую оптимизацию , но число ограничений в каждой итерации t равно C( n , t ) — числу подмножеств размера t . Оно растет экспоненциально с n . Можно свести задачу к другой задаче, в которой число ограничений является полиномом по n .

Для каждого t сумма может быть вычислена как оптимальное значение для следующей задачи с n +1 вспомогательными переменными (неограниченная переменная и неотрицательные переменные для всех j из 1,..., n ) и n дополнительными ограничениями: [5] : Теория 8  [18] Доказательство . Давайте вычислим значения вспомогательных переменных в оптимальном решении. ф [ 1.. т ] ( х ) {\displaystyle f_{[1..t]}(x)} г т {\displaystyle r_{t}} г т , дж {\displaystyle d_{t,j}} ( Л 3 ) макс ( т ⋅ г т − ∑ дж = 1 н г т , дж ) при условии       х ∈ Х , г т − ф дж ( х ) ≤ г т , дж  для всех  дж ∈ [ н ] , г т , дж ≥ 0  для всех  дж ∈ [ н ] . {\displaystyle {\begin{aligned}(L3)\\\max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})\\{\text{при условии}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ для всех }}j\in [n],\\&d_{t,j}\geq 0{\text{ для всех }}j\in [n].\end{aligned}}}

  • Для всех j , должно быть по крайней мере таким же большим, как 0 и , и при этом должно быть минимизировано, так как оно появляется в цели со знаком минус. Следовательно, . Таким образом, цель может быть записана как: . г т , дж {\displaystyle d_{t,j}} г т − ф дж ( х ) {\displaystyle r_{t}-f_{j}(x)} г т , дж = макс ( 0 , г т − ф дж ( х ) ) {\displaystyle d_{t,j}=\max(0,r_{t}-f_{j}(x))} t ⋅ r t − ∑ j = 1 n max ( 0 , r t − f j ( x ) ) {\displaystyle t\cdot r_{t}-\sum _{j=1}^{n}\max(0,r_{t}-f_{j}(x))}
  • Для любого k от 0 до n, если больше наименьших k целевых значений (то есть ), то сумма в правой части содержит ровно k положительных элементов: . В этом случае цель можно записать как: . Обратите внимание, что увеличивается с , когда k < t , и уменьшается с , когда k > t . Следовательно, максимальное значение достигается, когда k = t , то есть больше наименьших t целевых значений; в этом случае цель точно равна , как и утверждается. r t {\displaystyle r_{t}} r t ≥ f [ k ] ( x ) {\displaystyle r_{t}\geq f_{[k]}(x)} ∑ j = 1 k ( r t − f [ j ] ( x ) ) = k ⋅ r t − f [ 1.. k ] ( x ) {\displaystyle \sum _{j=1}^{k}(r_{t}-f_{[j]}(x))=k\cdot r_{t}-f_{[1..k]}(x)} ( t − k ) ⋅ r t + f [ 1.. k ] ( x ) {\displaystyle (t-k)\cdot r_{t}+f_{[1..k]}(x)} ( t − k ) ⋅ r t {\displaystyle (t-k)\cdot r_{t}} r t {\displaystyle r_{t}} r t {\displaystyle r_{t}} r t {\displaystyle r_{t}} f [ 1.. t ] ( x ) {\displaystyle f_{[1..t]}(x)}

Следовательно, задача (L2) эквивалентна следующей задаче лексикографической максимизации: [5] : (32)  ( L 4 ) lex ⁡ max ( t ⋅ r t − ∑ j = 1 n d t , j ) t = 1 n subject to       x ∈ X , r t − f j ( x ) ≤ d t , j  for all  j ∈ [ n ] , d t , j ≥ 0  for all  j ∈ [ n ] . {\displaystyle {\begin{aligned}(L4)\\\operatorname {lex} \max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})_{t=1}^{n}\\{\text{subject to}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ for all }}j\in [n],\\&d_{t,j}\geq 0{\text{ for all }}j\in [n].\end{aligned}}}

Эта задача (L4) имеет дополнительные переменные и дополнительные ограничения. Она может быть решена любым алгоритмом решения лексикографической максимизации , например: последовательным алгоритмом с использованием n линейных программ или лексикографическим симплексным алгоритмом (если цели и ограничения линейны). n 2 + n {\displaystyle n^{2}+n} n 2 {\displaystyle n^{2}}

Приблизительные решения лексимина

Одним из преимуществ алгоритма упорядоченных результатов является то, что его можно использовать даже тогда, когда решатель одной задачи неточен и возвращает только приблизительные решения. В частности, если решатель одной задачи аппроксимирует оптимальное решение одной задачи с мультипликативным множителем α ∈ (0,1] и аддитивным множителем ϵ ≥ 0, то алгоритм возвращает решение, которое аппроксимирует лексиминно-оптимальное решение с мультипликативным множителем α 2 /(1 − α + α 2 ) и аддитивным множителем ϵ/(1 − α + α 2 ). [19]

Алгоритм упорядоченных значений для общих задач

Алгоритм упорядоченных значений работает в любой области, в которой множество возможных значений целевых функций конечно. Он был разработан Огрычаком и Сливиньским. [16] Пусть будет множеством всех значений, которые могут быть возвращены функциями , такими что . Дано решение x и целое число k в {1,.., r }, определим как количество вхождений значения v r в вектор . Тогда задачу lexmaxmin можно сформулировать как следующую задачу лексикографической минимизации: поскольку мы хотим иметь как можно меньше функций, достигающих наименьшего значения; при этом как можно меньше функций, достигающих следующего наименьшего значения; и так далее. Огрычак и Сливиньский [16] показывают, как преобразовать эту нелинейную программу в линейную программу со вспомогательными переменными. В их вычислительных экспериментах алгоритм упорядоченных значений работает намного быстрее, чем алгоритм насыщения и алгоритм упорядоченных результатов. V = { v 1 , … , v r } {\displaystyle V=\{v_{1},\ldots ,v_{r}\}} f 1 , … , f n {\displaystyle f_{1},\ldots ,f_{n}} v 1 < ⋯ < v r {\displaystyle v_{1}<\cdots <v_{r}} h k ( x ) {\displaystyle h_{k}(x)} f 1 ( x ) , … , f n ( x ) {\displaystyle f_{1}(x),\ldots ,f_{n}(x)} ( H 1 ) lex ⁡ min h 1 ( x ) , … , h r − 1 ( x ) subject to x ∈ X {\displaystyle {\begin{aligned}(H1)\\\operatorname {lex} \min &&h_{1}(x),\ldots ,h_{r-1}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}

Алгоритм Берингера для квазивогнутых функций

Берингер [4] представил последовательный алгоритм для оптимизации lexmaxmin [ требуется пояснение ] , когда цели являются квазивыпуклыми функциями , а допустимое множество X является выпуклым множеством .

Средневзвешенное значение

Ягер [20] представил способ представления упорядочения лексимина аналитически с использованием оператора агрегации упорядоченного взвешенного усреднения . Он предполагает, что все объективные значения являются действительными числами от 0 до 1, а наименьшая разница между любыми двумя возможными значениями равна некоторой константе d < 1 (так что значения с разницей меньше d считаются равными). Вес устанавливается приблизительно равным . Это гарантирует, что максимизация взвешенной суммы эквивалентна lexmaxmin. w t {\displaystyle w_{t}} f [ t ] ( x ) {\displaystyle f_{[t]}(x)} d t {\displaystyle d^{t}} ∑ t w t f [ t ] ( x ) {\displaystyle \sum _{t}w_{t}f_{[t]}(x)}

Алгоритмы для дискретных переменных

Если набор векторов дискретен , а область определения достаточно мала, то можно использовать одну из функций, представляющих порядок лексимина, и максимизировать ее с учетом ограничений, используя решатель для задач удовлетворения ограничений .

Но если область велика, то вышеуказанный подход становится невозможным из-за большого количества возможных значений, которые может иметь эта функция: , где m — количество различных значений в области, а n — количество переменных. [21] ( m + n − 1 n ) {\displaystyle {m+n-1 \choose n}}

Бувере и Леметр представляют пять различных алгоритмов для поиска оптимальных по лексимину решений для дискретных задач удовлетворения ограничений: [21]

  1. Метод ветвей и границ основан на ограничении LEXIMIN — ограничении на два вектора x и y , утверждающем, что y лексимин-больше, чем x .
  2. Разветвление на насыщенных подмножествах — нахождение подмножеств переменных, которые должны быть зафиксированы на минимальном значении, и нахождение максимально-минимального значения для других переменных.
  3. Использование ограничения SORT — ограничения на два вектора x и y , говорящего, что y содержит те же элементы, что и x, отсортированные в порядке возрастания. Это ограничение можно эффективно вычислить несколькими алгоритмами. [22] [23]
  4. Использование ограничения ATLEAST.
  5. Использование преобразований максимум-мин.

В их экспериментах наиболее эффективным оказался подход 4 (ATLEAST), за которым следовал 3 (SORT) и 1 (LEXIMIN).

Далл'Альо [24] представляет алгоритм вычисления лексимин-оптимального распределения ресурсов.

Ссылки

  1. ^ abc ВЫЧИСЛЕНИЕ ЯДЕР ПРОСТЫХ ИГР И ЯДРЫШКА ИГР N ЛИЦ (Отчет).
  2. ^ Кольберг, Элон (1972-07-01). «Ядрышко как решение задачи минимизации». Журнал SIAM по прикладной математике . 23 (1): 34–39 . doi :10.1137/0123004. ISSN  0036-1399.
  3. ^ Дрешер, Мелвин (1961). Стратегические игры: теория и приложения. Prentice-Hall – через DTIC.
  4. ^ аб Берингер, Ф.А. (1 июня 1977 г.). «Лексикографическое квазивогнутое многокритериальное программирование». Zeitschrift für Operations Research . 21 (3): 103–116 . doi :10.1007/BF01919766. ISSN  1432-5217. S2CID  27807594.
  5. ^ abcdefgh Огрычак, В.; Пиоро, М.; Томашевский, А. (2005). «Проектирование телекоммуникационных сетей и задача оптимизации по максимуму и минимуму». Журнал телекоммуникаций и информационных технологий . 3 (3): 43–56 . doi : 10.26636/jtit.2005.3.326 . ISSN  1509-4553.
  6. ^ ab Элкинд, Эдит; Пасечник, Дмитрий (2009-01-04). Вычисление ядрышка игр с взвешенным голосованием. Общество промышленной и прикладной математики. С.  327–335 . doi :10.1137/1.9781611973068.37. hdl :10356/93815. ISBN 978-0-89871-680-1.
  7. ^ ab Willson, Stephen J. (1995). "Справедливое деление с использованием линейного программирования" (PDF) . Университет штата Айова (неопубликованная рукопись) .
  8. ^ Поттерс, Джос AM; Тийс, Стеф Х. (1992-02-01). «Ядрышко матричной игры и другие ядрышки». Математика исследования операций . 17 (1): 164– 174. doi :10.1287/moor.17.1.164. hdl : 2066/223732 . ISSN  0364-765X. S2CID  40275405.
  9. ^ Лусс, Ханан (1999-06-01). «О проблемах справедливого распределения ресурсов: лексикографический минимаксный подход». Исследование операций . 47 (3): 361–378 . doi : 10.1287/opre.47.3.361 . ISSN  0030-364X.
  10. ^ Nace, Dritan; Pioro, Michal (2008). «Справедливость по максимуму и минимуму и ее применение к маршрутизации и балансировке нагрузки в сетях связи: учебное пособие». IEEE Communications Surveys & Tutorials . 10 (4): 5– 17. doi :10.1109/SURV.2008.080403. ISSN  1553-877X. S2CID  6595144.
  11. ^ Airiau, Stéphane; Aziz, Haris; Caragiannis, Ioannis; Kruger, Justin; Lang, Jérôme; Peters, Dominik (2019-08-10). «Порционирование с использованием порядковых предпочтений: справедливость и эффективность». Труды 28-й Международной совместной конференции по искусственному интеллекту . IJCAI'19. Макао, Китай: AAAI Press: 11– 17. ISBN 978-0-9992411-4-1.
  12. ^ Бэй, Сяохуэй; Лу, Синьхан; Суксомпонг, Варут (28.06.2022). «Правдивый раздел торта». Труды конференции AAAI по искусственному интеллекту . 36 (5): 4809– 4817. doi : 10.1609/aaai.v36i5.20408 . ISSN  2374-3468. S2CID  245117491.
  13. ^ Огрычак, Влодзимеж (1997-08-01). «О лексикографическом минимаксном подходе к проблемам определения местоположения». Европейский журнал операционных исследований . 100 (3): 566– 585. doi :10.1016/S0377-2217(96)00154-3. ISSN  0377-2217.
  14. ^ Дюбуа, Дидье; Фортемпс, Филипп (1999-10-01). «Вычисление улучшенных оптимальных решений для задач удовлетворения гибких ограничений по максимуму–мину». Европейский журнал исследований операций . 118 (1): 95– 126. doi :10.1016/S0377-2217(98)00307-5. ISSN  0377-2217.
  15. ^ Эрготт, Маттиас (2005-05-18). Многокритериальная оптимизация. Springer Science & Business Media. ISBN 978-3-540-21398-7.
  16. ^ abc Огричак, Влодзимеж; Сливинский, Томаш (2006). «О прямых методах лексикографической мини-максной оптимизации». У Гаврилова Марина ; Джерваси, Освальдо; Кумар, Випин; Тан, Си Джей Кеннет; Таниар, Дэвид; Лагана, Антонио; Мун, Ёнгсонг; Чу, Хёнсын (ред.). Вычислительная наука и ее приложения – ICCSA 2006 . Конспекты лекций по информатике. Том. 3982. Берлин, Гейдельберг: Springer. стр.  802–811 . doi : 10.1007/11751595_85. ISBN 978-3-540-34076-8.
  17. ^ Огрычак, Влодзимеж (1997-08-01). «О лексикографическом минимаксном подходе к проблемам определения местоположения». Европейский журнал операционных исследований . 100 (3): 566– 585. doi :10.1016/S0377-2217(96)00154-3. ISSN  0377-2217.
  18. ^ Огрычак, Влодзимеж; Тамир, Арье (2003-02-14). «Минимизация суммы k наибольших функций за линейное время». Information Processing Letters . 85 (3): 117– 122. doi :10.1016/S0020-0190(02)00370-8. ISSN  0020-0190.
  19. ^ Хартман, Эден; Хассидим, Авинатан; Ауманн, Йонатан; Сегал-Халеви, Эрель (2023), «Аппроксимация лексимином: от одноцелевого к многоцелевому», ECAI 2023 , Frontiers in Artificial Intelligence and Applications, IOS Press, стр.  996–1003 , arXiv : 2303.12506 , doi : 10.3233/FAIA230371 , ISBN 9781643684369
  20. ^ Ягер, Рональд Р. (1997-10-01). «Об аналитическом представлении порядка Leximin и его применении к распространению гибких ограничений». Европейский журнал операционных исследований . 102 (1): 176– 192. doi :10.1016/S0377-2217(96)00217-2. ISSN  0377-2217.
  21. ^ аб Бувере, Сильвен; Леметр, Мишель (01 февраля 2009 г.). «Вычисление лексимин-оптимальных решений в сетях ограничений». Искусственный интеллект . 173 (2): 343–364 . doi : 10.1016/j.artint.2008.10.010 . ISSN  0004-3702.
  22. ^ Guernalec, Noëlle Bleuzen; Colmerauer, Alain (1997). "Сужение 2n-блока сортировок за O (N log n)". В Smolka, Gert (ред.). Principles and Practice of Constraint Programming-CP97 . Lecture Notes in Computer Science. Vol. 1330. Berlin, Heidelberg: Springer. pp.  2– 16. doi :10.1007/BFb0017426. ISBN 978-3-540-69642-1.
  23. ^ Мельхорн, Курт; Тиль, Свен (2000). «Быстрые алгоритмы для согласованности границ сортировки и ограничения Alldifferent». В Dechter, Rina (ред.). Принципы и практика программирования ограничений – CP 2000. Конспект лекций по информатике. Том 1894. Берлин, Гейдельберг: Springer. стр.  306–319 . doi :10.1007/3-540-45349-0_23. ISBN 978-3-540-45349-9.
  24. ^ Dall'Aglio, Marco (2001-05-01). "Проблема оптимизации Дубинса–Спаньера в теории справедливого деления". Журнал вычислительной и прикладной математики . 130 ( 1– 2): 17– 40. Bibcode :2001JCoAM.130...17D. doi : 10.1016/S0377-0427(99)00393-3 . ISSN  0377-0427.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Lexicographic_max-min_optimization&oldid=1271904780"