정수 계획법 실험 도구
작은 정수 선형계획 문제를 정확한 분기 한정법으로 풀고 탐색의 모든 노드를 확인하세요. 탐색 트리 전체를 조사한 경우에만 최선의 점을 최적이라고 증명해 보고합니다.
프로그램은 4,000자와 40줄, 변수 8개, 변수가 둘 이상인 제약 조건 8개까지 가능합니다. 노드 제한은 1~5,000이며 정확한 연산을 3,000,000회 수행하면 탐색도 중단됩니다. 기기의 백그라운드 작업자가 최대 15초 동안 계산합니다. JSON 보고서와 노드 CSV를 다운로드할 수 있습니다. 첫 줄에는 maximize 또는 minimize와 목적함수를 씁니다. 그다음 제약 조건을 한 줄에 하나씩 입력하세요. 최대 4,000자입니다. 실행하기 전에 설정을 검토하세요.
내 결과
정수 계획법 실험 도구
- maximize 5x + 4y와 같이 첫 줄에 목적함수를 입력하세요.
- 제약 조건은 한 줄에 하나씩 입력하세요. x, y >= 0과 같은 경계나 integer x, binary z와 같은 선택 항목도 입력할 수 있습니다.
- 노드 제한을 설정하고 탐색을 실행하세요.
- 상태, 현재 최선 정수해, 최선의 경계값과 간격을 확인한 뒤 JSON 보고서나 노드 CSV를 다운로드하세요.
알아두세요
프로그램은 4,000자와 40줄, 변수 8개, 변수가 둘 이상인 제약 조건 8개까지 가능합니다. 노드 제한은 1~5,000이며 정확한 연산을 3,000,000회 수행하면 탐색도 중단됩니다. 기기의 백그라운드 작업자가 최대 15초 동안 계산합니다. JSON 보고서와 노드 CSV를 다운로드할 수 있습니다.
분기 한정법
각 노드에서 심플렉스법으로 선형 완화를 정확히 풉니다. 정수 변수에 분수값이 나오면 x <= floor와 x >= ceiling의 두 분기로 나눕니다. 완화 문제가 실행 불가능하거나 현재까지의 최선 정수점을 넘을 수 없는 노드는 가지치기합니다. 방법: Wolsey, Integer Programming, 제2판, 7장 (2020).
증명의 의미
모든 노드를 풀거나 정확한 경계로 가지치기하면 현재 최선해가 최적이거나 문제가 실행 불가능함을 증명합니다. 노드 제한 또는 단계 예산에 먼저 도달하면 현재 최선해는 지금까지 찾은 점 중 최선일 뿐이며 보고서에 최선 경계와 두 값의 간격을 표시합니다.
입력 규칙
변수는 기본적으로 모두 정수입니다. integer x, y처럼 일부 변수를 정수로 지정하면 나머지 변수는 연속 변수로 취급합니다. 단일 변수 제약 조건은 경계로 변환됩니다. 완화 문제가 비유계이면 정수 계획 문제가 비유계이거나 실행 불가능할 수 있으므로 탐색을 중단합니다.