Repository navigation
Fix the infeasible shift cap in the workforce MILP notebook - #188
ramakrishnap-nv merged 2 commits into
Conversation
The "Adding Additional Constraints" section of the workforce MILP notebook caps each worker at 4 shifts, but the constraint sums over all 14 shifts of the two-week schedule. Seven workers at 4 shifts give at most 28 assignments while the shifts require 51, so the re-solve is infeasible: the notebook prints "Solver status: Infeasible" and "No optimal solution found", leaving nothing to compare. Apply the cap per week, as the code comment says (Mon1-Sun7 and Mon8-Sun14). The re-solve is then feasible and the cap binds: total labor cost rises from $468 to $486 and no worker takes more than 4 shifts in either week. Signed-off-by: Max Freedom Pollard <[email protected]> Co-Authored-By: Claude Opus 5.5 <[email protected]>
ramakrishnap-nv
left a comment
ramakrishnap-nv
left a comment
There was a problem hiding this comment.
LGTM. I re-solved the notebook's model independently with SciPy/HiGHS from the data in the notebook and reproduced your numbers:
- no cap: $468
- the old cap over all 14 shifts (7 workers × 4 = 28 < 51 required): infeasible
- the new per-week cap of 4: feasible, $486
- a two-week cap: 7 is infeasible, 8 gives $484 (as you said)
The split shift_names[:7] / [7:] is correct because the dict keeps Mon1–Sun14 order, and the markdown and print text now match the code. I haven't run it on cuOpt either.
Two minor notes:
- Week 2 needs 28 staff, which is exactly 7 workers × 4, so every worker must work exactly 4 shifts in week 2. That's fine and is what makes the cap bind, but a one-line note in the markdown would help readers see why the cost rises.
- The conclusion still says "limit worker shifts"; optionally say "per week" there too.
ramakrishnap-nv
left a comment
ramakrishnap-nv
left a comment
There was a problem hiding this comment.
Tested on real cuOpt 26.10.0 (GPU: Quadro RTX 8000, CUDA 13.3) by running the whole notebook with nbconvert, on main and on this branch.
main: the re-solve is infeasible (presolve finds it infeasible, objective$nan, "No optimal solution found").- This PR:
Optimal, objective $486.00, gap 0.00%. Every shift gets its required staff and no worker has more than 4 shifts in either week (Amy 3/4, Bob 0/4, the other five 4/4).
This matches the numbers in the description. The worker assignments differ from the PR's HiGHS run (e.g. Dan and Ed have 8 shifts), which is expected since several optimal solutions exist at $486. Fix confirmed.
Week 2 needs 28 staff, exactly 7 workers x 4 shifts, so under the cap every worker works exactly 4 shifts in week 2. Say so in the markdown above the constraint, and say "per week" in the conclusion. Signed-off-by: Max Freedom Pollard <[email protected]> Co-Authored-By: Claude Opus 5.5 <[email protected]>
|
Thanks for checking it on cuOpt. I added a line under the constraint heading explaining that week 2 needs 28 staff, so every worker works exactly 4 shifts that week, and changed the conclusion to say per week. |
|
Thank you @MaxFreedomPollard for the contribution |
The "Adding Additional Constraints" section of
workforce_optimization/workforce_optimization_milp.ipynbis meant to cap each worker at 4 shifts per week. The constraint actually sums over all 14 shifts of the two-week schedule (Mon1 to Sun14). Seven workers at 4 shifts give at most 28 assignments, but the shifts require 51. The re-solve is therefore infeasible, and the section ends with no solution to compare against the first one.The last version of the notebook with saved outputs (commit 5bc07bd, run on cuOpt 25.10) shows this:
The outputs were stripped later, and the notebook CI does not catch it because no cell raises. The cost-vs-fairness sweep in #151 shows the same thing on cuOpt 26.4: every cap of 7 or fewer total shifts is infeasible.
This change applies the cap per week (Mon1-Sun7 and Mon8-Sun14), as the code comment already says, and updates the markdown above the cell to match. With the fix, the re-solve is feasible and the cap binds: total labor cost rises from $468 to $486, and no worker takes more than 4 shifts in either week.
Testing
I have no GPU, so I could not run this on cuOpt. To check the notebook's logic, I ran its code cells with a small PuLP/HiGHS stand-in for the
cuopt.linear_programmingcalls it makes:Infeasible, withObjective value: $nan.Optimalat $486. Every shift has its required staff, every assignment respects availability, and each worker has at most 4 shifts per week (Dan and Ed drop from 11 shifts to 8, and Bob takes 4).The new cell uses only API calls the notebook already makes:
LinearExpression +=andproblem.addConstraint(expr <= k, name=...). Cell outputs stay stripped.workforce_optimization_multiobjective.ipynbsweeps its own two-week cap and is unchanged. If you would rather keep a two-week cap here, the smallest feasible value is 8 (cost $484).🤖 Generated with Claude Code