이 정수 프로그래밍입니까?

Question

문제 : n 변수 (x)가 상수가됩니다. x1 + x2 + .. + xn = const, 여기서 각 x는 p (양의 5) 양의 정수 값만 취할 수 있습니다. 우리는 x 사이의 차이가 최소화되는, 즉 가장 균일하게 분포되는 솔루션을 찾고자합니다. 이것은 정수 프로그래밍 문제입니까?

DLM은

Answer 1

실제에 당신은 적절한 분포를 얻기 위해 솔루션의 전체 공간을 검색 할 필요가 NP 완전 문제가 될 것으로 보인다. 어쩌면이

I. 욕심 알고리즘

foreach x in xses 
    if current_sum < desired_sum: 
     take maximal p for x 
    else take_minimal p for x 

당신은 아마 당신이 DESIRED_SUM

보다 약간 SUM 큰 것, 이것이 적절한 솔루션을 가져 오지 않습니다시피을 시도하지만,이 후에는 수 귀하의 배포를 최적화하기 시작하십시오 : 이제 우리는 탐욕스러운 선정 된 xses 세트를 갖게되었습니다

그러면 해결책이 닫힙니다.

II. 진화 알고리즘

엄격한 정의로 유전 알고리즘을 사용할 수 있습니다. 집단은 단지 벡터 및 그것에 적절한 진화 연산을 수행

(원하는 합 X로부터 계산 합계 간의 차이) 분명 X = X1, X2, X3, X4 ... XN] 적합도 함수들의 벡터 것 짧은 시간에 최적의 솔루션을 제공해야합니다.

Answer 2

정수에 대한 경계 (또는 추가 정보)가 있습니까? .

가

function adds_up_to(xs, N): 
    sums := {0} 
    for i from 1 to n: 
     new_sums := {} 
     for sum in sums: 
      for value in values: 
       new_sums := new_sums U {sum + value} 
     sums := new_sums 
    return (N in sums) 

(이 그냥 만족스러운 해결책을 검색 알고리즘이 필요 : 그들은 너무 큰 수없는 경우 (모든 조합을하지 않고) 모든 가능한 금액 통과하는 알고리즘을 할 가능이 될 수 차이를 처리하도록 강화되어야 함 - 의미가 무엇이든간에)

Answer 3

예 이것은 정수 프로그래밍 문제입니다.

minimize |x1 - x2| + |x2 - x3| + ... + |xn-1 - xn| 

    subject to x1 + x2 + x3 + ... + xn == c, 

       xi == Ai1*yi1 + Ai2*yi2 + ... + Aip*yip, i=1,...,n, 

       yi1 + yi2 + ... + yip == 1, i=1,...,n, 

       yij binary for i=1,...,n j=1,...,p, 

       xi integer for i=1,...,n, 

여기서 Aij는 xi의 특정 값이 어떤 정수를 나타낼 수 있는지를 설명하는 입력 데이터입니다. 다음은 3 개의 변수 (n = 3)로 구성된 구체적인 예입니다. 각 xi는 두 개의 정수 값 (p = 2) 중 하나를 취할 수 있습니다. 즉, X1은 1 또는 3, X2는 새롭게 작성하여 3 또는 4, X3은 2 또는 3

minimize |x1 - x2| + |x2 - x3| 

    subject to x1 + x2 + x3 == 8, 

       x1 == 1*y11 + 3*y12, 
       x2 == 3*y21 + 4*y22, 
       x3 == 2*y31 + 3*y32, 

       y11 + y12 == 1, 
       y21 + y22 == 1, 
       y31 + y32 == 1, 

       yij binary i=1,2,3 j=1,2 
       xi integer i=1,2,3 

당신은 MIP (혼합 정수 프로그램) 등의 상기 문제점을 재구성 할 수있을 수있을 수있을 수있다 목적 함수를 나타 내기 위해 변수 집합 u.

minimize u1 + u2 + ... + un 

    subject to ui >= xi - xi+1, i=1,...,n-1, 

       ui >= xi+1 - xi, i=1,...,n-1, 

       x1 + x2 + x3 + ... + xn == c, 

       xi == Ai1*yi1 + Ai2*yi2 + ... + Aip*yip, i=1,...,n, 

       yi1 + yi2 + ... + yip == 1, i=1,...,n, 

       yij binary for i=1,...,n j=1,...,p, 

       xi integer for i=1,...,n, 
       ui real for i=1,...,n-1, 

당신은 위의 문제를 해결하기 위해 표준 MIP solver를 사용할 수 있습니다.

Answer 4

관용적 인 기능은 집합 사이의 차이를 최소화하려는 경우 트릭입니다. 간단한 형태는 Sum (ABS (Xi-Xj)) 일 수 있습니다. 여기서 i> j입니다. 선형화 될 수 있습니다.그러나 샘플 변형을 사용하려면 QIP가되고 해결하는 데 약간 시간이 걸립니다.