Это целочисленное программирование?

Question

Проблема: n переменных (x) складываются, чтобы быть постоянными.x1 + x2 + .. + xn = const, где каждый x может принимать только p (скажем, 5) положительных целочисленных значений.Мы хотим найти решение, в котором разница между x сведена к минимуму, то есть они наиболее равномерно распределены.Это целочисленная проблема программирования?

dlm

Answer 1

Да, это целочисленная проблема программирования. Вы можете написать это как:

   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 2

Что касается объективной функции, то это хитрость, когда вы хотите минимизировать разницу между множеством.Простая форма может быть суммой (ABS (Xi-Xj)), где i> j.который может быть линеаризован.Однако, если вы хотите использовать примерный вариант, он станет QIP и займет немного больше времени.

Answer 3

У вас есть границы (или дополнительная информация) для целых чисел? Если они не слишком велики, возможно, выполним алгоритм, который обрабатывает все возможные суммы (без выполнения всех комбинаций):

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 4

Кажется, это np-полная проблема, в действительности вам нужно искать все пространство решений, чтобы получить правильное распределение. Может быть, попробовать это

I. Жадный алгоритм

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

Поскольку вы видите, что это не приведет к правильному решению, возможно, у вас будет некоторая сумма, превышающая DESIRED_SUM

но после этого вы можете начать оптимизировать свой дистрибутив: теперь у нас есть набор жадных выделенных xses

foreach x:
   if current_sum > desired_sum
       change taken P to minimal P for x
   else
     break

это приблизит вас к решению

II. Эволюционный алгоритм

Строгое определение вашей проблемы приводит вас к генетическим алгоритмам. Населения будут векторами X = [x1, x2, x3, x4 ... xn] фитнес-функция очевидна (разница между желаемой суммой и вычисленной суммой из X)

просто выполните правильные эволюционные операции над векторами, и это должно привести вас к оптимизированному решению за короткое время