정수계획·LP Relaxation·정수 해의 간극

분수 해가 실제 결정은 아닐 수 있습니다

두 프로젝트를 승인하거나 거절해야 한다고 합시다. 연속 최적화는 하나를 전부 승인하고 다른 하나를 1/3만 승인하라고 제안할 수 있습니다. 하지만 각 프로젝트가 나눌 수 없는 결정이면 이 해를 그대로 실행할 수 없습니다. 정수계획은 이 불가분성을 변수에 표현합니다. Relaxation은 feasible set을 넓혀 원래 문제를 분석하는 방법이며 분수 해를 자동으로 실행 가능한 결정으로 바꾸는 절차는 아닙니다.

이 단원은 이진 선택 네 개를 전부 확인할 수 있는 작은 모형입니다. 투명한 검산을 위한 전수 열거이지 큰 정수계획도 쉽게 해결할 수 있다는 주장이 아닙니다. 뒤에서 조합 구조와 형식적 탐색을 별도로 확장합니다.

무엇을 바꾸는지 먼저 정의하기

물건 0과 1의 무게는 각각 2와 3이며 가치는 음수가 아닌 v0, v1입니다. 선택하면 1, 선택하지 않으면 0인 변수 x0, x1을 둡니다. 이하 모드는

$$\max\ v_0x_0+v_1x_1\quad\text{subject to}\quad 2x_0+3x_1\le C,\quad x_0,x_1\in\{0,1\}.$$

정확 모드는 적재량 부등식만 등식으로 바꿉니다. 정확히 C를 채우는 다른 과제입니다. 경로 번호 대신 이진점 번호 code=2*x0+x1을 사용하며, 0·1·2·3번의 적재량은 0·3·2·5입니다. 이하 모드에서는 빈 선택이 언제나 가능합니다. 정확 모드에서는 C가 0, 2, 3, 5 중 하나일 때만 이진 해가 있습니다.

LP relaxation은 목적함수와 적재량 제약을 유지하고 변수 범위만 [0,1]로 바꿉니다. 단위 정사각형과 반평면 또는 직선의 교집합이 연속 feasible set입니다. C가 0에서 5 사이이면 두 모드의 연속 집합은 모두 비어 있지 않습니다.

상한의 방향 증명하기

가능한 모든 이진점은 연속 집합에도 들어갑니다. 따라서 정수 최적해가 존재하면

$$z_{\mathrm{IP}}\le z_{\mathrm{LP}}.$$

최대화에서 더 큰 집합을 탐색하기 때문에 LP 값이 상한입니다. 최소화라면 relaxation은 반대로 하한을 제공합니다. 실행 가능한 정수 후보의 값은 최대화 최적값의 하한입니다. 반올림한 점이 제약을 위반하면 그 점의 값은 이런 인증을 제공하지 않습니다.

가산 간극은 z_LP-z_IP입니다. 이 단원은 정수 최적값이 양수일 때 z_LP/z_IP도 표시합니다. 분모가 0이면 두 값이 모두 0이어도 비율을 제공하지 않습니다. 정수 문제가 실행 불가능하면 최적값·간극·비율을 모두 제공하지 않습니다. 해가 없는 경우를 값 0으로 바꾸면 가능한 영 가치 결정과 결정 자체의 부재를 혼동하게 됩니다.

연속 최적해와 기하

비어 있지 않은 콤팩트 다각형에서 선형 목적함수는 최적 꼭짓점을 가집니다. 선분이나 한 점으로 퇴화하는 경우도 포함합니다. 제약을 만족하는 정사각형 꼭짓점과 적재량 경계가 각 변을 만나는 점을 열거한 뒤 목적값을 비교합니다. 입력의 표준 십진 문자열을 유리수로 계산하므로 비교에 epsilon을 더해 동률이나 실행 가능성을 만드는 방식은 사용하지 않습니다. 화면의 소수 좌표와 값은 반올림 표시입니다.

선택한 최적점이 유일할 필요는 없습니다. 화면은 최적 꼭짓점 중 사전식 첫 점을 고르고 나머지 최적 꼭짓점도 표시합니다. 양의 가치 밀도 v0/2와 v1/3이 같으면 경계 선분 전체가 최적일 수 있습니다. 가치가 모두 0이면 가능한 모든 점이 최적입니다.

이 한 자원 제약 모형에서는 분수 배낭 규칙으로도 결과를 이해할 수 있습니다. 무게당 가치가 큰 물건부터 용량을 배정합니다. 덜 가치 있는 물건의 적재량 일부를 아직 포화되지 않은 높은 밀도의 물건으로 옮기면 가치가 커지기 때문입니다. 이 교환 논리를 임의의 정수계획이나 여러 자원 제약에 그대로 적용할 수는 없습니다.

상한과 반올림을 손으로 계산하기

가치 (3,4), C=3의 이하 모드에서 밀도 3/2가 4/3보다 큽니다. LP는 (1,1/3)을 선택하므로

$$z_{\mathrm{LP}}=3+4/3=13/3.$$

가능한 이진점 (0,0), (1,0), (0,1)의 가치는 0, 3, 4입니다. 정수 최적해는 (0,1), 최적값은 4, 가산 간극은 1/3입니다. 선택한 이진점이 가능하더라도 최적점은 아닐 수 있습니다.

C=4이면 LP 해는 (1,2/3), 값은 17/3입니다. 좌표별 가까운 이진값으로 반올림하면 (1,1)이 되어 무게 5가 용량 4를 넘습니다. 화면은 정확히 1/2일 때 올리는 half-up 규칙을 사용하고 원래 제약으로 반올림 결과를 다시 검사합니다. 반올림은 검증할 후보를 만드는 일이며 정확 해법이나 근사 보장 자체가 아닙니다.

같은 C=4에서 정확 모드로 바꾸면 LP는 여전히 가능하지만 어떤 이진점도 적재량 4를 만들지 못합니다. 주황 최적점이 사라지고 정수 값은 제공되지 않습니다. 연속 해의 존재만으로 정수 해의 존재를 증명할 수 없습니다.

도식과 용량 곡선 읽기

위 도식의 두 축은 같은 축척입니다. 파란 면이나 선분은 연속 feasible set이고 파란 원은 선택한 LP 해입니다. 주황 점은 선택한 정수 최적해, 주황 테두리는 모든 정수 최적점을 표시합니다. ×는 불가능한 이진점입니다. 얇은 원은 조회할 이진점, 점선 네모는 LP 해를 반올림한 점입니다. 서로 다른 의미의 표시가 같은 좌표에서 겹칠 수 있습니다.

아래 가로축은 반복 횟수가 아니라 C입니다. 파랑은 LP 값입니다. 이하 모드의 정수 값은 오른쪽 열린 수평 구간과 닫힌 점으로 표시합니다. 정확 모드에서는 정수 해가 있는 적재량만 주황 점으로 표시하고 불가능한 구간을 가짜 값으로 잇지 않습니다. 현재 LP 값에는 파란 점도 있습니다. 아주 작은 양의 정확한 분수는 소수 화면에서 0으로 반올림될 수 있으며 문장의 정확한 분수 표기가 이를 구분합니다. 비율 자체가 표시 범위를 넘는 경우와 분모 0인 경우도 따로 표시합니다.

문제와 해설

문제: 가치 (3,4), C=1의 이하 모드에서 두 최적값과 비율을 구하세요.

해설: 빈 이진 선택만 가능하므로 정수 값은 0입니다. LP는 (1/2,0)으로 값 3/2, 가산 간극도 3/2입니다. 분모가 0이라 비율은 정의되지 않습니다. 빈 선택은 존재하므로 정수 실행 불가능성과도 다릅니다.

문제: 가치 (2,3), C=3에서 선택한 LP 점은 유일할까요?

해설: 목적함수가 적재량과 같아 적재량 3의 경계 선분 전체가 최적입니다. 한 점을 고르는 결정적 규칙은 표시 방식이며 유일성 증명이 아닙니다. 정수점 (0,1)도 같은 값 3을 달성하지만 다른 최적 LP 점은 분수일 수 있습니다.

문제: 정수와 LP의 최적값이 같으면 모든 LP 최적점이 정수일까요?

해설: 위의 같은 밀도 예제가 반례입니다. 이 경우 정수 최적점이 존재한다는 사실과 최적 face 전체가 정수라는 사실은 다릅니다.

후속 학습 연결

James B. Orlin의 MIT 정수계획 참고 자료는 이진 부분집합 선택과 relaxation 경계의 역할을 설명합니다. 이 단원의 두 물건 계산, 정확 적재량 반례와 유리수 비교는 교재를 위한 직접 유도입니다. Branch-and-bound, 근사 보장, 미분 가능한 relaxation은 뒤 단원에서 별도 가정과 논리로 다룹니다.