Binary Integer Programming Problem - Enforce Zeros on Certain Groups

Question

I'm working on a binary integer programming problem using pulp. I have a vector X = [x_1, x_2, x_3, . . . , x_n]. I have enforced a number of simple constraints. I have a bunch of groups in the data say group0 = [x_1, x_2], group1 = [x_3, x_4] . . .. My goal is to maximize the number of groups where all the variables in the group are zero. So effectively the objective function would be

def objective(group):
    if sum(group) == 0:
        return 1
    else
        return 0
maximize sum(objective(group_i) for group_i in groups)

But Im not sure if there is a way to do this with a linear solver.

Also, to make things concrete this is essentially a scheduling problem. Each X_i represents a shift where x_i == 1 mean the worker is scheduled and x_i == 0 means they are not scheduled. Each group represents requests for time off, and we want to maximize the number of these requests that we can grant while ensuring staffing is sufficient/a number of other constraints are met.

A simple example with no objective function would be

import pulp

# Initialize problem and variables
num_variables = 10
prob = pulp.LpProblem("Shift_Scheduling", pulp.LpMinimize)
x = pulp.LpVariable.dicts("shift", range(num_variables), cat='Binary')

# Add simple constraint
prob += pulp.lpSum(x[i] for i in range(num_variables)) == int(num_variables * 0.8)

# Solve the problem
solver = pulp.PULP_CBC_CMD(timeLimit=30, threads=4, gapRel=0.5)
prob.solve(solver)

# View results
for i in range(num_variables):
    print(f"var {i} ==", pulp.value(x[i]))

Output: 
var 0 == 1.0
var 1 == 1.0
var 2 == 1.0
var 3 == 1.0
var 4 == 1.0
var 5 == 1.0
var 6 == 1.0
var 7 == 1.0
var 8 == 0.0
var 9 == 0.0

I have tried giving each group a weight so group0 would have weight == 1, group1 would have weight == 2 . . . This way, we incentivize the solver to zero out groups with lower weight. For example . . .

# Initialize problem and variables
num_variables = 10
prob = pulp.LpProblem("Shift_Scheduling", pulp.LpMaximize)
x = pulp.LpVariable.dicts("shift", range(num_variables), cat='Binary')

# Create groups [(0, 1), (2, 3), . . . ]
groups = [(i, i + 1) for i in range(0, num_variables, 2)]
# Get weights for each group - group_0 has weight 1, group_1 has wieght 2 . . .
group_weights = {}
for weight, group in enumerate(groups):
    for index in group:
        group_weights[index] = weight + 1

# Add objective function
prob += pulp.lpSum(group_weights[i] * x[i] for i in range(num_variables))

# Add simple constraint
prob += pulp.lpSum(x[i] for i in range(num_variables)) == int(num_variables * 0.8)

# Solve the problem
solver = pulp.PULP_CBC_CMD(timeLimit=60, threads=4, gapRel=0.5)
prob.solve(solver)

# View results
for i in range(num_variables):
    print(f"var {i} ==", pulp.value(x[i]))

output:
var 0 == 0.0
var 1 == 0.0
var 2 == 1.0
var 3 == 1.0
var 4 == 1.0
var 5 == 1.0
var 6 == 1.0
var 7 == 1.0
var 8 == 1.0
var 9 == 1.0

However I don't like this solution because we are giving priority to certain groups, it feels a bit hacky. It seems like as the constraints becomes more complex, this could lead to cases where the solver zeros out lots of low weight groups but solutions could exist where greater numbers of groups could be zeroed out if each group was prioritized equally. Of course, we want to maximize the number of time off requests that are granted and we don't want to arbitrarily prioritize one request over another.

Also if this is not possible with pulp I would be open to using other solvers, its just a significant amount of work has already been done by my team using pulp and I would rather not have to redo the work if its at all possible.

Answer 1

Let $G$ be the set of groups. For group $g\in G$, let $I_g$ be the set of indices $i$ in that group. Introduce binary decision variable $y_g$ to indicate whether $x_i=0$ for all $i\in I_g$. To maximize the number of groups that have all $x_i=0$, maximize $\sum_g y_g$ subject to linear constraints $$x_i \le 1-y_g \quad \text{for all $g\in G$ and $i\in I_g$} \tag1\label1$$ that enforce the logical implication $y_g \implies \lnot x_i$. Alternatively, you can aggregate \eqref{1} and instead enforce $$\sum_{i\in I_g} x_i \le |I_g|(1-y_g) \quad \text{for all $g\in G$} \tag2\label2$$ As usual, the aggregated version \eqref{2} is weaker but yields a smaller LP so might perform better.

Answer 2

This is just a complement to the answer given by @RobPratt.

Let an instance for our scheduling problem be given by:

• $W$ the set of workers;
• $G$ the set of groups, such that $g \in G$ if $g \subseteq W$; And
• $D \in \mathbb{N}$ be the minimum number of workers required for the scheduling.

We, then, can proceed with our BIP modeling with the following variables:

• $x_w \in \mathbb{B}$ is equals to $1$, if worker $w$ is allocated for the scheduling, and $0$ otherwise, $\forall w \in W$;
• $y_g \in \mathbb{B}$ is equals to $1$, if some $w \in g$ is allocated for the scheduling, and $0$ otherwise, $\forall g \in G$;

With the following objective function:

$\min \sum_{g \in G} y_g$

And with the following constraints:

• $\sum_{w \in W} x_w = D$, stating the mandatory number of workers;
• $x_w \leqslant y_g$ $\forall g \in G, w \in g$, stating that, when a worker $w$ is allocated, then all the groups containing this worker must be taken as allocated as well.

An improvement, could be:

• $y_g \leqslant \sum_{w \in g} x_w$ $\forall g \in G$, stating that, when a group $g$ is taken as allocated, then at least one worker belonging to this group must be allocated as well.

Below follows an implementation:

    import pulp

    # Initialize problem
    W = list(range(10))
    n = len(W)
    
    G = list(map(lambda w: (w, w+ 1), range(0, n, 2)))
    
    D = 0.8 * n
    
    # Initialize model
    prob = pulp.LpProblem("Shift_Scheduling", pulp.LpMinimize)
    
    # Initialize variables
    x = pulp.LpVariable.dicts("worker_allocated", W, cat='Binary')
    y = dict({g: pulp.LpVariable("group_allocated " + str(g), cat='Binary') for g in G})
    
    # Add obj. func.
    prob += pulp.lpSum(map(lambda g: y[g], G))
    
    # Add min demand constraint
    prob += pulp.lpSum(map(lambda w: x[w], W)) == D
    
    # Add group flag lifting constraint
    for g in G:
        for w in g:
            prob += x[w] <= y[g]
    
    # Add improvement
    for g in G:
        prob += y[g] <= pulp.lpSum(map(lambda w: x[w], g))
    
    # Solve the problem
    solver = pulp.PULP_CBC_CMD(timeLimit=30, threads=4, gapRel=0.5)
    prob.solve(solver)
    
    # View results
    for w in W:
        print(f"x {w} ==", pulp.value(x[w]))
    
    for g in G:
        print("y %s == %.1f" % (str(g), pulp.value(y[g])))

For more related problems, you may consider the set covering and set packing problems.

Regards.