pythonoptimizationlinear-programminggurobilinear-optimization

Sum of subset of binary variables == 1 in Gurobipy


I am writing a very simple optimization model in Gurobipy but am struggling with the binary variable constraints.

I have 5 materials in 3 groups. The decision variables are whether or not to use one of the materials and are binary. Each decision variable has a cost coefficient and I am minimizing total cost in the objective. The first group has 3 of the materials and the latter 2 groups have just one material in each.

I would like to write a constraint so that the sum of the decision variables in group 1 == 1 and so on... meaning you can only pick one material from each group.

The constraints would look something like this:

x[0] + x[3] + x[4] == 1
x[1] == 1
x[2] == 1

Is there a way to iterate through a list of components by group and to match those against the variable names?

Thank you!


Solution

  • You certainly can use subsets to form constraints, and here it is the best idea. As long as you provide a valid list or set of indices within the larger set, you should be fine.

    Here is an example in gurobipy. CAUTION: My gurobi license is not current so I cannot execute this code, but I think it is correct and should be close enough to demonstrate the concept.

    import gurobipy as gp
    from gurobipy import GRB
    
    materials = list(range(8))
    
    # groups of materials
    groups = {1: {0,2,3},
              2: {1},
              3: {4,5,6,7}}
    
    # a little sanity check for non-duplication and full coverage... OPTIONAL
    assert set.union(*groups.values()) == set(materials)               # full coverage
    assert sum(len(grp) for grp in groups.values()) == len(materials)  # no duplicates
    
    m = gp.Model('example')
    
    m.select = m.addVars(materials, name='select', vtype=GRB.BINARY)
    
    # sum up over each group to limit selection to one...
    # this will make one constraint for each group.
    for grp in groups.values():
        m.addConstr(sum(select[m] for m in grp) <= 1)