정수 프로그래밍

정수 프로그래밍 문제는 변수의 일부 또는 전부가 정수로 제한되는 수학적 최적화 또는 실현 가능성 프로그램입니다.많은 설정에서 이 용어는 목적 함수와 제약 조건(정수 제약 조건 제외)이 선형인 정수 선형 프로그래밍(ILP)을 나타냅니다.

정수 프로그래밍은 NP-완전입니다.특히, 0-1 정수 선형 프로그래밍의 특수한 경우, 알 수 없는 것은 이진수이며 제한사항만 충족되어야 합니다. 이는 Karp의 21개의 NP-완전 문제 중 하나입니다.

일부 결정 변수가 이산적이지 않은 경우 이 문제는 혼합 정수 프로그래밍 ^[1]문제로 알려져 있습니다.

ILP의 표준 및 표준 형식

정수 선형 프로그래밍에서 표준 형식은 표준 형식과 다릅니다.정규 형식의 정수 선형 프로그램은 다음과 같이 표현됩니다(결정되는 $\mathbf {x}$ 은 x $\mathbf {x}$ {\ $displaystyle \mathbf {x}$ 벡터입니다 $\mathbf {x}$ ).^[2]

{begin {aligned}&{\text {maximize}&\mathbf {c}^{\mathrm {T}}\mathbf {x}\&A\mathbf {x}\leq \mathbf {b},\&&\mathbf {0geb} \mathb

표준 형식의 ILP는 다음과 같이 표현됩니다.

\displaystyle {text {aligned}&{\text {t}&\mathbf {c}^{\mathbf {x}\&{\text {t}}\mathbf {x} +\mathbf {s} =\mathbf {b},\&\&\mathbf {c} \mathbf {x}

$\mathbf {c} ,\mathbf {b}$ 서 $\mathbf {c} ,\mathbf {b}$ c , $\mathbf {c} ,\mathbf {b}$ {c $} ,\mathbf$ { $b}$ 은 $A$ 이고A {\ $displaystyle$ A $}$ 는 $A$ 행렬이며 모든 엔트리가 정수입니다.선형 프로그램과 마찬가지로 표준 형식이 아닌 ILP는 부등식을 제거하고 느슨한 변수( $\displaystyle \mathbf$ {s $\mathbf {s}$ 를 도입하고 부호 제약이 없는 변수를 2개의 부호 제약 변수의 차이로 대체하여 표준 형식으로 변환할 수 있다.

예

LP 릴렉스 기능이 있는 IP 폴리토프

오른쪽 그림은 다음과 같은 문제를 보여줍니다.

{ begin { aligned }\x+y&\leq 1\3x+2y&\leq 12\x,y&\geq 0\x,y&\in \mathbb {Z} \endaligned

실행 가능한 정수점은 빨간색으로 표시되고 빨간색 점선은 볼록 선체를 나타냅니다. 볼록 선체는 이러한 모든 점을 포함하는 가장 작은 볼록 다면체입니다.파란색 선은 좌표축과 함께 LP 완화 다면체를 정의하며, 이는 적분 제약 없이 부등식으로 제공됩니다.최적화의 목적은 다면체에 닿은 상태에서 검은색 점선을 위쪽으로 이동하는 것입니다.정수 문제의 최적 해결 방법은 둘 다 목표값이 2인 포인트 $2)$ 와 $(1,2)$ $,$ $)$ 입니다 $(2,2)$ .이완의 독특한 최적치는 ( $)$ {{ $디스플레이$ 스타일 $(1.8, 2.8)}$ 이며 $(1.8,2.8)$ $(1.8,2.8)$ 목표값은 2.8입니다.완화의 해를 가장 가까운 정수로 반올림하면 ILP에는 적합하지 않습니다.

NP-경도 증명

다음은 최소 정점 커버에서 NP-경도의 증명 역할을 하는 정수 프로그래밍으로 축소된 것입니다.

$G=(V,E)$ $=$ ( V $G=(V,E)$ , $G=(V,E)$ ) { $displaystyle$ G=( $V, E)}$ 을 $G=(V,E)$ (를) 무방향 그래프라고 $G=(V,E)$ .다음과 같이 선형 프로그램을 정의합니다.

(\displaystyle {begin{aligned}\min \sum _{v}y_{v}\y_{u}&\geq 1&\forall uv\in E\y_{v}&\forall v\in V\y_{v}&\mathbbb Z&\for)

제약조건에 의해 y $y_{v}$ {\ $style y_{v}$ 가 $y_{v}$ 0 또는 1로 $y_{v}$ 되기 때문에 정수 프로그램에 대한 실현 가능한 해법은 모두 정점의 서브셋입니다.첫 번째 제약조건은 모든 에지의 끝점이 적어도 하나 이상 이 서브셋에 포함된다는 것을 의미합니다.따라서 솔루션은 꼭지점 덮개를 설명합니다.또한 정점 커버 C를 지정하면 y $y_{v}$ v {\ $displaystyle y_{v}$ 는 $y_{v}$ $v\in C$ 의 v $v\in C$ C {\ $displaystyle$ v $\in$ C $v\in C$ }에 $v\in C$ 대해 1로, 임의의 $v\not \in C$ C {\ $displaystyle$ v $\not\in$ C $}$ 에 $v\not \in C$ 대해 0으로 설정할 수 있으므로 정수 프로그램에 대한 실현 가능한 솔루션을 얻을 수 있습니다.따라서 y $y_{v}$ ${\$ 의 $y_{v}$ 합을 최소화하면 최소 정점 ^[3]커버도 찾을 수 있습니다.

변종

Mixed-integer Linear Programming(MILP; 혼합 정수 선형 프로그래밍)에서는 일부 변수( $\$ 만 정수로 제한되고 다른 변수는 정수 이외의 변수가 허용됩니다.

제로 원 선형 프로그래밍(또는 이진 정수 프로그래밍)은 변수가 0 또는 1로 제한되는 문제를 포함합니다.모든 경계 정수 변수는 이진 ^[4]변수의 조합으로 표현될 수 있습니다.예를 들어 정수 $0\leq x\leq U$ 0 ${\displaystyle$ 0 $\leq$ x\ $leq$ U $0\leq x\leq U$ 의 경우 변수는 $\lfloor \log _{2}U\rfloor +1$ 2 $\lfloor \log _{2}U\rfloor +1$ U $\lfloor \log _{2}U\rfloor +1$ + $\lfloor \log _{2}U\rfloor +1$ { $displaystyle \lfloor _{2}U\rfloor$ +1} $바이너리$ 변수를 사용하여 표시할 수 있습니다.

{\displaystyle x=x_{1}+2x_{2}+4x_{3}+\cdots+2^{\lfloor \log_{2}U\rfloor +1}x_{\lfloor\{\lfloor \log_{2}U\rfloor +1}.

적용들

문제를 선형 프로그램으로 모델링할 때 정수 변수를 사용하는 이유는 크게 두 가지입니다.

정수 변수는 정수만 될 수 있는 수량을 나타냅니다.예를 들어, 3.7대의 자동차를 만드는 것은 불가능하다.
정수 변수는 결정을 나타내므로(예: 가장자리를 그래프에 포함할지 여부) 값 0 또는 1만 적용해야 합니다.

이러한 고려사항은 실제로 자주 발생하므로 정수 선형 프로그래밍을 많은 애플리케이션 영역에서 사용할 수 있습니다. 그 중 일부는 아래에 간략히 설명되어 있습니다.

생산 계획

혼합 정수 프로그래밍은 잡샵 모델링을 포함한 산업 생산에서 많은 응용 분야를 가지고 있습니다.농업 생산 계획에서 발생하는 한 가지 중요한 예는 자원을 공유할 수 있는 여러 작물의 생산량을 결정하는 것이다(예: 토지, 노동, 자본, 종자, 비료 등).가능한 목표는 가용 리소스를 초과하지 않고 총 생산량을 극대화하는 것입니다.경우에 따라서는 선형 프로그램으로 표현할 수 있지만 변수는 정수여야 합니다.

스케줄

이러한 문제에는 운송 네트워크에서의 서비스 및 차량 스케줄링이 포함됩니다.예를 들어, 버스나 지하철을 개별 노선에 할당하여 시간표를 맞출 수 있도록 하고 운전기사를 배치하는 문제가 발생할 수 있습니다.여기서 바이너리 결정 변수는 버스 또는 지하철이 노선에 할당되는지 여부와 기관사가 특정 열차 또는 지하철에 할당되는지 여부를 나타냅니다.제로원 프로그래밍 기술은 프로젝트가 상호 배타적이거나 기술적으로 상호의존적인 프로젝트 선택 문제를 해결하기 위해 성공적으로 적용되었습니다.이는 모든 결정 변수가 정수인 정수 프로그래밍의 특수한 경우에 사용됩니다.값은 0 또는 1로 가정할 수 있습니다.

영역 분할

영토분할 또는 지역구획 문제는 지역구별로 분할하여 서로 다른 기준이나 제약을 고려하면서 일부 운영을 계획하는 것입니다.이 문제에 대한 몇 가지 요구사항은 인접성, 콤팩트성, 균형 또는 형평성, 자연경계의 존중, 그리고 사회경제적 동질성이다.이러한 유형의 문제에는 정치 지역구, 학교 지역구, 보건 서비스 지역구 및 폐기물 관리 지역구가 포함됩니다.

통신망

이러한 문제의 목적은 미리 정의된 통신 요건을 충족하고 네트워크의 총 비용을 최소화할 ^[5]수 있도록 설치하는 회선 네트워크를 설계하는 것입니다.이를 위해서는 다양한 회선의 용량 설정과 함께 네트워크의 토폴로지를 모두 최적화해야 합니다.많은 경우 용량은 정수량으로 제한됩니다.일반적으로 사용되는 기술에 따라 정수 또는 이진 변수와 선형 부등식으로 모델링할 수 있는 추가적인 제한이 있습니다.

셀룰러 네트워크

GSM 모바일 네트워크에서의 주파수 계획 태스크는 사용자에게 서비스를 제공하고 ^[6]안테나 간의 간섭을 최소화하기 위해 안테나 간에 사용 가능한 주파수를 분배하는 것을 포함합니다.이 문제는 2진수 변수가 안테나에 주파수가 할당되어 있는지 여부를 나타내는 정수 선형 프로그램으로 공식화할 수 있습니다.

기타 응용 프로그램

알고리즘

ILP를 해결하는 간단한 방법은 x가 정수라는 제약을 제거하고 대응하는 LP(ILP의 LP 완화라고 함)를 해결한 다음 솔루션의 엔트리를 LP 완화로 반올림하는 것입니다.그러나 이 솔루션은 최적이지 않을 뿐만 아니라 실현 가능하지 않을 수도 있습니다. 즉, 일부 제약 조건을 위반할 수도 있습니다.

완전한 단일성을 사용하다

일반적으로 LP 완화에 대한 솔루션은 $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ $A\mathbf {x} =\mathbf {b}$ $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ $A\mathbf {x} =\mathbf {b}$ $A\mathbf {x} =\mathbf {b}$ {\ $displaystyle$ A $\mathbf$ ${x}$ $=$ b {\displaystyle A $\mathbf$ $A\mathbf {x} =\mathbf {b}$ { $c} }$ 의 $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ 형식을 가진 경우 통합될 수 $A\mathbf {x} =\mathbf {b}$ . $A$ 서 ILP는 A x = b $\$ $A\$ mathbf { $x} =\mathbf$ { $c}$ 입니다 $A\mathbf {x} =\mathbf {b}$ . $모든$ 정수 엔트리를 $가지며$ A $(\displaystyle$ A $)$ 는 $A$ 완전히 단일 모듈형입니다. 그러면 모든 기본 실행 가능한 솔루션이 필수적입니다.이것에 의해, 심플렉스 알고리즘에 의해서 반환되는 해는 적분이 보증된다.모든 기본 실현 가능한 해법이 적분임을 나타내려면 $\mathbf {x}$ x $(\$ $displaystyle$ \ $mathbf$ $\mathbf {x}$ {x $})$ 를 임의의 기본 실현 가능한 해법으로 합니다 $.$ $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ $(\$ displaystyle \ $mathbf$ { $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ $})$ 는 $\mathbf {x}$ $A\mathbf {x} =\mathbf {b}$ $\mathbf {x}$ 하므로 A x = b $(\displaystyle$ A $\mathbf$ {x}) = \ $mathbf$ $\mathbf {x}$ { $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ $}$ $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ $}$ $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ 1 $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ )로 합니다. ${\$ $displaystyle$ $\mathbf {x} _{0}=[x_{n_{1},x_cdots,x_{n_{j}}}$ 는 $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ 기본 $\mathbf {x}$ x의 기본 열에 대응하는 요소입니다.\ $displaystyle$ $\mathbf {x$ 의 정의에 따르면, 일부 정사각형 하위 $B$ 가 있습니다 $.$ $B\mathbf {x} _{0}=\mathbf {b}$ $B\mathbf {x} _{0}=\mathbf {b}$ $B\mathbf {x} _{0}=\mathbf {b}$ 0 $=$ b {\ $displaystyle B\mathbf$ {x} _ ${0$ }=\ $mathbf {b}$ 。

B $($ $스타일$ B $)$ 의 $B$ 열은 선형 $B$ 이고 B $(디스플레이 스타일$ B $)$ 는 $B$ 정사각형이므로 B $(디스플레이 스타일$ B $)$ 는 $B$ 비음절이며, 따라서 B $(디스플레이 스타일$ B $)$ 는 $B$ 단모듈러이므로 $\det(B)=\pm 1$ $=$ ± $(디스플레이$ 스타일 $\det(B$ )=\ $pm$ 1)도 $\det(B)=\pm 1$ B $(디스플레이$ 스타일 B)이므로 $B$ ,가역적이므로 $\mathbf {x} _{0}=B^{-1}\mathbf {b}$ 0 $=$ - $\mathbf {x} _{0}=B^{-1}\mathbf {b}$ {\ $displaystyle \mathbf {x} _{0$ }= $B^{-1}\mathbf {b$ 정의에 $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ B - $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ d $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ d d d d $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ ( B ) $=$ ± $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ $B^{-1}={\frac {B^{\mathrm {adj} }}{\det(B)}}=\pm B^{\mathrm {adj} }$ （ $displaystyle$ B^ {-1} = $fraccram$ { $b}$ {f {f {b}}}}}}}.는 $B의$ 관계를 나타내고 있으며 $,$ $B는$ 일체형이기 $B$ 에 일체형입니다.그러므로,

{begin{aligned}&\rightarrow B^{-1}=\pm B^{\mathrm {arg}}{\text{는 정수입니다.}}\\&\오른쪽 화살표 x_{0}=B^{-1}b{\text{\text}는 적분입니다.}}\&\rightarrow {실현 가능한 모든 기본 솔루션은 필수적입니다.}}\end {aligned}

따라서 ILP의 $행렬$ A $(\style$ A $)$ 가 $A$ ILP 알고리즘을 사용하는 것이 아니라 완전히 단변형일 경우 심플렉스 방법을 사용하여 LP 완화를 풀 수 있으며, 그 해는 정수가 된다.

정확한 알고리즘

$행렬$ A $(\displaystyle$ A $)$ 가 $A$ 완전히 단일화되지 않은 경우 정수 선형 프로그램을 정확하게 해결하기 위해 사용할 수 있는 다양한 알고리즘이 있습니다.알고리즘의 한 클래스는 LP 완화를 해결한 후 솔루션을 정수 실현 가능한 점을 배제하지 않고 정수가 되도록 유도하는 선형 구속조건을 추가하여 작동하는 절단 평면 방법이다.

또 다른 알고리즘 클래스는 분기 및 바운드 방식의 변형입니다.예를 들어, 분기 및 바운드 및 절단 평면 방법을 모두 결합한 분기 및 절단 방법입니다.분기 및 바운드 알고리즘은 절단면만 사용하는 알고리즘에 비해 여러 가지 이점이 있습니다.한 가지 장점은 알고리즘을 조기에 종료할 수 있고 적어도 하나의 통합 솔루션이 발견되면 실현 가능한 솔루션을 반환할 수 있다는 것입니다.또, LP완화의 해법을 이용해, 반환되는 해법이 최적성과 얼마나 떨어져 있는지를 최악의 경우 추정할 수 있다.마지막으로 분기 및 바인딩 방법을 사용하여 여러 최적 솔루션을 반환할 수 있습니다.

소수의 변수에 대한 정확한 알고리즘

A $(\displaystyle$ A $)$ 가 $A$ m-by-n 정수 행렬이고 $(\$ 가 $\mathbf {b}$ m-by-1 정수 벡터라고 $A$ 합니다.실현 가능성 문제에 초점을 맞춘다. 즉, A $A\mathbf {x} \leq \mathbf {b}$ b \ $displaystyle$ A $\mathbf {x}$ \ $leq$ 를 만족하는 n-by-1 벡터 $\mathbf {x}$ ${\$ \ $mathbf$ { $x}}$ 가 존재하는지 여부를 결정한다.

V를 A $(\displaystyle$ A $)$ $\mathbf {b}$ b $(\$ 계수의 최대 절대값으로 하고 n(변수 수)이 고정 상수일 경우 실현가능성 문제는 m 및 로그 V 단위로 시간 다항식으로 해결할 수 있다.이것은 n=1인 경우에 사소한 것이다.사례 n=2는 1981년 허버트 ^[11]스카프에 의해 해결되었다.일반적인 사건은 1983년 헨드릭 렌스트라가 라즐로 로바스와 피터 반 엠데 보아스의 아이디어를 ^[12]결합해 해결했다.

0-1 ILP의 특수한 경우, Lenstra의 알고리즘은 완전한 열거와 동등합니다.가능한 모든 솔루션의 수는 고정되어ⁿ(2), 각 솔루션의 실현 가능성을 시간 폴리(m, 로그 V)로 확인할 수 있습니다.각 변수가 임의의 정수일 수 있는 일반적인 경우 완전한 열거는 불가능합니다.여기서 Lenstra의 알고리즘은 숫자의 기하학에서 아이디어를 사용합니다. $\mathbf {x}$ 명령어는 원래 문제를 다음과 같은 특성을 가진 것으로 변환합니다.해법 x $(\$ 의 $\mathbf {x}$ 존재는 $x_{n}$ 하거나 xn $(\$ n})( $x_{n}$ n번째 변수)의 값은 길이가 n의 함수로 제한되는 간격에 속합니다.후자의 경우, 문제는 제한된 수의 저차원 문제로 감소한다.알고리즘의 런타임 복잡성은 몇 가지 단계에서 개선되었습니다.

Lenstra의^[12] 원래 알고리즘은 $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$ $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$ $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$ 3) $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$ ( $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$ log $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$ V ) $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$ ( $2^{O(n^{3})}\cdot (m\cdot \log V)^{O(1)}$ ) \ $displaystyle$ 2 $^{O(n^{3}}$ \ $cdot ( m$ \ $cdot$ \ $log$ V )^{ $O$ (1 $)}$ 였습니다.
Kannan은^[13] $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ O ( $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ ) $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ ( $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ V ) $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ O ( $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ ) \ $display$ n $^{ O$ ( n ) } \ $cdot ( m$ \ $cdot$ \ $log$ V )^{ $O$ ( $1$ ) $n^{O(n)}\cdot (m\cdot \log V)^{O(1)}$ ^[14]} . . . with 。
프랭크와^[15] 타도스는 다른 개선된 알고리즘을 제시했습니다.향상된 런타임은 $n^{2.5n}\cdot \ell$ 2. $n^{2.5n}\cdot \ell$ $⋅display$ { $displaystyle$ $\ell$ n $^{$ 2 $.5n$ }\ $cdot \ell }$ 입니다 $.$ 서 $\ell$ "\displaystyle $\ell$ "은 입력 ^[16]비트 수로 ${\text{poly}}(m,\log {V})$ $($ , ${\text{poly}}(m,\log {V})$ V $)\displaystyle$ {poly $}(m,\log {V$ ^[17]^{: Prop.8}입니다.

Lenstra의 알고리즘은 ILP가 이중의 경우에도 다항식 시간 해결 가능하다는 것을 의미하며, 여기서 n은 변화하지만 m(제한조건의 수)은 일정합니다.

경험적 방법

정수 선형 프로그래밍은 NP-hard이므로 많은 문제 인스턴스가 다루기 어렵기 때문에 대신 경험적 방법을 사용해야 합니다.예를 들어 tabu 검색을 사용하여 ^[18]ILP에 대한 솔루션을 검색할 수 있습니다.tabu 검색을 사용하여 ILP를 해결하려면 다른 모든 정수 제약 변수를 일정하게 유지하면서 실행 가능한 솔루션의 정수 제약 변수를 증가 또는 감소시키는 것으로 정의할 수 있습니다.다음으로 제한되지 않은 변수가 해결됩니다.단기 메모리는 이전에 시도한 솔루션으로 구성될 수 있으며, 중기 메모리는 높은 목표값을 초래한 정수 제약 변수 값으로 구성될 수 있습니다(ILP가 최대화 문제라고 가정).마지막으로, 장기 메모리는 이전에 시도하지 않은 정수 값으로 검색을 유도할 수 있습니다.

ILP에 적용할 수 있는 다른 경험적 방법은 다음과 같습니다.

또한 출장 세일즈맨 문제에 대한 k-opt 휴리스틱과 같은 다양한 문제별 휴리스틱이 있습니다.휴리스틱 방법의 단점은 해법을 찾지 못하면 실현 가능한 해법이 없기 때문인지 알고리즘이 단순히 해법을 찾지 못했기 때문인지 판단할 수 없다는 것입니다.또, 통상, 이러한 방법으로 반환되는 솔루션이 최적에 얼마나 가까운지를 정량화하는 것은 불가능합니다.

스파스 정수 프로그래밍

정수 프로그램을 정의하는 $행렬$ A $(\displaystyle$ A $)$ 가 $A$ 희박한 경우가 많습니다.특히, 이는 매트릭스가 블록 구조를 가지고 있을 때 발생하며, 이는 많은 응용 프로그램에서 그러합니다.행렬의 희소성은 다음과 같이 측정할 수 있다. $A$ {\displaystyle A}의 그래프에는 A{\ $displaystyle$ A $A$ 의 열에 대응하는 정점이 있으며, A{\ $displaystyle$ A $}$ 의 $A$ $A$ 행이 모두 0이 아닌 경우 두 개의 $A$ 이 에지를 형성합니다.마찬가지로 꼭지점은 변수에 대응하며, 부등식을 공유하는 경우에는 두 변수가 모서리를 형성합니다. $A의$ $희소성$ $d$ 는 $d$ $A$ 의 $A$ $그래프$ 트리 깊이와 $A$ 의 $A$ 전치 그래프 트리 깊이 사이의 최소값입니다. \ $displaystyle$ A는 $a$ $A$ $A의$ 으로 $a$ 됩니다.um A $\style$ $A$ displaystyle n $\displaystyle$ n $\$ displaystyle n은 $n$ $정수$ 프로그램의 변수 수입니다.그 후 2018년에는^[19] 정수 프로그래밍을 { $displaystyle$ a $}$ 와 $a$ d { $displaystyle$ d $d$ 로 파라미터화된 강력한 다항식 및 고정 파라미터 처리 가능 시간으로 해결할 수 있음을 보여주었다.즉, 어떤 $계산$ 가능한 $함수$ f ${displaystyle$ f $}$ 와 $f$ 어떤 $상수$ k{ $displaystyle$ k $k$ 의 경우 정수 프로그래밍은 $f(a,d)n^{k}$ f $a$ $d$ k({ $displaystyle f(a, d)$ n $k$ })로 해결할 수 있습니다. 특히 시간은 오른쪽 $(\displaystyle$ b $)$ 및 목적 $함수$ c{ $displaystyle$ }와 무관합니다. $c$ 또한 변수의 $숫자$ $n(\displaystyle$ n $n$ )이 파라미터인 Lenstra의 기존 결과와 달리 변수의 $n$ (\ $displaystyle$ n $n$ )은 입력의 변수 부분입니다 $.$

「」를 참조해 주세요.

제약 조건이 있는 최소 제곱

레퍼런스

^ "Mixed-Integer Linear Programming (MILP): Model Formulation" (PDF). Retrieved 16 April 2018.
^ Papadimitriou, C. H.; Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Mineola, NY: Dover. ISBN 0486402584.
^ Erickson, J. (2015). "Integer Programming Reduction" (PDF). Archived from the original (PDF) on 18 May 2015.
^ Williams, H.P. (2009). Logic and integer programming. International Series in Operations Research & Management Science. Vol. 130. ISBN 978-0-387-92280-5.
^ Borndörfer, R.; Grötschel, M. (2012). "Designing telecommunication networks by integer programming" (PDF).
^ Sharma, Deepak (2010). "Frequency Planning".
^ Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A.; Khodr, H. M. (2010-01-01). "Optimal scheduling of a renewable micro-grid in an isolated load area using mixed-integer linear programming". Renewable Energy. 35 (1): 151–156. doi:10.1016/j.renene.2009.02.031. hdl:10400.22/1585. ISSN 0960-1481.
^ Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (2013-10-01). "Distributed energy resource system optimisation using mixed integer linear programming". Energy Policy. 61: 249–266. doi:10.1016/j.enpol.2013.05.009. ISSN 0301-4215.
^ Schouwenaars, T.; Valenti, M.; Feron, E.; How, J. (2005). "Implementation and Flight Test Results of MILP-based UAV Guidance". 2005 IEEE Aerospace Conference: 1–13. doi:10.1109/AERO.2005.1559600. ISBN 0-7803-8870-4. S2CID 13447718.
^ Radmanesh, Mohammadreza; Kumar, Manish (2016-03-01). "Flight formation of UAVs in presence of moving obstacles using fast-dynamic mixed integer linear programming". Aerospace Science and Technology. 50: 149–160. doi:10.1016/j.ast.2015.12.021. ISSN 1270-9638.
^ Scarf, Herbert E. (1981). "Production Sets with Indivisibilities, Part I: Generalities". Econometrica. 49 (1): 1–32. doi:10.2307/1911124. ISSN 0012-9682. JSTOR 1911124.
^ ^a ^b Lenstra, H. W. (1983-11-01). "Integer Programming with a Fixed Number of Variables". Mathematics of Operations Research. 8 (4): 538–548. CiteSeerX 10.1.1.431.5444. doi:10.1287/moor.8.4.538. ISSN 0364-765X.
^ Kannan, Ravi (1987-08-01). "Minkowski's Convex Body Theorem and Integer Programming". Mathematics of Operations Research. 12 (3): 415–440. doi:10.1287/moor.12.3.415. ISSN 0364-765X.
^ Goemans, Michel X.; Rothvoss, Thomas (2020-11-07). "Polynomiality for Bin Packing with a Constant Number of Item Types". Journal of the ACM. 67 (6): 38:1–38:21. doi:10.1145/3421750. hdl:1721.1/92865. ISSN 0004-5411. S2CID 227154747.
^ Frank, András; Tardos, Éva (1987-03-01). "An application of simultaneous diophantine approximation in combinatorial optimization". Combinatorica. 7 (1): 49–65. doi:10.1007/BF02579200. ISSN 1439-6912. S2CID 45585308.
^ Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). "Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 102–108. ISBN 978-1-57735-770-4.
^ Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (2019-06-17). "High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming". Proceedings of the 2019 ACM Conference on Economics and Computation. EC '19. Phoenix, AZ, USA: Association for Computing Machinery: 505–523. doi:10.1145/3328526.3329649. ISBN 978-1-4503-6792-9. S2CID 195298520.
^ Glover, F. (1989). "Tabu search-Part II". ORSA Journal on Computing. 1 (3): 4–32. doi:10.1287/ijoc.2.1.4. S2CID 207225435.
^ Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs". Michael Wagner: 14 pages. arXiv:1802.05859. doi:10.4230/LIPICS.ICALP.2018.85. S2CID 3336201. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

추가 정보

George L. Nemhauser; Laurence A. Wolsey (1988). Integer and combinatorial optimization. Wiley. ISBN 978-0-471-82819-8.
Alexander Schrijver (1998). Theory of linear and integer programming. John Wiley and Sons. ISBN 978-0-471-98232-6.
Laurence A. Wolsey (1998). Integer programming. Wiley. ISBN 978-0-471-28366-9.
Dimitris Bertsimas; Robert Weismantel (2005). Optimization over integers. Dynamic Ideas. ISBN 978-0-9759146-2-5.
John K. Karlof (2006). Integer programming: theory and practice. CRC Press. ISBN 978-0-8493-1914-3.
H. Paul Williams (2009). Logic and Integer Programming. Springer. ISBN 978-0-387-92279-9.
Michael Jünger; Thomas M. Liebling; Denis Naddef; George Nemhauser; William R. Pulleyblank; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, eds. (2009). 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer. ISBN 978-3-540-68274-5.
Der-San Chen; Robert G. Batson; Yu Dang (2010). Applied Integer Programming: Modeling and Solution. John Wiley and Sons. ISBN 978-0-470-37306-4.
Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice. CRC Press. ISBN 978-1-498-71016-9.

외부 링크

[1] "Mixed-Integer Linear Programming (MILP): Model Formulation" (PDF). Retrieved 16 April 2018.

[optBook-2] Papadimitriou, C. H.; Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Mineola, NY: Dover. ISBN 0486402584.

[3] Erickson, J. (2015). "Integer Programming Reduction" (PDF). Archived from the original (PDF) on 18 May 2015.

[4] Williams, H.P. (2009). Logic and integer programming. International Series in Operations Research & Management Science. Vol. 130. ISBN 978-0-387-92280-5.

[5] Borndörfer, R.; Grötschel, M. (2012). "Designing telecommunication networks by integer programming" (PDF).

[6] Sharma, Deepak (2010). "Frequency Planning".

[7] Morais, Hugo; Kádár, Péter; Faria, Pedro; Vale, Zita A.; Khodr, H. M. (2010-01-01). "Optimal scheduling of a renewable micro-grid in an isolated load area using mixed-integer linear programming". Renewable Energy. 35 (1): 151–156. doi:10.1016/j.renene.2009.02.031. hdl:10400.22/1585. ISSN 0960-1481.

[8] Omu, Akomeno; Choudhary, Ruchi; Boies, Adam (2013-10-01). "Distributed energy resource system optimisation using mixed integer linear programming". Energy Policy. 61: 249–266. doi:10.1016/j.enpol.2013.05.009. ISSN 0301-4215.

[9] Schouwenaars, T.; Valenti, M.; Feron, E.; How, J. (2005). "Implementation and Flight Test Results of MILP-based UAV Guidance". 2005 IEEE Aerospace Conference: 1–13. doi:10.1109/AERO.2005.1559600. ISBN 0-7803-8870-4. S2CID 13447718.

[10] Radmanesh, Mohammadreza; Kumar, Manish (2016-03-01). "Flight formation of UAVs in presence of moving obstacles using fast-dynamic mixed integer linear programming". Aerospace Science and Technology. 50: 149–160. doi:10.1016/j.ast.2015.12.021. ISSN 1270-9638.

[11] Scarf, Herbert E. (1981). "Production Sets with Indivisibilities, Part I: Generalities". Econometrica. 49 (1): 1–32. doi:10.2307/1911124. ISSN 0012-9682. JSTOR 1911124.

[:0-12] Lenstra, H. W. (1983-11-01). "Integer Programming with a Fixed Number of Variables". Mathematics of Operations Research. 8 (4): 538–548. CiteSeerX 10.1.1.431.5444. doi:10.1287/moor.8.4.538. ISSN 0364-765X.

[13] Kannan, Ravi (1987-08-01). "Minkowski's Convex Body Theorem and Integer Programming". Mathematics of Operations Research. 12 (3): 415–440. doi:10.1287/moor.12.3.415. ISSN 0364-765X.

[14] Goemans, Michel X.; Rothvoss, Thomas (2020-11-07). "Polynomiality for Bin Packing with a Constant Number of Item Types". Journal of the ACM. 67 (6): 38:1–38:21. doi:10.1145/3421750. hdl:1721.1/92865. ISSN 0004-5411. S2CID 227154747.

[15] Frank, András; Tardos, Éva (1987-03-01). "An application of simultaneous diophantine approximation in combinatorial optimization". Combinatorica. 7 (1): 49–65. doi:10.1007/BF02579200. ISSN 1439-6912. S2CID 45585308.

[16] Bliem, Bernhard; Bredereck, Robert; Niedermeier, Rolf (2016-07-09). "Complexity of efficient and envy-free resource allocation: few agents, resources, or utility levels". Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. IJCAI'16. New York, New York, USA: AAAI Press: 102–108. ISBN 978-1-57735-770-4.

[17] Bredereck, Robert; Kaczmarczyk, Andrzej; Knop, Dušan; Niedermeier, Rolf (2019-06-17). "High-Multiplicity Fair Allocation: Lenstra Empowered by N-fold Integer Programming". Proceedings of the 2019 ACM Conference on Economics and Computation. EC '19. Phoenix, AZ, USA: Association for Computing Machinery: 505–523. doi:10.1145/3328526.3329649. ISBN 978-1-4503-6792-9. S2CID 195298520.

[18] Glover, F. (1989). "Tabu search-Part II". ORSA Journal on Computing. 1 (3): 4–32. doi:10.1287/ijoc.2.1.4. S2CID 207225435.

[19] Koutecký, Martin; Levin, Asaf; Onn, Shmuel (2018). "A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs". Michael Wagner: 14 pages. arXiv:1802.05859. doi:10.4230/LIPICS.ICALP.2018.85. S2CID 3336201. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

Search

정수 프로그래밍

네임스페이스

더

목차

ILP의 표준 및 표준 형식

예

NP-경도 증명

변종