Complicated constraint with logical operators in PuLP

Question

I have an optimization problem that I am trying to solve with PuLP.

1. All the variables are Booleans.
2. The variables that are "selected" will be true, all others false.
3. Objective function is simple: each selected variable has a constant reward.
4. so optimal solution if there is no constraint would be all variables turned on (true)
5. sadly there are constraints that won't allow all to be turned on :)

There are two types of constraints:

1. simple constraint that takes a list of variable indexes, where zero or one is allowed to be turned on. That would be expressed as pulp.lpSum(variables[str(i)] for i in indexes) <= 1
2. more complicated constraint that takes two arrays as input.
   1. zero or one elements may be selected from first array
   2. zero, one, or many elements may be selected from second array
   3. if no element is selected from first array, then no element should be selected from second
   4. if an element is selected from first array, then at least one element should be selected from the second. And vice-versa.

Here's some code that demonstrates it. The code does not work as I would like, because I don't know how to specify the more complicated constraint type:

from unittest import TestCase
import pulp
class IpModelTestCase(TestCase):
def test_pulp_with_weird_constraint(self):
    self.count = 20
    self.constrain_sums = [[0, 1, 2, 3, 4],
                           [5, 6, 7, 8, 9],
                           [10, 11, 12, 13, 14],
                           [15, 16, 17, 18, 19]]
    self.constrain_sums_both_zero_or_one_and_one_or_greater = [([0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
                                                                [10, 11, 12, 13, 14, 15, 16, 17, 18, 19])]

    model = pulp.LpProblem('pulp', pulp.LpMaximize)
    rewards = [3] * self.count

    variables = pulp.LpVariable.dicts('option', indexs=[str(i) for i in range(self.count)], cat=pulp.LpBinary)

    # set the objective function
    model += pulp.lpSum([rewards[i] * variables[str(i)] for i in range(self.count)])

    # these constraints are straightforward. 
    # enforces: pick at most one index from each list
    for indexes in self.constrain_sums:
        model += pulp.lpSum(variables[str(i)] for i in indexes) <= 1

    # Here is where I am stuck. The "pseudocode" below describes what I intend the constraint to do,
    # but it does not work, I think because this whole mess is not a single pure linear expression.
    # Rather it's 3 different LP combined with and/or logic operators
    for indexes_zero_or_one, indexes_zero_or_one_or_greater in self.constrain_sums_both_zero_or_one_and_one_or_greater:
        model += (
                (
                    # choose one index from first list AND choose one or more from the second.
                        pulp.lpSum(variables[str(i)] for i in indexes_zero_or_one) == 1
                        and
                        pulp.lpSum(variables[str(i)] for i in indexes_zero_or_one_or_greater) >= 1
                )
                or
                (
                    # OR, if no index from first list is chosen, then don't choose any from the second list either.
                        pulp.lpSum(variables[str(i)] for i in indexes_zero_or_one) +
                        pulp.lpSum(variables[str(i)] for i in indexes_zero_or_one_or_greater) == 0
                )

        )

    print(model)

    # solve it
    model.solve(pulp.PULP_CBC_CMD())
    selected = [int(i) for i, var in variables.items() if var.varValue > 0.99]
    print(selected)

See the "here is where I am stuck" comment above for the part I am stuck on. How to express the more complicated constraint as a single linear expression? Just not sure how to do it. Is it possible?

Output of the code above for completeness:

pulp:
MAXIMIZE
3*option_0 + 3*option_1 + 3*option_10 + 3*option_11 + 3*option_12 + 3*option_13 + 3*option_14 + 3*option_15 + 3*option_16 + 3*option_17 + 3*option_18 + 3*option_19 + 3*option_2 + 3*option_3 + 3*option_4 + 3*option_5 + 3*option_6 + 3*option_7 + 3*option_8 + 3*option_9 + 0
SUBJECT TO
_C1: option_0 + option_1 + option_2 + option_3 + option_4 <= 1
_C2: option_5 + option_6 + option_7 + option_8 + option_9 <= 1
_C3: option_10 + option_11 + option_12 + option_13 + option_14 <= 1
_C4: option_15 + option_16 + option_17 + option_18 + option_19 <= 1
_C5: option_10 + option_11 + option_12 + option_13 + option_14 + option_15

option_16 + option_17 + option_18 + option_19 >= 1

VARIABLES
0 <= option_0 <= 1 Integer
0 <= option_1 <= 1 Integer
0 <= option_10 <= 1 Integer
0 <= option_11 <= 1 Integer
0 <= option_12 <= 1 Integer
0 <= option_13 <= 1 Integer
0 <= option_14 <= 1 Integer
0 <= option_15 <= 1 Integer
0 <= option_16 <= 1 Integer
0 <= option_17 <= 1 Integer
0 <= option_18 <= 1 Integer
0 <= option_19 <= 1 Integer
0 <= option_2 <= 1 Integer
0 <= option_3 <= 1 Integer
0 <= option_4 <= 1 Integer
0 <= option_5 <= 1 Integer
0 <= option_6 <= 1 Integer
0 <= option_7 <= 1 Integer
0 <= option_8 <= 1 Integer
0 <= option_9 <= 1 Integer
Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019
command line - /home/jhersch/.virtualenvs/gemini3.6.9/lib/python3.6/site-packages/pulp/apis/../solverdir/cbc/linux/64/cbc /tmp/938110e6df59477d9d411715c91ac428-pulp.mps max branch printingOptions all solution /tmp/938110e6df59477d9d411715c91ac428-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 10 COLUMNS
At line 101 RHS
At line 107 BOUNDS
At line 128 ENDATA
Problem MODEL has 5 rows, 20 columns and 30 elements
Coin0008I MODEL read with 0 errors
Continuous objective value is 12 - 0.00 seconds
Cgl0008I 4 inequality constraints converted to equality constraints
Cgl0004I processed model has 0 rows, 0 columns (0 integer (0 of which binary)) and 0 elements
Cbc3007W No integer variables - nothing to do
Cuts at root node changed objective from -12 to -1.79769e+308
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Result - Optimal solution found
Objective value:                12.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00
[0, 5, 10, 15]

The output is not desired because:

1. the last constraint _C5 is incomplete. It's only part of the more complicated constraint I really want to express.
2. the output [0, 5, 10, 15] is not what I want. It violates the complicated constraint (because I wasn't able to express it correctly). It violates it because indexes 0 and 5 are not allowed to both be chosen. Only zero or one elements should be selected from [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

EDIT: For completness, here it is fixed up with Rob's solution:

    def test_pulp_with_weird_constraint(self):
        self.count = 20
        self.constrain_sums = [[0, 1, 2, 3, 4],
                               [5, 6, 7, 8, 9],
                               [10, 11, 12, 13, 14],
                               [15, 16, 17, 18, 19]]
        self.constrain_sums_both_zero_or_one_and_one_or_greater = [([0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
                                                                    [10, 11, 12, 13, 14, 15, 16, 17, 18, 19])]
    model = pulp.LpProblem('pulp', pulp.LpMaximize)
    rewards = [3] * self.count

    variables = pulp.LpVariable.dicts('option', indexs=list(range(self.count)), cat=pulp.LpBinary)

    # set the objective function
    model += pulp.lpSum([rewards[i] * variables[i] for i in range(self.count)])

    # these constraints are straightforward. enforces pick at most one index from each list
    for indexes in self.constrain_sums:
        model += pulp.lpSum(variables[i] for i in indexes) <= 1

    for indexes_zero_or_one, indexes_zero_or_one_or_greater in self.constrain_sums_both_zero_or_one_and_one_or_greater:
        # zero or one elements selected from first array
        model += (pulp.lpSum(variables[i] for i in indexes_zero_or_one) <= 1)
        # if no element is selected from first array, then no element should be selected from second
        for index in indexes_zero_or_one_or_greater:
            model += (pulp.lpSum(variables[i] for i in indexes_zero_or_one) >= variables[index])

        # if an element is selected from first array, then at least one element should be selected from the second
        model += (pulp.lpSum(variables[i] for i in indexes_zero_or_one) <=
                  pulp.lpSum(variables[i] for i in indexes_zero_or_one_or_greater))

    # solve it
    model.solve(pulp.PULP_CBC_CMD())
    selected = [int(i) for i, var in variables.items() if var.varValue > 0.99]
    self.assertEqual([0, 10, 15], selected)

Answer 1

Suppose your two arrays are indexed by $I$ and $J$, and let $x_i$ be the binary variable.

1. zero or one elements may be selected from first array: $$\sum_{i\in I} x_i \le 1 \tag1$$

2. zero, one, or many elements may be selected from second array: no constraint needed here

3. if no element is selected from first array, then no element should be selected from second: $$x_j \le \sum_{i\in I} x_i \quad \text{for $j\in J$} \tag2$$

4. if an element is selected from first array, then at least one element should be selected from the second: $$\sum_{i\in I} x_i \le \sum_{j\in J} x_j \tag3$$

The "And vice-versa" part is already enforced by $(2)$.

Note that a natural but weak alternative to $(3)$ is $$x_i \le \sum_{j\in J} x_j \quad \text{for $i\in I$} \tag4$$ But $(3)$ is a strengthening of $(4)$ based on $(1)$, as described in How can I strengthen a family of constraints in the presence of a clique constraint?