Integer allocation and relaxation gaps for indivisible work

Last updated: 5 Oct 20265 min read

tutorial

A fractional allocation can bound an integer plan but cannot schedule part of an indivisible task.

Show the difference with a small case

Queue A reviews take three hours and yield five benefit units; queue B reviews take two hours and yield three. The budget is seven hours. The continuous relaxation could assign 7/3 A reviews and claim 35/3, about 11.67 benefit units. Real reviews are indivisible. The best integer plan is one A and two B reviews: seven hours and 11 units. Feasibility is checked after the integer choice, not assumed from a fractional solution.

Use the relaxation as information

For a maximization problem, the continuous relaxation provides an upper bound on the best integer objective when it contains every integer-feasible plan. The gap between that bound and a valid integer plan helps assess how much improvement might remain. It is not a percentage that can be interpreted without a stated denominator, and it may be weak for some formulations.

Respect dependencies

If every partner review needs a specialist sign-off, the plan may have a second capacity constraint. If two reviews target the same customer escalation, their benefits may not add independently. A linear objective assumes additive marginal benefit; validate that assumption or model the interaction explicitly. Do not increase integer counts beyond the number of eligible cases in each queue.

Choose a method for scale

Brute-force enumeration is transparent for two queues and a small budget. With many queues, dependencies and large capacities, the number of combinations grows quickly; use an appropriate integer-programming solver and retain its status, feasible incumbent and best bound. A time-limited solution may be good enough operationally without being proved optimal. State that distinction in the decision packet.

Make the output auditable

Publish queue counts, hours consumed, expected benefit and every active constraint. Add a simple feasible baseline such as all B reviews under the budget, then show the improvement. Recompute the totals from source data, not only the solver return object. A plan with a higher objective but a hidden policy violation is not a win.

Implementation

def best_small_integer_plan(hour_budget):
    best = (0, 0, 0)  # benefit, queue_a_reviews, queue_b_reviews
    for queue_a_reviews in range(hour_budget // 3 + 1):
        for queue_b_reviews in range(hour_budget // 2 + 1):
            used_hours = 3 * queue_a_reviews + 2 * queue_b_reviews
            if used_hours <= hour_budget:
                benefit = 5 * queue_a_reviews + 3 * queue_b_reviews
                best = max(best, (benefit, queue_a_reviews, queue_b_reviews))
    return best

assert best_small_integer_plan(7) == (11, 1, 2)

Performance and operating cost

The two-loop enumeration uses O((B/3 + 1)(B/2 + 1)) time and O(1) auxiliary space for budget B. That is suitable only for small fixtures; general integer programming can be computationally hard, so larger instances need solver bounds and runtime limits.

Common Mistakes

Do not schedule a fractional review because the relaxed objective looks better.
Do not claim a time-limited integer solution is optimal without a proof or bound.
Do not assume benefits add when actions overlap on the same customer.