선형 조합 최적화

Question

이 조합 최적화를 해결하기 위해 무차별 알고리즘보다 알고리즘을 더 잘 이해하려고합니다.

샘플 문제 : 가능한 선형 방정식 1. 2A 합성 최소/최대 비용 2A + B를 달성하기 + B = 4 2. = 1 3. + B = 2 (RHS가 선정)

않음 2 결합 및 3을 얻을 2A + B = 3

타겟 식 더 긴하고있을 때, 분명히 성분 차식의 파워 셋 (모든 조합)를 찾는 무력 방법은 최적이 아닌 powerset은 거대하게 성장합니다.

문제가 배낭 문제의 변형입니까? 누가이 작업을 최적으로 수행 할 수있는 지침이 있습니까?

Answer 1

확실히 배낭이 아닙니다. 선형 최적화 (linear programming) 문제 일뿐입니다. Ruby의 경우, RGLPK

Answer 2

이 문제를 올바르게 이해하면 은 변형의 배낭 문제입니다. 각 상자에는 사과와 바나나가 있습니다. 그것은 또한 비용이 있습니다. 특정 수의 사과와 바나나를 얻으려면 상자를 골라야하며 총 비용은 최소화해야합니다.

나는 1D 캐시 대신 2 차원 캐시를 사용하는 DP Knapsack 알고리즘을 사용합니다 : cache [5] [10]은 5 개의 사과와 10 개의 바나나를 얻는 데 드는 비용입니다.

각 상자에 대해 지금까지 발견 된 모든 구성에 추가하고 결과가 캐시 된 값보다 싼지 확인하십시오. 그것은 캐시를 업데이트합니다.

캐시가 희박 해지기 때문에 알려진 구성 (즉, 무한대 캐시 값의 위치)을 추적하기 위해 세트를 사용하여 모든 알려진 구성을 반복하지 않고 수행 할 수 있습니다 전체 캐시를 통해.

Answer 3

이 문제는 선형 프로그래밍을 사용하여 공식화 할 수 있습니다. Gnu 선형 프로그래밍 키트 (GLPK)와 루비 래퍼 'rglpk'를 사용하여이를 해결할 수 있습니다.

운영 체제에 따라 http://www.gnu.org/software/glpk/에서 GLPK 4.44를 다운로드하십시오. 패키지의 압축을 풀고 다음 명령을 사용하여 응용 프로그램을 설치하십시오.

./configure && sudo make clean && sudo make && sudo make install 

명령 줄을 열고 아래 명령을 실행하여 'rglpk'를 설치하십시오.

gem install rglpk 

이 코드를 실행하십시오.

require 'rglpk' 

#min/max 2a+b 
#1. 2a+b=4 
#2. a=1 
#3. a+b=2 

p = Rglpk::Problem.new 
p.name = "sample" 
p.obj.dir = Rglpk::GLP_MAX 

rows = p.add_rows(3) 
rows[0].name = "2a+b=4" 
rows[0].set_bounds(Rglpk::GLP_UP, 0, 4) 
rows[1].name = "a=1" 
rows[1].set_bounds(Rglpk::GLP_UP, 0, 1) 
rows[2].name = "a+b=2" 
rows[2].set_bounds(Rglpk::GLP_UP, 0, 2) 

cols = p.add_cols(2) 
cols[0].name = "a" 
cols[0].set_bounds(Rglpk::GLP_LO, 0.0, 0.0) 
cols[1].name = "b" 
cols[1].set_bounds(Rglpk::GLP_LO, 0.0, 0.0) 

p.obj.coefs = [2, 1] 

p.set_matrix([ 
2, 1, 
1, 0, 
1, 1 
]) 

p.simplex 
z = p.obj.get 
x1 = cols[0].get_prim 
x2 = cols[1].get_prim 

printf("z = %g; x1 = %g; x2 = %g\n", z, x1, x2) 
#=> z = 3; x1 = 1; x2 = 1