# How to make the elements of the solution of gurobi belong to the elements of the specified list?

If I want to use the elements of the list as the range of the solution, like list1 = [10,20,50,60,30],and the elements of the solution must belong to the elements of the list The sample example as follow:

m = Model()

list1 = [[10,20,30],[20,30],[10],[10,30],[10,20,30,40],[10,20,30]]

# Adding variables
f = [1,1,1,1,1,1]
z = m.addVars(6, lb=1, ub=100, vtype=GRB.INTEGER)
m.addConstr(z.prod(f) == 100, name="")

m.setObjective(z.prod(f), sense=GRB.MAXIMIZE)
m.update()


The elements of the solution must belong to the corresponding list. For example,there is one solution[10,20,10,30,20,10],and the first element of the solution10must belong to the list[10,20,30]$$$$.How should this be achieved?

• Ok. I think I get what you mean now. The sets $S_{i}$ are given. For each i, choose an element $x_i$ from set $S_{i}$. Ensure that $\sum_{i} x_{i} = 100$. Jun 30 at 3:32
• The code shows that there is a list named list1 and contains 6 sub-lists, the model has 6 variables, the value of each variable can only be taken in the sub-list corresponding to list1, such as variable 1 can only take 10,20,30, variable 2 can only take 20,30 Jun 30 at 3:33
• Does each set have an arithmetic progression of values? I mean something like $s_{1}, s_{1} + 10, s_{1} + 20, \ldots$. So you can have a set {10, 20, 30, 40} but not a set with only {10, 30, 40}. Jun 30 at 3:34
• The value is set randomly,a set may be with only {10,30,40} Jun 30 at 3:36
• Do you want the final sum to be exactly 100? Sometimes, that is impossible. Jun 30 at 3:38

## 2 Answers

Given values $$v_i$$ with index set $$I$$ (for example, $$I=\{1,2,3,4,5\}$$ with $$v=[10,20,50,60,30]$$), you can enforce $$x=v_i$$ for some $$i\in I$$ by introducing binary variables $$y_i$$ and imposing linear constraints \begin{align} \sum_{i\in I} y_i &= 1 \tag1 \\ \sum_{i\in I} v_i y_i &= x \tag2 \end{align} Constraint $$(1)$$ chooses exactly one $$i$$ with $$y_i=1$$, and constraint $$(2)$$ forces $$x=v_i$$ for that $$i$$.

• Generally, how many sets can this formulation handle? The model looks like a 0-1 knapsack problem with additional constraints to ensure choosing only 1 item from each set. Jun 30 at 3:50
• Thanks a lot. I find some timing: towardsdatascience.com/… Jun 30 at 3:59
• Yes, and it is the standard approach. It is not quite knapsack because the RHS is a variable, not a constant. Jun 30 at 4:02
• I have added a more general question and answer that address the modeling aspect, independent of solver: or.stackexchange.com/questions/6545/… Jul 9 at 14:31

Here is a small variation of RobPratt's answer.

I will use two sets, as an example. Two sets of constants are given: $$S_1 = \lbrace x_{1,1}, x_{1,2}, x_{1,3} \rbrace$$ and $$S_2 = \lbrace x_{2,1}, x_{2,2} \rbrace$$. The goal is to choose 1 item from each set and ensure the sum of all items chosen is 100.

Make one binary variables per item: $$b_{1,1}, b_{1,2}, b_{1,3}$$ and $$b_{2,1}, b_{2,2}$$. These binary variables indicate which items are chosen. For example, if $$b_{1,1} = 1$$, the 1st item in the 1st set is chosen. Binary variables can only have two possible values: 0 or 1. Sometimes they are also called boolean variables.

Constraints to ensure only 1 item chosen from each set:

$$b_{1, 1} + b_{1,2} + b_{1,3} = 1$$ $$b_{2, 1} + b_{2,2} = 1$$

A constraint to ensure the sum of all items chosen is 100:

$$b_{1, 1} x_{1,1} + b_{1,2} x_{1,2} + b_{1,3}x_{1,3} + b_{2,1}x_{2,1} + b_{2,2}x_{2,2} = 100$$

I haven't used or installed gurobipy before. Here is my guess based on the documentation and example code.

"""A variation of subset sum problem.

Additional constraints group the items and ensure only 1 item
chosen per group.
"""
import gurobipy as gp
from gurobipy import GRB

def process_group(item_values: list, m: gp.Model, prefix: str):
# Create one binary variable per item in the group.
shape = len(item_values)
bns = m.addMVars(shape, vtype=GRB.BINARY,
name=(prefix + "_choice")

# A constraint that ensures only 1 item in this group is chosen.
m.addConstr(bns.sum() == 1, name=(prefix + "_choose1"))

# contribution = x11 * b11 + x12 * b12 + ...
coefficients = item_values
variables = bns
contribution = gp.LinExpr(coefficients, variables)
return contribution

def main():
# Data and parameters
group_values_list = [[10, 20, 30], [20, 30], [10],
[10, 30], [10, 20, 30, 40],
[10, 20, 30]]
max_total_value = 100

# Model
m = gp.Model()
contributions = [process_group(g, m, "set%d" % i)
for i, g in enumerate(group_values_list)]
total_value = sum(contributions)

# Limit the total value of the chosen items
m.addConstr(total_value <= max_total_value,
"total value limit")

# Objective is to maximize the total value
m.setObjective(total_value, GRB.MAXIMIZE)

# Optimize model
m.optimize()

for v in m.getVars():
print('%s %g' % (v.varName, v.x))

print('Obj: %g' % m.objVal)

main()

• I am not very familiar with python voice based gurobi programming, can you send me the approximate code? Jun 30 at 4:36
• I am sorry. I start learning optimization since last month through this site and self-study. I haven't used gurobipy before. Jun 30 at 4:39
• Thank you very much for your answer, but I have some problems with your code Jun 30 at 6:43
• After modifying the code, the program is now running properly and outputting the results I need, thank you again Jun 30 at 7:58
• should be m.addConstr instead of model.addConstr in the process_group function. you can use an IDE like pycharm to catch simple mistakes like this one. Jun 30 at 11:28