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

Question

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?

Answer 1

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$.

Answer 2

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()