Блог

Итак, у меня есть эта смешанная целочисленная программа, где мой индикатор x равен 0 или 1 в зависимости от того, используется элемент или нет. Я хотел бы максимизировать цену предметов в пакете в соответствии с ограничениями в приведенном ниже коде.

Мой вопрос в том, что я хочу повторить этот процесс многократно конечное число раз и каждый раз использовать решение для наложения дополнительных ограничений на следующий раз / раунд.

Цена колеблется каждый раз, поэтому необходимо будет упаковывать разные товары. Однако я разрешаю только одно бесплатное изменение при каждом запуске решателя. За каждое дополнительное изменение из последнего набора решений будет взиматься штраф, скажем, -100 за каждый элемент. Игрушечный пример: Итак, если последнее решение было [0,0,1,1,0,0,0,0,0], а новое решение [1,1,0,0,0,0,0,0,0], то в достижении цели -100 был бы наложен штраф из-за того, что они были 2 изменениями с последнего раунда. Если бы оно изменилось на [0,1,0,1,0,0,0,0,0,0], то это было бы непенализировано.

Как мне наложить это наказание в objective и наложить ограничение на 1 бесплатное изменение?

Начальная программа выглядит следующим образом:

 items = [i for i in range(len(df))]
price = df['price'].to_dict()
volume = df['volume'].to_dict() 
weight = df['weight'].to_dict()


prob = LpProblem('mip',LpMaximize)
x = LpVariable.dicts("items", items, 0, 1, LpBinary)

#objective
prob  = lpSum([(price[i]*x[i]) for i in items])

#constraints
prob  = lpSum([x[i] for i in items]) = 10
prob  = lpSum([weight[i] * x[i] for i in items]) <= 1000
prob  = lpSum([volume[i] * x[i] for i in items]) <= 5000

prob.solve()

#to get the solution in a list for reuse
current_solution = [x[i].varValue for i in items]
  

Я думал об использовании фиктивных элементов в var [i] с prices = -100, но не смог заставить его работать. Любая помощь? Заранее большое спасибо.

Не очень просто.

Я бы попробовал что-то вроде:

(1) Введите двоичную переменную d[i] ∈ {0,1} и ограничения:

  -d[i] <= x[i] - x0[i] <= d[i]
  

где x0 — предыдущее решение. (Это должно быть реализовано как два разных ограничения в PuLP. Кроме того, мы на самом деле можем расслабиться d , чтобы быть непрерывным между 0 и 1: он будет автоматически двоичным.)

(2) Добавьте переменную n и ограничение:

   n = sum(i, d[i])
  

(3) Добавьте положительную переменную n1 >= 0 и ограничение

   n1 >= n - 1 
  

(4) Добавьте термин к цели

  -100*n1
  

(мы хотим минимизировать 100*n1 , поэтому я добавил знак минус, поскольку ваш объект максимизируется).