So I have this mixed integer program where my indicator x is in 0 or 1 depending on if the item is used or not. I would like to maximise price of items in the bag according to the constraints in the below code.
My question is, I want to repeat this process repeatedly a finite number of times, and use the solution each time to impose further constraints for the next time/round.
The price fluctuates each time/round so different items will need to be packed. However, I am only allowing one free change each time I run the solver. For each additional change from the last solution set will come at a penalty of say -100 per each item. Toy example: So if the last solution was [0,0,1,1,0,0,0,0,0,0] and the new solution is [1,1,0,0,0,0,0,0,0,0] then a penalty would have incurred in the objective of -100 due to their being 2 changes from the last round. If it changed to [0,1,0,1,0,0,0,0,0,0] then that would be unpenalised.
How do I impose this penalty in the objective and impose the 1 free change constraint?
The initial program is as follows:
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]
I thought about using dummy items in var[i] with prices = -100, but couldn't get it to work. Any help? Thanks so much in advance.
Not super easy.
I would try something like:
(1) Introduce a binary variable d[i] ∈ {0,1} and the constraints:
-d[i] <= x[i] - x0[i] <= d[i]
where x0 is the previous solution. (This has to implemented as two different constraints in PuLP. Also, we actually may relax d to be continuous between 0 and 1: it will be binary automatically.)
(2) Add a variable n and the constraint:
n = sum(i, d[i])
(3) Add a positive variable n1 >= 0 and the constraint
n1 >= n - 1
(4) Add a term to the objective
-100*n1
(we want to minimize 100*n1 so I added the minus sign, as your obj is maximizing).