배낭과 제약 조건이 여러 개인 배낭 문제 해결

Question

저는 Excel solver 또는 다른 도구 (모든 제안은 환영합니다)로 해결하려는 다음 문제가 있지만 코드를 작성하지 않으려합니다.

몇 가지 배낭 (약 5)에 넣을 항목이 (약 40 개) 있습니다. 모든 항목의 무게는 같지만 모든 배낭은 동일한 공간을 사용합니다.

항목의 무게의 합은 배낭의 용량보다 훨씬 적습니다.

내가해야 할 일은 배낭에있는 물건을 모두 채우거나 모두 같은 무게로 채우는 것입니다. 즉, 분산을 줄입니다.

일부 항목은 함께 사용할 수없는 제약이 있습니다. 함께 갈 수 있거나 가질 수없는 항목의 목록 (또는 인접 행렬)이 있습니다.

물론 한 항목이 배낭에 들어가면 두 번째 항목으로 이동할 수 없습니다 (항목의 각 왕당 하나의 항목 만 있음).

나는이 문제를 Excel에서 해결하려고 노력하고 있지만 알고리즘 중 3 가지는 솔루션을 찾을 수 없다고하지만 수동으로 찾을 수 있으므로 제대로 구성하지 않았다고 생각합니다.

어쨌든 나는 체중에 관한 문제의 일부만을 능가하여 구성 할 수 있지만 항목 간의 비 호환성에 관한 문제의 부분을 설정할 수는 없습니다.

당신의 도움이

Answer 1

이 배낭에 비해 측면 제약 multiprocessor scheduling 더 주셔서 감사합니다.

이렇게 순진한 형식을 시도해 볼 수 있습니다. 각 항목에 대해 배낭의 항목을 나타내는 0-1 변수와 해당 변수의 합이 1 인 제약이 배낭의 최대 총 무게를 최소화하는 것입니다. 함께 갈 수없는 항목 쌍마다 해당 표시기 변수의 합계가 1보다 작거나 같음을 나타내는 [배낭 수] 제약이 있습니다.

두 개의 배낭 (A 및 B), 세 항목 (x, 무게 3, y, 무게 1, z, 무게 4)과 충돌 (x는 y와는 다를 수 있음). 파괴에는 대칭이 없기 때문에

minimize C 
over 0-1 variables Ax, Ay, Az, Bx, By, Bz and real variable C 
subject to 
C >= 3*Ax + 1*Ay + 4*Az # load in A 
C >= 3*Bx + 1*By + 4*Bz # load in B 
Ax + Bx = 1 # one placement of x 
Ay + By = 1 # one placement of y 
Az + Bz = 1 # one placement of z 
Ax + Ay <= 1 # conflict between x and y in A 
Bx + By <= 1 # conflict between x and y in B 

이 제제는 최적이 아닌 - 본질적으로, LP 솔버의 검색 트리 배낭의 순열의 수와 같은 요인에 의해 복제됩니다. 이것은 단지 5입니다! = 최악의 경우 = 120이므로 괜찮을 수도 있습니다. 길을가는 길은 아마도 올바른 배낭 수와 제약 조건에 따라 하나의 배낭을 포장하는 하위 문제가있는 항목을 정확하게 다루는 데 필요한 주된 문제가있는 column generation이지만 Excel의 범위를 벗어납니다.