Python Pulp Integer Linear Program with dynamic constraint -

i want solve mixed integer linear program following objective function:

j = maximize (f1(x) + f2(x)) subject constraint: cost(x) <= threshold

where x set of selected variables, f1 , f2 2 scoring functions , cost cost function.

f2 function based on similarity between selected variables. don't know how formulate function in pulp.

this minimal working example in function f2 similarity between 2 ingredients , want add similarity[i][j] objective function if j in selected variables, don't know how it.

import numpy np import pulp threshold = 200 model = pulp.lpproblem('selection', pulp.lpmaximize) similarity = np.array([[1., 0.08333333, 0.1, 0., 0., 0.0625],                        [0.08333333, 1., 0.33333333,                            0., 0.11111111, 0.07692308],                        [0.1, 0.33333333, 1., 0.2, 0., 0.09090909],                        [0., 0., 0.2, 1., 0., 0.],                        [0., 0.11111111, 0., 0., 1., 0.27272727],                        [0.0625, 0.07692308, 0.09090909, 0., 0.27272727, 1.]]) ingredients = ['var_%d' % in range(6)] scores = np.random.randint(1, 3, size=len(ingredients)) costs = np.random.randint(20, 60, len(ingredients)) scores = dict(zip(ingredients, scores)) costs = dict(zip(ingredients, costs)) x = pulp.lpvariable.dict(     'x_%s', ingredients, lowbound=0, upbound=1, cat=pulp.lpinteger) model += sum([scores[i] * x[i] in ingredients]) model += sum([costs[i] * x[i] in ingredients]) <= threshold solver = pulp.solvers.pulp_cbc_cmd() model.solve(solver) 

this code considers static costs (encoded in costs variable). how can dynamically add similarity costs similarity variable?

i believe want add interaction term says when both ingredients i , j selected, there cost associated existence of both i , j, described in similarity matrix. going assume (as in case) similarity symmetric matrix, since ordering of i , j not matter (it matters if both selected or not).

a naive formulation add term selected[i, j] * x[i] * x[j] objective. render problem non-linear, , although structure not prohibitively difficult, there common modelling trick keep model linear. here is.

we define new set of variables y_{ij} equal 1 if both i , j participate in solution. note can define i>j or j<i since not care ordering. impose restrictions:

y_{ij} <= x_i y_{ij} <= x_j y_{ij} >= x_i + x_j - 1 

this set of restrictions guarantee y_{ij} equals 1 when both x_i , x_j equal 1, want.

an implementation on code:

import numpy np import pulp itertools import product threshold = 200 model = pulp.lpproblem('selection', pulp.lpmaximize) similarity = np.array([[1., 0.08333333, 0.1, 0., 0., 0.0625],                        [0.08333333, 1., 0.33333333,                            0., 0.11111111, 0.07692308],                        [0.1, 0.33333333, 1., 0.2, 0., 0.09090909],                        [0., 0., 0.2, 1., 0., 0.],                        [0., 0.11111111, 0., 0., 1., 0.27272727],                        [0.0625, 0.07692308, 0.09090909, 0., 0.27272727, 1.]]) ingredients = ['var_%d' % in range(6)]  ingredient_pairs = ['var_{}_{}'.format(     ingredients.index(var[0]), ingredients.index(var[1]))      var in product(ingredients, ingredients)      if ingredients.index(var[0]) > ingredients.index(var[1])]   # flatten similarity array indices = np.triu_indices_from(similarity) similarity = similarity[indices]  scores = np.random.randint(1, 3, size=len(ingredients)) costs = np.random.randint(20, 60, len(ingredients)) scores = dict(zip(ingredients, scores)) costs = dict(zip(ingredients, costs)) similarity = dict(zip(ingredient_pairs, similarity)) x = pulp.lpvariable.dict(     'x_%s', ingredients, lowbound=0, upbound=1, cat=pulp.lpinteger) y = pulp.lpvariable.dict(     'y_%s', ingredient_pairs, lowbound=0, upbound=1, cat=pulp.lpinteger) model += sum([scores[i] * x[i] in ingredients]) + sum([     similarity[i] * y[i] in ingredient_pairs]) model += sum([costs[i] * x[i] in ingredients]) <= threshold pair in ingredient_pairs:     indexes = pair.split('_')[1:]     index in indexes:         # y_{ij} <= x_i , y_{ij} <= x_j q         model += y[pair] <= x['var_{}'.format(index)]     # y_{ij} >= x_i + x_j - 1     model += y[pair] >= sum(x['var_{}'.format(i)] in indexes) - 1 solver = pulp.solvers.pulp_cbc_cmd() model.solve(solver) model.writelp('similarity.lp') print 'objective: {}'.format(pulp.value(model.objective)) v in model.variables():     if v.varvalue > 10e-4:         print v.name, v.varvalue 

i hope helps.

---

a working implementation can found here