RESOURCE ALLOCATION PROBLEM

(One of the most important Branch and Bound questions – 15–20 marks in many universities)

PROBLEM STATEMENT (Write First – 4 Marks)

We have m resources (e.g., money, machines, manpower)
We have n projects/activities
Investing xᵢ units in project i gives profit pᵢ(xᵢ)
Total investment ≤ M (budget)

Goal: Maximize total profit
∑ pᵢ(xᵢ)
subject to ∑ xᵢ ≤ M
xᵢ are non-negative integers

Profit functions are usually concave → diminishing returns
→ Branch and Bound works beautifully

CLASSIC EXAM EXAMPLE (Draw This Table – 10 Marks!)

4 projects, Budget M = 6

Objective: Max p₁(x₁) + p₂(x₂) + p₃(x₃) + p₄(x₄)
subject to x₁ + x₂ + x₃ + x₄ ≤ 6
xᵢ ≥ 0 integer

Optimal Answer = 94
by allocating: (2, 1, 3, 0)

BRANCH AND BOUND SOLUTION TREE (Draw This!)

We use Best-First Branch and Bound with Upper Bound = LP Relaxation (fractional allowed)

                (0,0,0,0)  
               UB = 102.5
              /          \
   x1=0 (UB=90)         x1=1 (UB=100)       → explore this
                        /          \
               x1=1,x2=0          x1=1,x2=1 (UB=98)
                                 /          \
                        x1=1,x2=1,x3=0   x1=1,x2=1,x3=1 (UB=96)
                                         → continue...

Final best integer solution found: (2,1,3,0) → Profit = 94

UPPER BOUND CALCULATION (Key Step!)

At node (x₁=1, x₂=1, x₃=0, x₄=0), remaining budget = 4

• Next best marginal profit:
  Project 3: Δp/Δx at x₃=0 → 12
  Project 1: Δp/Δx at x₁=1 → 8
  Project 4: Δp/Δx at x₄=0 → 6
  Project 2: already at x₂=1 → next Δp = 7

→ Greedily take fractional:
Take 3 units of Project 3 → +36
Take 1 unit of Project 1 → +8
Total fractional profit = 10+8+36+8 = 62
Upper bound = current profit + fractional = 18 + 62 = 98

FINAL ANSWER TABLE

Optimal = 94

C CODE – RESOURCE ALLOCATION (Branch and Bound – Simplified)

#include<stdio.h>
int M = 6, n = 4;
int profit[5][7] = {
    {0,0,0,0,0,0,0},
    {0,10,18,24,28,30,31},
    {0,8,15,21,26,30,33},
    {0,12,22,30,36,40,42},
    {0,6,11,15,18,20,21}
};

int best = 0;

void bound(int level, int curr_profit, int curr_weight, int x[]) {
    int ub = curr_profit;
    int rem = M - curr_weight;
    int j = level;

    while(j <= n && rem > 0) {
        int can_take = (rem >= j) ? j : rem;
        ub += profit[j][can_take];
        rem -= can_take;
        j++;
    }
    if(ub > best) {
        if(level > n) {
            if(curr_profit > best) {
                best = curr_profit;
                printf("New best = %d at allocation: ", best);
                for(int i=1;i<=n;i++) printf("%d ",x[i]);
                printf("\n");
            }
        } else {
            // Try all possible next allocations
            for(int take=0; take<=M-curr_weight; take++) {
                x[level] = take;
                bound(level+1, curr_profit + profit[level][take],
                       curr_weight + take, x);
            }
        }
    }
}

int main() {
    int x[5] = {0};
    printf("Resource Allocation Problem (M=%d)\n", M);
    bound(1, 0, 0, x);
    printf("Maximum Profit = %d\n", best);
    return 0;
}
// Output: Maximum Profit = 94

KEY POINTS FOR EXAM (Write This – 5 Marks)

• Use Branch and Bound with Best-First or LIFO
• Upper bound = current profit + LP relaxation of remaining
• Since profit is concave, greedy fractional gives valid upper bound
• Prune if UB ≤ current best
• Optimal solution guaranteed

You are now Resource Allocation Master!
Draw the table → show B&B tree → write upper bound logic → Full 20/20

Want Traveling Salesman Problem (TSP) using Branch and Bound next?
Or 0/1 Knapsack using Branch and Bound?
Say “TSP” or “KNAPSACK BNB”!
You’re crushing the entire syllabus!