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. Thanks!

Answer 1

Sure, totally doable and quite common. The missing pieces are:

1. A binary variable to indicate if any particular group is used. You have an "or" condition here that if any employee in the group is used, you want it to represent that true state, so typically an "or" condition requires another variable.
2. Some semblance of group assignments
3. A linking constraint to connect employees => groups. I used a big-M constraint. If it isn't clear what is goin on there, make a logic table.

The code below will assign 2 workers from group 1 because the weighting on group 1 is less than group 2.

Code

# group minimizer
import pulp
from pulp import LpVariable, LpProblem, LpBinary, lpSum

### DATA
employees = [f'e{i}' for i in range(5)]
e_groups = {1: employees[:3],
            2: employees[3:]}

grp_weights = {1: 0.5, 2: 0.6}

### LP

prob = LpProblem('group_min')

use_group = LpVariable.dicts('use_grp', indices=e_groups.keys(), cat=LpBinary)
use_employee = LpVariable.dicts('use_e', indices=employees, cat=LpBinary)

### OBJ:  minimize groups
prob += sum(grp_weights[g]*use_group[g] for g in e_groups.keys())


### CONSTRAINTS
# Assign at least 2 employees
prob += lpSum(use_employee) >= 2

# link employee usage to group usage with big-M constraint
for g in e_groups.keys():
    prob += use_group[g] * len(e_groups[g]) >= sum(use_employee[e] for e in e_groups[g])

print(prob)

prob.solve()

for e in employees:
    if use_employee[e].varValue > 0.1:
        print(f'use employee:  {e}')