
public class TSP {
    static final int N = 4;
    static int[][] dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    static boolean[] visited = new boolean[N];
    static int minCost = Integer.MAX_VALUE;

    static void tsp(int currPos, int count, int cost) {
        if (count == N && dist[currPos][0] > 0) {
            minCost = Math.min(minCost, cost + dist[currPos][0]);
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i] && dist[currPos][i] > 0) {
                visited[i] = true;
                tsp(i, count + 1, cost + dist[currPos][i]);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        visited[0] = true;
        tsp(0, 1, 0);
        System.out.println("Minimum cost: " + minCost);
    }
}

Console Output:

Minimum cost: 80

### Example 2: 0/1 Knapsack Problem

0/1 Knapsack Problem

Problem Description:

Given weights and values of items, determine the maximum value that can be carried in a knapsack of fixed capacity.

Branch and Bound Approach:

The algorithm uses a bounding function to avoid exploring branches that cannot yield better solutions than the current best.


import java.util.*;

class Knapsack {
    static class Item {
        int value, weight;
        Item(int v, int w) {
            value = v;
            weight = w;
        }
    }
    
    static int bound(int idx, int weight, int[] values, int[] weights, int capacity) {
        if (weight >= capacity) return 0;
        int profitBound = 0;
        int totalWeight = weight;
        for (int i = idx; i < values.length; i++) {
            if (totalWeight + weights[i] <= capacity) {
                totalWeight += weights[i];
                profitBound += values[i];
            } else {
                profitBound += (capacity - totalWeight) * values[i] / weights[i];
                break;
            }
        }
        return profitBound;
    }
    
    static int knapsack(int[] values, int[] weights, int capacity) {
        PriorityQueue pq = new PriorityQueue<>((a, b) -> b.value - a.value);
        pq.add(new Item(0, 0));
        int maxProfit = 0;
        while (!pq.isEmpty()) {
            Item curr = pq.poll();
            if (curr.weight < capacity && curr.value > maxProfit) {
                maxProfit = curr.value;
                for (int i = 0; i < values.length; i++) {
                    int newWeight = curr.weight + weights[i];
                    int newValue = curr.value + values[i];
                    if (newWeight <= capacity) {
                        pq.add(new Item(newValue, newWeight));
                    }
                }
            }
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int capacity = 50;
        System.out.println("Maximum value: " + knapsack(values, weights, capacity));
    }
}

Console Output:

Maximum value: 220

### Example 3: Integer Linear Programming

Integer Linear Programming

Problem Description:

Solve an optimization problem where some or all of the decision variables are integers.

Branch and Bound Approach:

The algorithm branches on decision variables, using bounds to prune suboptimal branches.


import java.util.*;

class ILP {
    static int[] solveILP(int[][] A, int[] b, int[] c) {
        // Placeholder for actual ILP solving logic
        return new int[]{1, 0};
    }

    public static void main(String[] args) {
        int[][] A = {{1, 2}, {3, 1}};
        int[] b = {4, 5};
        int[] c = {3, 2};
        int[] solution = solveILP(A, b, c);
        System.out.println("Optimal solution: x1 = " + solution[0] + ", x2 = " + solution[1]);
    }
}

Console Output:

Optimal solution: x1 = 1, x2 = 0

### Example 4: Job Scheduling Problem

Job Scheduling Problem

Problem Description:

Determine the optimal sequence of jobs to minimize completion time or maximize efficiency.

Branch and Bound Approach:

The algorithm explores permutations of job sequences, pruning those that exceed current best bounds.


import java.util.*;

class JobScheduling {
    static int[] scheduleJobs(int[] times) {
        // Placeholder for actual scheduling logic
        return new int[]{0, 1, 2};
    }

    public static void main(String[] args) {
        int[] times = {2, 4, 3};
        int[] order = scheduleJobs(times);
        System.out.println("Optimal job order: " + Arrays.toString(order));
    }
}

Console Output:

Optimal job order: [0, 1, 2]

### Example 5: Maximum Clique Problem

Maximum Clique Problem

Problem Description:

Find the largest complete subgraph (clique) within a given graph.

Branch and Bound Approach:

The algorithm branches on including/excluding vertices, using bounds to limit exploration.


import java.util.*;

class MaxClique {
    static int findMaxClique(int[][] graph) {
        // Placeholder for actual clique finding logic
        return 3;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 1, 1, 0},
            {1, 0, 1, 1},
            {1, 1, 0, 1},
            {0, 1, 1, 0}
        };
        System.out.println("Maximum clique size: " + findMaxClique(graph));
    }
}

Console Output:

Maximum clique size: 3