Showing posts with label Branch and Bound. Show all posts
Showing posts with label Branch and Bound. Show all posts

Saturday, February 18, 2023

BRANCH AND BOUND : C CODE for JOB ASSIGNMENT PROBLEM

C code to solve JOB ASSIGNMENT problem using Branch and Bound.

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#define MAX_JOBS 10

int costMatrix[MAX_JOBS][MAX_JOBS];

int numJobs;

int minCost = INT_MAX;

int bestAssignment[MAX_JOBS];

void branchAndBound(int assignment[MAX_JOBS], int numAssigned, int costSoFar)

{

 if (numAssigned == numJobs) {

 // All jobs have been assigned, so update the best assignment if the current cost is lower

 if (costSoFar < minCost) {

 minCost = costSoFar;

 for (int i = 0; i < numJobs; i++) {

 bestAssignment[i] = assignment[i];

 }

 }

 } else {

 // Assign the next job to each available worker and branch on the resulting cost

 for (int i = 0; i < numJobs; i++) {

 if (assignment[i] == -1) {

 // This job has not been assigned yet

 int newAssignment[MAX_JOBS];

 for (int j = 0; j < numJobs; j++) {

 newAssignment[j] = assignment[j];

 }

 newAssignment[i] = numAssigned;

 int newCost = costSoFar + costMatrix[numAssigned][i];

 if (newCost < minCost) {

 // Only explore this branch if it could potentially lead to a better solution

 branchAndBound(newAssignment, numAssigned + 1, newCost);

 }

 }

 }

 }

}

int main()

{

 // Read input from file or user input

 printf("Enter the number of jobs: ");

 scanf("%d", &numJobs);

 printf("Enter the cost matrix:\n");

 for (int i = 0; i < numJobs; i++) {

 for (int j = 0; j < numJobs; j++) {

 scanf("%d", &costMatrix[i][j]);

 }

 }

 // Initialize the assignment to all unassigned

 int assignment[MAX_JOBS];

 for (int i = 0; i < numJobs; i++) {

 assignment[i] = -1;

 }

 // Solve the problem using branch and bound

 branchAndBound(assignment, 0, 0);

 // Print the best assignment and its cost

 printf("Best assignment: ");

 for (int i = 0; i < numJobs; i++) {

 printf("(%d, %d) ", bestAssignment[i], i);

 }

 printf("\nCost: %d\n", minCost);

 return 0;

}




GRAPH ALGORITHMS : FLOYD-WARSHAL -Displaying DISTANCE MATRIX and PI MATRIX using C PROGRAM

Modify the following Floyd-Warshall algorithm by introducing a π( pi ) table as per the class’s discussion. Here you can write one function...