구성 선형 프로그램

Configuration 선형 프로그램(configuration-LP)은 조합 최적화 문제를 해결하기 위해 사용되는 특정 선형 프로그래밍입니다.그것은 재고 삭감 ^[1]^[2]문제의 맥락에서 도입되었다.이후 bin^[3]^[4] packing 및 작업 ^[5]^[6]스케줄링에 적용되었습니다.구성 LP에는 가능한 구성마다 변수가 있습니다.각각 가능한 항목의 멀티셋은 1개의 빈에 들어갈 수 있습니다(이러한 구성은 패턴이라고도 불립니다).일반적으로 구성 수는 문제 크기에서 기하급수적으로 증가하지만 경우에 따라서는 폴리네만 사용하여 대략적인 해결책을 얻을 수 있습니다.설정의 개수가 한정되어 있습니다.

인빈패킹

일체형 LP

bin packing 문제에서는 크기가 다른 항목이 n개 있습니다.목표는 항목을 최소 수의 빈으로 채우는 것이며, 각 빈에는 최대 B를 포함할 수 있습니다.실현 가능한 설정은 최대 B의 합계를 가진 사이즈 세트입니다.

예:^[7] 항목 크기가 3,3,4,4,4,4이고 B=12라고 가정합니다.다음으로 설정 가능한 것은 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444입니다.사이즈 3의 아이템이 3개뿐이라면 3333 설정을 사용할 수 없습니다.

다양한 크기의 세트(및 그 수)를 S로 나타냅니다.다른 설정(및 그 번호)의 세트를 C로 나타냅니다.S 의 사이즈 및 C 의 설정 c 의 사이즈 마다, 다음을 나타냅니다.

n_s - s 크기의 항목 수.
a_s_,c - 구성 c의 크기 s 발생 횟수.
x_c - 구성이 c인 빈의 수를 나타내는 변수입니다.

다음으로 bin-packing 설정 LP는 다음과 같습니다.

${text{minimize}~~\sum_{c\in C}x_{c}~{\text{subject to}}$
$\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ S 내의 모든 s(-사이즈의 n개 항목 모두 팩됨 $\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ 에_s $\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ c $\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ $\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ $\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ x c $\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ n s (\ $displaystyle$ \ $sum _{c\in C}a_{s,c}x_{$ c}\ $geq n_{$ s $\sum _{c\in C}a_{s,c}x_{c}\geq n_{s}$ })
$x_{c}\in \{0,\ldots ,n\}$ $x_{c}\in \{0,\ldots ,n\}$ 의 모든 c에 대해 $x_{c}\in \{0,\ldots ,n\}$ c $x_{c}\in \{0,\ldots ,n\}$ { 0 , $x_{c}\in \{0,\ldots ,n\}$ , n $}$ { $displaystyle$ x $_$ { $c$ } \ $in$ \ { $0$ , \ $ldots$ , $n$ \ } (최대 $x_{c}\in \{0,\ldots ,n\}$ n개의 빈이 존재하며 각 개별 설정에는 최대 n개의 빈이 있습니다.

구성 LP는 정수 선형 프로그램이기 때문에 일반적으로 NP-hard입니다.게다가, 문제 자체도 일반적으로 매우 크다. 즉, C 변수와 S 제약 조건이 있다.만약 가장 작은 사이즈는eB(0,1 일부가 e를 위해(에서))다음 각 쓰레기 통에서 1/e 항목 있는델 수 있는 구성을 갖추C~ S1/e, 만약 e, e로 여겨진다(일정한 정수 LP철저한 검색으로:대부분의 S1/e 구성에서, 각 구성에 있어 거기에 해결될 수 있는 매우 클 수 있는 번호입니다.이다최대 n개의 가능한 값이 있으므로 확인할 수 있는 $n^{S^{1/e}}$ $n^{S^{1/e}}$ 의 S $n^{S^{1/e}}$ 1/ $(\$ n $^{S^{1/e}})$ 조합이 $n^{S^{1/e}}$ 있습니다.각 조합에 대해 S 구속조건을 확인해야 하므로 실행시간은 $S\cdot n^{S^{1/e}}$ $S\cdot n^{S^{1/e}}$ S $S\cdot n^{S^{1/e}}$ / $S\cdot n^{S^{1/e}}$ \ $displaystyle$ S \ $cdot$ n^ { $S ^$ { 1 / e $}$ 이며, S, e가 ^[7]일정할 때 n의 다항식이다.

단, 이 ILP는 몇 가지 근사 알고리즘의 기초가 됩니다.이러한 알고리즘의 주요 아이디어는 원래 인스턴스를 S가 작고 e가 크므로 C가 상대적으로 작은 새로운 인스턴스로 줄이는 것입니다.그 후, ILP는 완전 검색(S, C가 충분히 작은 경우) 또는 분수 LP로 완화하는 방법으로 해결할 수 있습니다.

프랙셔널 LP

bin-packing의 부분 구성 LP 이것은 위의 ILP의 선형 프로그래밍 완화입니다. $x_{c}\in \{0,\ldots ,n\}$ $x_{c}\in \{0,\ldots ,n\}$ $x_{c}\in \{0,\ldots ,n\}$ $x_{c}\in \{0,\ldots ,n\}$ $x_{c}\in \{0,\ldots ,n\}$ { $x_{c}\in \{0,\ldots ,n\}$ 0 , $x_{c}\in \{0,\ldots ,n\}$ , n $}$ { $displaystyle$ $x$ $x_{c}\in \{0,\ldots ,n\}$ _ { $c$ } \ $in$ \ { $0$ , \ $ldots$ $x_{c}\in \{0,\ldots ,n\}$ , $n$ \ } $은$ $x_{c}\geq 0$ $x_{c}\geq 0$ 0 으로 $x_{c}\geq 0$ 대체됩니다.즉, 각 설정은 소수만큼 사용할 수 있습니다.이완은 Gilmore와 Gomory에 ^[2]의해 처음 제시되었으며, 종종 Gilmore-Gomory 선형 프로그램으로 ^[8]불린다.

예: 크기가 3인 항목이 31개이고 크기가 4인 항목이 7개이고 빈 크기가 10이라고 가정합니다.설정은 4, 44, 34, 334, 3, 333, 333 입니다.제약 조건은 [0,0,1,2,1,2,3]*x=31 및 [1,2,1,1,0,0,0]*x=7입니다.프랙셔널 LP에 대한 최적의 해는 [0,0,0,7,0,0,17/3] 즉, 구성 334의 빈은 7개, 구성 333의 빈은 17/3이다.필요한 설정은 2개뿐입니다.

즉, 프랙셔널 LP는 다음과 같이 쓸 수 있습니다.

${text{f}~\mathbf {1} \cdot \mathbf {x}~~{\text{s.t}}.}~~A\mathbf {x} \geq \mathbf {n} ~~{\text{and}} ~~\mathbf {x} \geq 0$

여기서 1은 C 사이즈의 벡터(1, ...1)이고, A는 각 열이 단일 구성을 나타내는 S-by-C 행렬이며, n은 벡터(n₁, ...n_S)입니다.

프랙셔널 LP 해결

적분성 제약이 없는 선형 프로그램은 변수 및 제약의 수에서 시간 다항식으로 해결할 수 있습니다.문제는 프랙셔널컨피규레이션 LP의 변수 수가 가능한 Configuration의 수와 동일하다는 것입니다.이는 매우 클 수 있습니다.Karmarkar와 Karp는^[9] 이 문제를 해결하는 알고리즘을 제시합니다.

첫째, 부분 LP의 이중 선형 프로그램을 구성합니다.

${\text{maximize}}~~\mathbf {n} \cdot \mathbf {y} ~~~{\text{s.t.}}~~A^{T}\mathbf {y} \leq \mathbf {1} ~~~{\text{and}}~~\mathbf {y} \geq 0$ ${\text{maximize}}~~\mathbf {n} \cdot \mathbf {y} ~~~{\text{s.t.}}~~A^{T}\mathbf {y} \leq \mathbf {1} ~~~{\text{and}}~~\mathbf {y} \geq 0$ $}~~A^{T}\mathbf$ {y} \ $leq \mathbf$ {1} $~~{\text{and}}~\mathbf$ {y} \ $geq$ 0}.

여기에는 S변수₁ y, ..., 및_S C의 제약조건이 있습니다.각 설정 c에 $A^{c}\cdot y\leq 1$ $A^{c}\cdot y\leq 1$ c c $A^{c}\cdot y\leq 1$ ${\$ 1 \ $cdot$ y \ $leq$ 1 $A^{c}\cdot y\leq 1$ 。 $여기$ 서 A $A^{c}$ c \ $display$ $style$ A^ { $c$ }는 $A^{c}$ 설정 c 3을 나타내는 A의 컬럼입니다.경제적인 ^[9]해석은 다음과 같습니다.각 크기 s에 대해 음이 아닌 가격_s y를 결정해야 합니다.우리의 이익은 모든 품목의 총 가격입니다.각 구성의 아이템의 총가격이 최대 1이라는 제약조건에 따라 이익을 극대화하고 싶습니다.

둘째, 모든 제약조건을 나열할 필요는 없고 분리 오라클만 있으면 되는 타원체 메서드의 변형을 적용합니다.분리 오라클은 벡터 y가 주어졌을 때 그것이 가능하다고 단언하거나 그것이 위반하는 제약을 찾아내는 알고리즘입니다.듀얼 LP의 분리 오라클은 크기 s와 값 y의 배낭 문제를 해결함으로써 구현할 수 있습니다.배낭 문제의 최적 솔루션이 최대 1의 총값을 갖는 경우 y는 실현 가능합니다.배낭 문제의 최적 솔루션이 1보다 크면 y는 실현 불가능하며 배낭 문제의 최적 솔루션은 다음과 같은 구성을 식별합니다.제약조건을 위반했습니다.

셋째, 배낭 문제에 대한 근사 솔루션을 사용하면 이중 LP에 대한 근사 솔루션을 얻을 수 있으며, 이로부터 원시 LP에 대한 근사 솔루션을 얻을 수 있습니다. Karmarkar-Karp bin 패킹 알고리즘을 참조하십시오.

전체적으로 모든 허용 계수 h에 대해 최대 LOPT(I) + h의 기본적인 실현 가능한 비용 솔루션을 찾고 시간 내에 실행됩니다.

$O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ ( $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ log $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ 2 $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ n $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ h $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ ) + $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ 4 $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ log $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ S $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ log $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ s $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ h $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ S $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ h $O\left(S^{8}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ ） \ $displaystyle O$ \ $left$ ( $S$ ^ 8 } \ $log$ { $S$ } \ log $^2}$ ( { \ $frac$ { Sn } { eh } ) + \ $fracS$ \ $log$ { 4 $}$

여기서 S는 다른 크기의 수, n은 다른 항목의 수, 가장 작은 항목의 크기는 eB입니다.특히 e / 1/n 및 h=1인 경우 알고리즘은 O $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ ( S $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ log $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ 2 $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ n + $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ S log $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ n $O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)$ ) { $display style$ O $\left$ ( $S }$ \ log { $S }$ \ log { $S$ }{ $n }$ { $n$ } : LOPT + 1빈을 가진 솔루션을 찾습니다.

$O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ ( $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ log $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ 2 $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ n $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ h $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ ) + $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ 4 $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ log $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ S $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ log $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ s $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ h $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ e $O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)$ ） \ $displaystyle$ O \ $left$ ( $S$ ^ 7 $}$ \ $log$ { S } \ log $^2}$ ( { \ $frac$ { $Sn$ } { eh } ) + \ $fracS$ \ $log$ { $4 }$

소수점 LP 반올림

Karmarkar와 Karp는 프랙셔널 LP를 적분 LP에 대한 대략적인 해법으로 반올림하는 방법을 추가로 개발했습니다. Karmarkar-Karp bin 패킹 알고리즘을 참조하십시오.그 증거는 이 LP의 가법적 일체성 갭이 O(log²(n)에 있음을 보여준다.나중에, Hoberg와 Rothvoss는^[10] 그들의 결과를 개선했고 적분성 갭이 O(log(n)에 있다는 것을 증명했다.적분성 갭에서 가장 잘 알려진 하한이 상수 δ(1)입니다.정확한 통합 갭을 찾는 것은 미해결 문제입니다.

In bin covering(빈 커버)

쓰레기통 덮개 문제에서는 크기가 다른 품목이 n개 있습니다.목표는 항목을 최대 수의 빈으로 채우는 것입니다. 각 빈에는 최소 B가 포함되어야 합니다.이 문제의 자연스러운 설정 LP는 다음과 같습니다.

${text{f}~\mathbf {1} \cdot \mathbf {x}~~{\text{s.t}}.}~~A\mathbf {x} \leq \mathbf {n} ~~{\text{and}} ~~\mathbf {x} \geq 0$

여기서 A는 합계가 B 이상인 항목의 모든 구성을 나타냅니다(포함 최소 구성만 사용할 수 있습니다).이 LP의 문제는 빈 커버 문제에서 작은 아이템은 최적의 솔루션을 위해 필수적이기 때문에 작은 아이템을 취급하는 것이 문제가 된다는 것입니다.작은 아이템을 허용하면 구성 수가 카르마르카 및 카르프 기술에 비해 너무 많을 수 있습니다.Csirik, Johnson 및^[11] Kenyon이 대체 LP를 제공합니다.첫째, 작은 항목이라고 불리는 항목 집합을 작은 항목이라고 합니다.T를 모든 작은 아이템의 총 사이즈로 합니다.그런 다음 합계가 2 미만인 모든 구성을 나타내는 행렬 A를 작성합니다.그런 다음 위의 LP에 대해 한 가지 추가 제약이 있습니다.

{text{s.t}~\mathbf {1} \cdot \mathbf {x}~{\text{s.t}}.}}

A\mathbf {x} \leq \mathbf {n}

\displaystyle \sum _{c\in C:sum(c) <B}(B-sum(c)\cdot x_{c}\leq T}

\displaystyle \mathbf {x} \geq 0}

추가적인 제약은 빈의 "빈 공간"을 작은 항목으로 채울 수 있도록 보장합니다.이 LP의 듀얼은 더 복잡하여 간단한 배낭 문제 분리 오라클로는 해결할 수 없습니다.Csirik, Johnson 및^[11] Kenyon은 1/epsilon에서 대략적으로 시간 지수적으로 해결하기 위한 다른 방법을 제시합니다.얀센과 솔리스-오바는^[12] 1/epsilon에서 대략적으로 시간 지수적으로 해결할 수 있는 개선된 방법을 제시한다.

기계 스케줄링 중

관련 없는 머신의 스케줄링 문제에서는 n개의 다른 작업을 처리해야 하는 머신이 몇 개 있습니다.machine i가 j작업을 처리할 때 시간이 걸립니다_i_,j.목표는 기계의 최대 완료 시간을 가능한 한 단축하도록 기계 간에 작업을 분할하는 것입니다.이 문제의 결정 버전은 시간 T가 주어졌을 때 모든 기계의 완료 시간이 최대 T인 파티션이 있는가?

각 기계 i에 대해 기계 i로 처리할 수 있는 작업의 서브셋이 T만큼 많다.이러한 각 서브셋을 머신i 의 설정이라고 부릅니다.주어진 시간 T에서 기계 i의 모든 구성 세트를 C(T)로_i 나타냅니다.C(T)의_i 각 머신 i 및 설정 c에 대해 변수 $x_{i,c}$ i $x_{i,c}$ (\ $displaystyle x_{i,c})$ 를 $x_{i,c}$ 정의합니다.이 $x_{i,c}$ x i는 실제 머신 i에서 사용되는 설정이 c인 경우 1과 같고, 그렇지 않은 경우 0과 같습니다.다음으로 LP의 제약사항은 다음과 같습니다.

$\sum _{c\in C_{i}(T)}x_{i,c}=1$ § $\sum _{c\in C_{i}(T)}x_{i,c}=1$ ∈ $\sum _{c\in C_{i}(T)}x_{i,c}=1$ $\sum _{c\in C_{i}(T)}x_{i,c}=1$ ( $\sum _{c\in C_{i}(T)}x_{i,c}=1$ T ) $\sum _{c\in C_{i}(T)}x_{i,c}=1$ , c $=$ $1$ ( \ $displaystyle$ \ $sum _$ { c \ $in C$ _ { $i$ } ( T )x $_$ { i , c $\sum _{c\in C_{i}(T)}x_{i,c}=1$ $\sum _{c\in C_{i}(T)}x_{i,c}=1$ } $=$ 1 ） $\sum _{c\in C_{i}(T)}x_{i,c}=1$
$\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ ; $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ = 1 m $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ c $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ , c $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ ( $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ ) $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ i , c $=$ $1$ \ $displaystyle$ \ $sum _$ { i $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ = $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ 1 $^{$ m } \ $sum _$ { c \ $ni j$ , c \ $in C$ _ { i } ( T ) $x _$ { i , c $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ $}$ = 1 $\sum _{i=1}^{m}\sum _{c\ni j,c\in C_{i}(T)}x_{i,c}=1$ } ;
$x_{i,j}\in \{0,1\}$ x $x_{i,j}\in \{0,1\}$ , j $x_{i,j}\in \{0,1\}$ { $x_{i,j}\in \{0,1\}$ , $}$ { $displaystyle x$ _ { $i$ , $j$ } \ $in$ \ { $0$ , $1$ \ } 。

특성.

관련성이 없는 머신스케줄링에 대한 설정 LP의 통합 차이는 ^[5]2입니다.

「」를 참조해 주세요.

고다중성 빈 패킹

레퍼런스

^ Eisemann, Kurt (1957-04-01). "The Trim Problem". Management Science. 3 (3): 279–284. doi:10.1287/mnsc.3.3.279. ISSN 0025-1909.
^ ^a ^b 길모어 P.C., R.E. 고모리(1961년)커팅 스톡 문제에 대한 선형 프로그래밍 접근법입니다.Operations Research 9: 849-859
^ Karmarkar, Narendra; Karp, Richard M. (1982-11-01). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982): 312–320. doi:10.1109/SFCS.1982.61. S2CID 18583908.
^ Bansal, Nikhil; Caprara, Alberto; Sviridenko, Maxim (2006-10-01). "Improved approximation algorithms for multidimensional bin packing problems". 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06): 697–708. doi:10.1109/FOCS.2006.38. ISBN 0-7695-2720-5. S2CID 7690347.
^ ^a ^b Verschae, José; Wiese, Andreas (2014-08-01). "On the configuration-LP for scheduling on unrelated machines". Journal of Scheduling. 17 (4): 371–383. doi:10.1007/s10951-013-0359-4. ISSN 1099-1425. S2CID 34229676.
^ Knop, Dušan; Koutecký, Martin (2020-03-04). "Scheduling Kernels via Configuration LP". arXiv:2003.02187 [cs.DS].
^ ^a ^b Claire Mathieu. "Approximation Algorithms Part I, Week 3: bin packing". Coursera. Archived from the original on 2021-07-15.
^ Rothvoß, T. (2013-10-01). "Approximating Bin Packing within O(log OPT * Log Log OPT) Bins". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science: 20–29. arXiv:1301.4010. doi:10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID 15905063.
^ ^a ^b Karmarkar, Narendra; Karp, Richard M. (November 1982). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982): 312–320. doi:10.1109/SFCS.1982.61. S2CID 18583908.
^ Hoberg, Rebecca; Rothvoss, Thomas (2017-01-01), "A Logarithmic Additive Integrality Gap for Bin Packing", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 2616–2625, doi:10.1137/1.9781611974782.172, ISBN 978-1-61197-478-2, S2CID 1647463, retrieved 2021-02-10
^ ^a ^b Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Better approximation algorithms for bin covering". Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '01. Washington, D.C., USA: Society for Industrial and Applied Mathematics: 557–566. ISBN 978-0-89871-490-6.
^ Jansen, Klaus; Solis-Oba, Roberto (2002-11-21). "An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering". Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC '02. Berlin, Heidelberg: Springer-Verlag. 2518: 175–186. doi:10.1007/3-540-36136-7_16. ISBN 978-3-540-00142-3.

[1] Eisemann, Kurt (1957-04-01). "The Trim Problem". Management Science. 3 (3): 279–284. doi:10.1287/mnsc.3.3.279. ISSN 0025-1909.

[Gilmore61-2] 길모어 P.C., R.E. 고모리(1961년)커팅 스톡 문제에 대한 선형 프로그래밍 접근법입니다.Operations Research 9: 849-859

[:1-3] Karmarkar, Narendra; Karp, Richard M. (1982-11-01). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982): 312–320. doi:10.1109/SFCS.1982.61. S2CID 18583908.

[4] Bansal, Nikhil; Caprara, Alberto; Sviridenko, Maxim (2006-10-01). "Improved approximation algorithms for multidimensional bin packing problems". 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06): 697–708. doi:10.1109/FOCS.2006.38. ISBN 0-7695-2720-5. S2CID 7690347.

[:0-5] Verschae, José; Wiese, Andreas (2014-08-01). "On the configuration-LP for scheduling on unrelated machines". Journal of Scheduling. 17 (4): 371–383. doi:10.1007/s10951-013-0359-4. ISSN 1099-1425. S2CID 34229676.

[6] Knop, Dušan; Koutecký, Martin (2020-03-04). "Scheduling Kernels via Configuration LP". arXiv:2003.02187 [cs.DS].

[:2-7] Claire Mathieu. "Approximation Algorithms Part I, Week 3: bin packing". Coursera. Archived from the original on 2021-07-15.

[:22-8] Rothvoß, T. (2013-10-01). "Approximating Bin Packing within O(log OPT * Log Log OPT) Bins". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science: 20–29. arXiv:1301.4010. doi:10.1109/FOCS.2013.11. ISBN 978-0-7695-5135-7. S2CID 15905063.

[:12-9] Karmarkar, Narendra; Karp, Richard M. (November 1982). "An efficient approximation scheme for the one-dimensional bin-packing problem". 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982): 312–320. doi:10.1109/SFCS.1982.61. S2CID 18583908.

[:3-10] Hoberg, Rebecca; Rothvoss, Thomas (2017-01-01), "A Logarithmic Additive Integrality Gap for Bin Packing", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, Society for Industrial and Applied Mathematics, pp. 2616–2625, doi:10.1137/1.9781611974782.172, ISBN 978-1-61197-478-2, S2CID 1647463, retrieved 2021-02-10

[:24-11] Csirik, Janos; Johnson, David S.; Kenyon, Claire (2001-01-09). "Better approximation algorithms for bin covering". Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '01. Washington, D.C., USA: Society for Industrial and Applied Mathematics: 557–566. ISBN 978-0-89871-490-6.

[:32-12] Jansen, Klaus; Solis-Oba, Roberto (2002-11-21). "An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering". Proceedings of the 13th International Symposium on Algorithms and Computation. ISAAC '02. Berlin, Heidelberg: Springer-Verlag. 2518: 175–186. doi:10.1007/3-540-36136-7_16. ISBN 978-3-540-00142-3.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Search

구성 선형 프로그램

네임스페이스

더

목차

인빈패킹

일체형 LP

프랙셔널 LP

프랙셔널 LP 해결

소수점 LP 반올림

In bin covering(빈 커버)

기계 스케줄링 중

특성.

「」를 참조해 주세요.

레퍼런스

Search

구성 선형 프로그램

인빈패킹

일체형 LP

프랙셔널 LP

프랙셔널 LP 해결

소수점 LP 반올림

In bin covering(빈 커버)

기계 스케줄링 중

특성.

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.