to solve a work scheduling problem to assign
workers to shifts. Here are notes about doing that. This is a common use case,
but isn't explicitly covered in the
The tool is supposed to allocate workers to the shifts to try to cover all the
shifts, give everybody work, and try to match their preferences. I implemented
the tool:
#!/usr/bin/python3
import sys
import os
import re
def report_solution_to_console(vars):
for w in days_of_week:
annotation = ''
if human_annotate is not None:
for s in shifts.keys():
m = re.match(rf' w - ', s)
if not m: continue
if vars[human_annotate][s].value():
annotation = f" ( human_annotate SCHEDULED)"
break
if not len(annotation):
annotation = f" ( human_annotate OFF)"
print(f" w annotation ")
for s in shifts.keys():
m = re.match(rf' w - ', s)
if not m: continue
annotation = ''
if human_annotate is not None:
annotation = f" ( human_annotate shifts[s][human_annotate] )"
print(f" ---- s[m.end():] annotation ")
for h in humans:
if vars[h][s].value():
print(f" h ( shifts[s][h] )")
def report_solution_summary_to_console(vars):
print("\nSUMMARY")
for h in humans:
print(f"-- h ")
print(f" benefit: benefits[h].value():.3f ")
counts = dict()
for a in availabilities:
counts[a] = 0
for s in shifts.keys():
if vars[h][s].value():
counts[shifts[s][h]] += 1
for a in availabilities:
print(f" counts[a] a ")
human_annotate = None
days_of_week = ('SUNDAY',
'MONDAY',
'TUESDAY',
'WEDNESDAY',
'THURSDAY',
'FRIDAY',
'SATURDAY')
humans = ['ALICE', 'BOB',
'CAROL', 'DAVID', 'EVE', 'FRANK', 'GRACE', 'HEIDI', 'IVAN', 'JUDY']
shifts = 'SUNDAY - SANDING 9:00 AM - 4:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'DAVID': 'PREFERRED',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'DISFAVORED',
'HEIDI': 'DISFAVORED',
'IVAN': 'PREFERRED',
'JUDY': 'NEUTRAL' ,
'WEDNESDAY - SAWING 7:30 AM - 2:30 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'DAVID': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'NEUTRAL',
'HEIDI': 'DISFAVORED',
'IVAN': 'PREFERRED',
'EVE': 'REFUSED',
'JUDY': 'REFUSED' ,
'THURSDAY - SANDING 9:00 AM - 4:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'DAVID': 'PREFERRED',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'PREFERRED',
'HEIDI': 'DISFAVORED',
'IVAN': 'PREFERRED',
'JUDY': 'PREFERRED' ,
'SATURDAY - SAWING 7:30 AM - 2:30 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'DAVID': 'PREFERRED',
'FRANK': 'PREFERRED',
'HEIDI': 'DISFAVORED',
'IVAN': 'PREFERRED',
'EVE': 'REFUSED',
'JUDY': 'REFUSED',
'GRACE': 'REFUSED' ,
'SUNDAY - SAWING 9:00 AM - 4:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'DAVID': 'PREFERRED',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'DISFAVORED',
'IVAN': 'PREFERRED',
'JUDY': 'PREFERRED',
'HEIDI': 'REFUSED' ,
'MONDAY - SAWING 9:00 AM - 4:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'DAVID': 'PREFERRED',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'PREFERRED',
'IVAN': 'PREFERRED',
'JUDY': 'PREFERRED',
'HEIDI': 'REFUSED' ,
'TUESDAY - SAWING 9:00 AM - 4:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'DAVID': 'PREFERRED',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'NEUTRAL',
'IVAN': 'PREFERRED',
'JUDY': 'PREFERRED',
'HEIDI': 'REFUSED' ,
'WEDNESDAY - PAINTING 7:30 AM - 2:30 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'NEUTRAL',
'HEIDI': 'DISFAVORED',
'IVAN': 'PREFERRED',
'EVE': 'REFUSED',
'JUDY': 'REFUSED',
'DAVID': 'REFUSED' ,
'THURSDAY - SAWING 9:00 AM - 4:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'DAVID': 'PREFERRED',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'PREFERRED',
'IVAN': 'PREFERRED',
'JUDY': 'PREFERRED',
'HEIDI': 'REFUSED' ,
'FRIDAY - SAWING 9:00 AM - 4:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'DAVID': 'PREFERRED',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'PREFERRED',
'IVAN': 'PREFERRED',
'JUDY': 'DISFAVORED',
'HEIDI': 'REFUSED' ,
'SATURDAY - PAINTING 7:30 AM - 2:30 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'FRANK': 'PREFERRED',
'HEIDI': 'DISFAVORED',
'IVAN': 'PREFERRED',
'EVE': 'REFUSED',
'JUDY': 'REFUSED',
'GRACE': 'REFUSED',
'DAVID': 'REFUSED' ,
'SUNDAY - PAINTING 9:45 AM - 4:45 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'DISFAVORED',
'IVAN': 'PREFERRED',
'JUDY': 'PREFERRED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'MONDAY - PAINTING 9:45 AM - 4:45 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'PREFERRED',
'IVAN': 'PREFERRED',
'JUDY': 'NEUTRAL',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'TUESDAY - PAINTING 9:45 AM - 4:45 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'NEUTRAL',
'IVAN': 'PREFERRED',
'JUDY': 'PREFERRED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'WEDNESDAY - SANDING 9:45 AM - 4:45 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'DAVID': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'NEUTRAL',
'HEIDI': 'DISFAVORED',
'IVAN': 'PREFERRED',
'JUDY': 'NEUTRAL',
'EVE': 'REFUSED' ,
'THURSDAY - PAINTING 9:45 AM - 4:45 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'NEUTRAL',
'IVAN': 'PREFERRED',
'JUDY': 'PREFERRED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'FRIDAY - PAINTING 9:45 AM - 4:45 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'PREFERRED',
'FRANK': 'PREFERRED',
'GRACE': 'PREFERRED',
'IVAN': 'PREFERRED',
'JUDY': 'DISFAVORED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'SATURDAY - SANDING 9:45 AM - 4:45 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'DAVID': 'PREFERRED',
'FRANK': 'PREFERRED',
'HEIDI': 'DISFAVORED',
'IVAN': 'PREFERRED',
'EVE': 'REFUSED',
'JUDY': 'REFUSED',
'GRACE': 'REFUSED' ,
'SUNDAY - PAINTING 11:00 AM - 6:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'HEIDI': 'PREFERRED',
'IVAN': 'NEUTRAL',
'JUDY': 'NEUTRAL',
'DAVID': 'REFUSED' ,
'MONDAY - PAINTING 12:00 PM - 7:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'PREFERRED',
'IVAN': 'NEUTRAL',
'JUDY': 'NEUTRAL',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'TUESDAY - PAINTING 12:00 PM - 7:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'NEUTRAL',
'HEIDI': 'REFUSED',
'JUDY': 'REFUSED',
'DAVID': 'REFUSED' ,
'WEDNESDAY - PAINTING 12:00 PM - 7:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'NEUTRAL',
'JUDY': 'PREFERRED',
'EVE': 'REFUSED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'THURSDAY - PAINTING 12:00 PM - 7:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'NEUTRAL',
'JUDY': 'PREFERRED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'FRIDAY - PAINTING 12:00 PM - 7:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'NEUTRAL',
'JUDY': 'DISFAVORED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'SATURDAY - PAINTING 12:00 PM - 7:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'NEUTRAL',
'FRANK': 'NEUTRAL',
'IVAN': 'NEUTRAL',
'JUDY': 'DISFAVORED',
'EVE': 'REFUSED',
'HEIDI': 'REFUSED',
'GRACE': 'REFUSED',
'DAVID': 'REFUSED' ,
'SUNDAY - SAWING 12:00 PM - 7:00 PM':
'ALICE': 'PREFERRED',
'BOB': 'PREFERRED',
'CAROL': 'NEUTRAL',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'NEUTRAL',
'JUDY': 'PREFERRED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'MONDAY - SAWING 2:00 PM - 9:00 PM':
'ALICE': 'PREFERRED',
'BOB': 'PREFERRED',
'CAROL': 'DISFAVORED',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'DISFAVORED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'TUESDAY - SAWING 2:00 PM - 9:00 PM':
'ALICE': 'PREFERRED',
'BOB': 'PREFERRED',
'CAROL': 'DISFAVORED',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'HEIDI': 'REFUSED',
'JUDY': 'REFUSED',
'DAVID': 'REFUSED' ,
'WEDNESDAY - SAWING 2:00 PM - 9:00 PM':
'ALICE': 'PREFERRED',
'BOB': 'PREFERRED',
'CAROL': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'DISFAVORED',
'EVE': 'REFUSED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'THURSDAY - SAWING 2:00 PM - 9:00 PM':
'ALICE': 'PREFERRED',
'BOB': 'PREFERRED',
'CAROL': 'DISFAVORED',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'DISFAVORED',
'HEIDI': 'REFUSED',
'DAVID': 'REFUSED' ,
'FRIDAY - SAWING 2:00 PM - 9:00 PM':
'ALICE': 'PREFERRED',
'BOB': 'PREFERRED',
'CAROL': 'DISFAVORED',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'HEIDI': 'REFUSED',
'JUDY': 'REFUSED',
'DAVID': 'REFUSED' ,
'SATURDAY - SAWING 2:00 PM - 9:00 PM':
'ALICE': 'PREFERRED',
'BOB': 'PREFERRED',
'CAROL': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'DISFAVORED',
'EVE': 'REFUSED',
'HEIDI': 'REFUSED',
'GRACE': 'REFUSED',
'DAVID': 'REFUSED' ,
'SUNDAY - PAINTING 12:15 PM - 7:15 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'PREFERRED',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'HEIDI': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'NEUTRAL',
'DAVID': 'REFUSED' ,
'MONDAY - PAINTING 2:00 PM - 9:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'DISFAVORED',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'HEIDI': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'DISFAVORED',
'DAVID': 'REFUSED' ,
'TUESDAY - PAINTING 2:00 PM - 9:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'DISFAVORED',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'HEIDI': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'REFUSED',
'DAVID': 'REFUSED' ,
'WEDNESDAY - PAINTING 2:00 PM - 9:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'HEIDI': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'DISFAVORED',
'EVE': 'REFUSED',
'DAVID': 'REFUSED' ,
'THURSDAY - PAINTING 2:00 PM - 9:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'DISFAVORED',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'HEIDI': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'DISFAVORED',
'DAVID': 'REFUSED' ,
'FRIDAY - PAINTING 2:00 PM - 9:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'DISFAVORED',
'EVE': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'GRACE': 'NEUTRAL',
'HEIDI': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'REFUSED',
'DAVID': 'REFUSED' ,
'SATURDAY - PAINTING 2:00 PM - 9:00 PM':
'ALICE': 'NEUTRAL',
'BOB': 'NEUTRAL',
'CAROL': 'DISFAVORED',
'FRANK': 'NEUTRAL',
'HEIDI': 'NEUTRAL',
'IVAN': 'DISFAVORED',
'JUDY': 'DISFAVORED',
'EVE': 'REFUSED',
'GRACE': 'REFUSED',
'DAVID': 'REFUSED'
availabilities = ['PREFERRED', 'NEUTRAL', 'DISFAVORED']
import pulp
prob = pulp.LpProblem("Scheduling", pulp.LpMaximize)
vars = pulp.LpVariable.dicts("Assignments",
(humans, shifts.keys()),
None,None, # bounds; unused, since these are binary variables
pulp.LpBinary)
# Everyone works at least 2 shifts
Nshifts_min = 2
for h in humans:
prob += (
pulp.lpSum([vars[h][s] for s in shifts.keys()]) >= Nshifts_min,
f" h works at least Nshifts_min shifts",
)
# each shift is ~ 8 hours, so I limit everyone to 40/8 = 5 shifts
Nshifts_max = 5
for h in humans:
prob += (
pulp.lpSum([vars[h][s] for s in shifts.keys()]) <= Nshifts_max,
f" h works at most Nshifts_max shifts",
)
# all shifts staffed and not double-staffed
for s in shifts.keys():
prob += (
pulp.lpSum([vars[h][s] for h in humans]) == 1,
f" s is staffed",
)
# each human can work at most one shift on any given day
for w in days_of_week:
for h in humans:
prob += (
pulp.lpSum([vars[h][s] for s in shifts.keys() if re.match(rf' w ',s)]) <= 1,
f" h cannot be double-booked on w "
)
#### Some explicit constraints; as an example
# DAVID can't work any PAINTING shift and is off on Thu and Sun
h = 'DAVID'
prob += (
pulp.lpSum([vars[h][s] for s in shifts.keys() if re.search(r'- PAINTING',s)]) == 0,
f" h can't work any PAINTING shift"
)
prob += (
pulp.lpSum([vars[h][s] for s in shifts.keys() if re.match(r'THURSDAY SUNDAY',s)]) == 0,
f" h is off on Thursday and Sunday"
)
# Do not assign any "REFUSED" shifts
for s in shifts.keys():
for h in humans:
if shifts[s][h] == 'REFUSED':
prob += (
vars[h][s] == 0,
f" h is not available for s "
)
# Objective. I try to maximize the "happiness". Each human sees each shift as
# one of:
#
# PREFERRED
# NEUTRAL
# DISFAVORED
# REFUSED
#
# I set a hard constraint to handle "REFUSED", and arbitrarily, I set these
# benefit values for the others
benefit_availability = dict()
benefit_availability['PREFERRED'] = 3
benefit_availability['NEUTRAL'] = 2
benefit_availability['DISFAVORED'] = 1
# Not used, since this is a hard constraint. But the code needs this to be a
# part of the benefit. I can ignore these in the code, but let's keep this
# simple
benefit_availability['REFUSED' ] = -1000
benefits = dict()
for h in humans:
benefits[h] = \
pulp.lpSum([vars[h][s] * benefit_availability[shifts[s][h]] \
for s in shifts.keys()])
benefit_total = \
pulp.lpSum([benefits[h] \
for h in humans])
prob += (
benefit_total,
"happiness",
)
prob.solve()
if pulp.LpStatus[prob.status] == "Optimal":
report_solution_to_console(vars)
report_solution_summary_to_console(vars)
variable, and the shift schedule and the
workers' preferences are encoded in the
dict. The problem is defined by
a
dict of dicts, each a boolean variable indicating whether a particular
worker is scheduled for a particular shift. We define a set of constraints to
these worker allocations to restrict ourselves to valid solutions. And among
these valid solutions, we try to find the one that maximizes some benefit
function, defined here as:
So for instance each shift that was scheduled as somebody's PREFERRED shift
gives us 3 benefit points. And if all the shifts ended up being PREFERRED, we'd
have a total benefit value of 3*Nshifts. This is impossible, however, because
that would violate some constraints in the problem.
The exact trade-off between the different preferences is set in the
dict. With the above numbers, it's equally good for
somebody to have a NEUTRAL shift and a day off as it is for them to have
DISFAVORED shifts. If we really want to encourage the program to work people as
much as possible (days off discouraged), we'd want to raise the DISFAVORED
threshold.
I run this program and I get:
So we have a solution! We have 108 total benefit points. But it looks a bit
uneven: Judy only works 2 days, while some people work many more: David works 5
for instance. Why is that? I update the program with =human_annotate = 'JUDY'=,
run it again, and it tells me more about Judy's preferences:
This tells us that on Monday Judy does not work, although she marked the SAWING
shift as PREFERRED. Instead David got that shift. What would happen if David
gave that shift to Judy? He would lose 3 points, she would gain 3 points, and
the total would remain exactly the same at 108.
How would we favor a more even distribution? We need some sort of tie-break. I
want to add a nonlinearity to strongly disfavor people getting a low number of
shifts. But PuLP is very explicitly a linear programming solver, and cannot
solve nonlinear problems. Here we can get around this by enumerating each
specific case, and assigning it a nonlinear benefit function. The most obvious
approach is to define another set of boolean variables:
. And then using them to add extra benefit terms, with
values nonlinearly related to
. Something like this:
So in the previous example we considered giving David's 5th shift to Judy, for
her 3rd shift. In that scenario, David's extra benefit would change from -0.2 to
-0.3 (a shift of -0.1), while Judy's would change from -0.8 to -0.5 (a shift of
+0.3). So the balancing out the shifts in this way would work: the solver would
favor the solution with the higher benefit function.
Great. In order for this to work, we need the
variables
to function as intended: they need to be binary indicators of whether a specific
person has that many shifts or not. That would need to be implemented with
constraints. Let's plot it like this:
variable (plotted on the x axis of this
plot) would need to be defined by a set of linear AND constraints to
the true (red) values of this variable from the false (black) values.
As can be seen in this plot, this isn't possible. So this representation does
not work.
How do we fix it? We can use inequality variables instead. I define a different
set of variables
.
The equality variable from before can be expressed as a difference of these
inequality variables:
So we can use two linear constraints to make each of these variables work
properly. To use these in the benefit function we can use the equality
constraint expression from above, or we can use these directly:
In this scenario, David would get a boost of 0.4 from giving up his 5th shift,
while Judy would lose a boost of 0.2 from getting her 3rd, for a net gain of 0.2
benefit points. The exact numbers will need to be adjusted on a case by case
basis, but this works.
The full program, with this and other extra features is available
Like each month, have a look at the work funded by 
Are you a student aspiring to participate in the 
The Open Source Initiative has two classes of board seats: Affiliate seats, and Individual Member seats. In the upcoming election, each affiliate can nominate a candidate, and each affiliate can cast a vote for the Affiliate candidates, but there's only 1 Affiliate seat available. I initially expressed interest in being nominated as an Affiliate candidate via Debian. But since 
dmidecode grep -A8 ^System Information
tells me that the Manufacturer is HP and Product Name is OMEN Transcend Gaming Laptop 14-fb0xxx
I m provisioning a new piece of hardware for my eng consultant and it s proving more difficult than I expected. I must admit guilt for some of this difficulty. Instead of installing using the debian installer on my keychain, I dd d the pv block device of the 16 inch 2023 version onto the partition set aside from it. I then rebooted into rescue mode and cleaned up the grub config, corrected the EFI boot partition s path in /etc/fstab, ran the grub installer from the rescue menu, and rebooted.
On the initial boot of the system, X or Wayland or whatever is supposed to be talking to this vast array of GPU hardware in this device, it s unable to do more than create a black screen on vt1. It s easy enough to switch to vt2 and get a shell on the installed system. So I m doing that and investigating what s changed in Trixie. It seems like it s pretty significant. Did they just throw out Keith Packard s and Behdad Esfahbod s work on font rendering? I don t understand what s happening in this effort to abstract to a simpler interface. I ll probably end up reading more about it.
In an effort to have Debian re-configure the system for Desktop use, I have uninstalled as many packages as I could find that were in the display and human interface category, or were firmware/drivers for devices not present in this Laptop s SoC. Some commands I used to clear these packages and re-install connamon follow:
Almost two years ago, Twitter launched encrypted direct messages. I wrote about their technical implementation 
A few months ago 
Update 20250309 13:20-03:00 - How to help
A friend of mine living in the USA sent me this link to help the flood victims: 
The "real" thing
Let's get to the heavy, heartbreaker part. I did go to downtown Bah a Blanca, but during night, so let me share some links, most of them in Spanish, but images are images:
In today s digital landscape, social media is more than just a communication tool it is the primary medium for global discourse. Heads of state, corporate leaders and cultural influencers now broadcast their statements directly to the world, shaping public opinion in real time. However, the dominance of a few centralized platforms X/Twitter, Facebook and YouTube raises critical concerns about control, censorship and the monopolization of information. Those who control these networks effectively wield significant power over public discourse.
In response, a new wave of distributed social media platforms has emerged, each built on different decentralized protocols designed to provide greater autonomy, censorship resistance and user control. While 
Mastodon was created in 2016 by 
Interestingly,