Thursday, 1 November 2018

Constrain optimisation with duplicates

I have a set of many (10000+) items, from which have I have to choose exactly k items. I can only choose each item multiple times subject to an ordering constraint: If I choose an item in position 1, I can't choose it until position 21. My items have profits, and costs.

Each item is represented as a tuple:

item = ('item name', cost, profit)

as an example

vase = ['Ming Vase', 1000, 10000]

plate = ['China Plate', 10, 5]

and the total set of items is a list of lists:

items = [item1, item2, ..., itemN].

My profits and costs are also lists:

profits = [x[2] for x in items]
costs = [x[1] for x in items]

For each item chosen, it needs to have a minimum value, and that item can't be reused within the next 19 items. I want to choose the k cheapest items with the highest value subject to this constraint, but I'm having difficulty formulating it.

I'm having trouble formulating this using google OR tools. The following just gets the best k (in this case 100) without any extra constraints

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver('SolveAssignmentProblemMIP',
                       pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

x = {}

for i in range(MAX_ITEMS):
    x[i] = solver.BoolVar('x[%s]' % (i))

#Define the constraints 
total_chosen = 100
solver.Add(solver.Sum([x[i] for i in range(MAX_ITEMS)]) == total_chosen)

max_cost = 5.0

for i in range(num_recipes):
    solver.Add(x[i] * cost[i] <= max_cost)

solver.Maximize(solver.Sum([profits[i] * x[i] for i in range(total_chosen)]))
sol = solver.Solve()

I can get the set of items I've chosen by:

for i in range(MAX_ITEMS):
    if x[i].solution_value() > 0:
        print(item[i].item_name)

Any help in formulating the constraints and objective would be really helpful. Thanks!



from Constrain optimisation with duplicates

No comments:

Post a Comment