1
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$ Jun 30 at 3:32
  • $\begingroup$ 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 $\endgroup$
    – Zying
    Jun 30 at 3:33
  • $\begingroup$ 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}. $\endgroup$ Jun 30 at 3:34
  • $\begingroup$ The value is set randomly,a set may be with only {10,30,40} $\endgroup$
    – Zying
    Jun 30 at 3:36
  • $\begingroup$ Do you want the final sum to be exactly 100? Sometimes, that is impossible. $\endgroup$ Jun 30 at 3:38
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jun 30 at 3:50
  • $\begingroup$ Thanks a lot. I find some timing: towardsdatascience.com/… $\endgroup$ Jun 30 at 3:59
  • 1
    $\begingroup$ Yes, and it is the standard approach. It is not quite knapsack because the RHS is a variable, not a constant. $\endgroup$
    – RobPratt
    Jun 30 at 4:02
  • $\begingroup$ I have added a more general question and answer that address the modeling aspect, independent of solver: or.stackexchange.com/questions/6545/… $\endgroup$
    – RobPratt
    Jul 9 at 14:31
1
$\begingroup$

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()
$\endgroup$
5
  • $\begingroup$ I am not very familiar with python voice based gurobi programming, can you send me the approximate code? $\endgroup$
    – Zying
    Jun 30 at 4:36
  • $\begingroup$ I am sorry. I start learning optimization since last month through this site and self-study. I haven't used gurobipy before. $\endgroup$ Jun 30 at 4:39
  • $\begingroup$ Thank you very much for your answer, but I have some problems with your code $\endgroup$
    – Zying
    Jun 30 at 6:43
  • $\begingroup$ After modifying the code, the program is now running properly and outputting the results I need, thank you again $\endgroup$
    – Zying
    Jun 30 at 7:58
  • $\begingroup$ 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. $\endgroup$ Jun 30 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.