Quadratic Assignment Problem (QAP) - Coding

The Quadratic Assignment Problem (QAP) is an optimization problem that deals with assigning a set of facilities to a set of locations, considering the pairwise distances and flows between them.

The problem is to find the assignment that minimizes the total cost or distance, taking into account both the distances and the flows.

The distance matrix and flow matrix, as well as restrictions to ensure each facility is assigned to exactly one location and each location is assigned to exactly one facility, can be used to formulate the QAP as a quadratic objective function.

The QAP is a well-known example of an NP-hard problem, which means that for larger cases, computing the best solution might be difficult. As a result, many algorithms and heuristics have been created to quickly identify approximations of answers.

There are various types of algorithms for different problem structures, such as:

Precise algorithms
Approximation algorithms
Metaheuristics like genetic algorithms and simulated annealing
Specialized algorithms

Example: Given four facilities (F1, F2, F3, F4) and four locations (L1, L2, L3, L4). We have a cost matrix that represents the pairwise distances or costs between facilities. Additionally, we have a flow matrix that represents the interaction or flow between locations. Find the assignment that minimizes the total cost based on the interactions between facilities and locations. Each facility must be assigned to exactly one location, and each location can only accommodate one facility.

Facilities cost matrix:

	L1	L2	L3	L4
F1	0	2	3	1
F2	2	0	1	4
F3	3	1	0	2
F4	1	4	2	0

Flow matrix:

	F1	F2	F3	F4
L1	0	1	2	3
L2	1	0	4	2
L3	2	4	0	1
L4	3	2	1	0

To solve the QAP, various optimization techniques can be used, such as mathematical programming, heuristics, or metaheuristics. These techniques aim to explore the search space and find the optimal or near-optimal solution.

The solution to the QAP will provide an assignment of facilities to locations that minimizes the overall cost.

C++

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int calculateTotalCost(const vector<vector<int>>& facilities, const vector<vector<int>>& locations, const vector<int>& assignment) {
    int totalCost = 0;
    int n = facilities.size();
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int facility1 = assignment[i];
            int facility2 = assignment[j];
            int location1 = i;
            int location2 = j;
             
            totalCost += facilities[facility1][facility2] * locations[location1][location2];
        }
    }
 
    return totalCost;
}
 
int main() {
    // Facilities cost matrix
    vector<vector<int>> facilities = {
        {0, 2, 3, 1},
        {2, 0, 1, 4},
        {3, 1, 0, 2},
        {1, 4, 2, 0}
    };
 
    // Flow matrix
    vector<vector<int>> locations = {
        {0, 1, 2, 3},
        {1, 0, 4, 2},
        {2, 4, 0, 1},
        {3, 2, 1, 0}
    };
 
    int n = facilities.size();
 
    // Generate initial assignment (0, 1, 2, 3)
    vector<int> assignment(n);
    for (int i = 0; i < n; i++) {
        assignment[i] = i;
    }
 
    // Calculate the initial total cost
    int minCost = calculateTotalCost(facilities, locations, assignment);
    vector<int> minAssignment = assignment;
 
    // Generate all permutations of the assignment
    while (next_permutation(assignment.begin(), assignment.end())) {
        int cost = calculateTotalCost(facilities, locations, assignment);
        if (cost < minCost) {
            minCost = cost;
            minAssignment = assignment;
        }
    }
 
    // Print the optimal assignment and total cost
    cout << "Optimal Assignment: ";
    for (int i = 0; i < n; i++) {
        cout << "F" << (minAssignment[i] + 1) << "->L" << (i + 1) << " ";
    }
    cout << endl;
    cout << "Total Cost: " << minCost << endl;
 
    return 0;
}

Java

// Java code for the above approach
 
import java.util.*;
 
class GFG {
 
    static void swap(List<Integer> assignment, int left, int right)
    {
        // Swap the data
        int temp = assignment.get(left);
        assignment.set(left, assignment.get(right));
        assignment.set(right, temp);
    }
 
    // Function to reverse the sub-list
    // starting from left to the right
    // both inclusive
    static void reverse(List<Integer> assignment, int left, int right)
    {
        // Reverse the sub-list
        while (left < right) {
            swap(assignment, left, right);
            left++;
            right--;
        }
    }
 
    // Function to find the next permutation
    // of the given integer list
    static boolean next_permutation(List<Integer> assignment)
    {
        // find the size of the list
        int size = assignment.size();
 
        // If the given dataset is empty
        // or contains only one element
        // next_permutation is not possible
        if (size <= 1)
            return false;
 
        int last = size - 2;
 
        // find the longest non-increasing suffix
        // and find the pivot
        while (last >= 0) {
            if (assignment.get(last) < assignment.get(last + 1)) {
                break;
            }
            last--;
        }
 
        // If there is no increasing pair
        // there is no higher order permutation
        if (last < 0)
            return false;
 
        int nextGreater = size - 1;
 
        // Find the rightmost successor to the pivot
        for (int i = size - 1; i > last; i--) {
            if (assignment.get(i) > assignment.get(last)) {
                nextGreater = i;
                break;
            }
        }
 
        // Swap the successor and the pivot
        swap(assignment, nextGreater, last);
 
        // Reverse the suffix
        reverse(assignment, last + 1, size - 1);
 
        // Return true as the next_permutation is done
        return true;
    }
 
    static int calculateTotalCost(List<List<Integer> > facilities,
                                       List<List<Integer> > locations,
                                       List<Integer> assignment)
    {
        int totalCost = 0;
        int n = facilities.size();
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int facility1 = assignment.get(i);
                int facility2 = assignment.get(j);
                int location1 = i;
                int location2 = j;
 
                totalCost += facilities.get(facility1).get(facility2)
                                  *locations.get(location1).get(location2);
            }
        }
 
        return totalCost;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Facilities cost matrix
        List<List<Integer> > facilities
            = Arrays.asList(Arrays.asList(0, 2, 3, 1),
                            Arrays.asList(2, 0, 1, 4),
                            Arrays.asList(3, 1, 0, 2),
                            Arrays.asList(1, 4, 2, 0));
 
        // Flow matrix
        List<List<Integer> > locations
            = Arrays.asList(Arrays.asList(0, 1, 2, 3),
                            Arrays.asList(1, 0, 4, 2),
                            Arrays.asList(2, 4, 0, 1),
                            Arrays.asList(3, 2, 1, 0));
 
        int n = facilities.size();
 
        // Generate initial assignment (0, 1, 2, 3)
        List<Integer> assignment = new ArrayList<>();
 
        for (int i = 0; i < n; i++) {
            assignment.add(i);
        }
 
        // Calculate the initial total cost
        int minCost = calculateTotalCost(facilities, locations, assignment);
        List<Integer> minAssignment = assignment;
 
        // Generate all permutations of the assignment
        while (next_permutation(assignment)) {
            int cost = calculateTotalCost(facilities, locations, assignment);
            if (cost < minCost) {
                minCost = cost;
                minAssignment = assignment;
            }
        }
 
        // Print the optimal assignment and total cost
        System.out.print("Optimal Assignment: ");
 
        for (int i = 0; i < n; i++) {
            System.out.print("F" + (minAssignment.get(i) + 1) + "->L" + (i + 1) + " ");
        }
 
        System.out.print("\nTotal Cost: " + minCost);
    }
}
 
// This code is contributed by ragul21

Python3

def calculateTotalCost(facilities, locations, assignment):
    totalCost = 0
    n = len(facilities)
 
    for i in range(n):
        for j in range(n):
            facility1 = assignment[i]
            facility2 = assignment[j]
            location1 = i
            location2 = j
 
            totalCost += facilities[facility1][facility2] * locations[location1][location2]
 
    return totalCost
 
if __name__ == "__main__":
    # Facilities cost matrix
    facilities = [
        [0, 2, 3, 1],
        [2, 0, 1, 4],
        [3, 1, 0, 2],
        [1, 4, 2, 0]
    ]
 
    # Flow matrix
    locations = [
        [0, 1, 2, 3],
        [1, 0, 4, 2],
        [2, 4, 0, 1],
        [3, 2, 1, 0]
    ]
 
    n = len(facilities)
 
    # Generate initial assignment (0, 1, 2, 3)
    assignment = list(range(n))
 
    # Calculate the initial total cost
    minCost = calculateTotalCost(facilities, locations, assignment)
    minAssignment = assignment.copy()
 
    import itertools
 
    # Generate all permutations of the assignment
    for assignment in itertools.permutations(assignment):
        cost = calculateTotalCost(facilities, locations, list(assignment))
        if cost < minCost:
            minCost = cost
            minAssignment = list(assignment)
 
    # Print the optimal assignment and total cost
    print("Optimal Assignment: ", end="")
    for i in range(n):
        print(f"F{minAssignment[i] + 1}->L{i + 1} ", end="")
    print()
    print(f"Total Cost: {minCost}")

C#

using System;
using System.Collections.Generic;
using System.Linq;
 
class FacilityLocation
{
    static int CalculateTotalCost(List<List<int>> facilities, List<List<int>> locations, List<int> assignment)
    {
        int totalCost = 0;
        int n = facilities.Count;
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int facility1 = assignment[i];
                int facility2 = assignment[j];
                int location1 = i;
                int location2 = j;
 
                totalCost += facilities[facility1][facility2] * locations[location1][location2];
            }
        }
 
        return totalCost;
    }
 
    static void Main()
    {
        // Facilities cost matrix
        List<List<int>> facilities = new List<List<int>>
        {
            new List<int> { 0, 2, 3, 1 },
            new List<int> { 2, 0, 1, 4 },
            new List<int> { 3, 1, 0, 2 },
            new List<int> { 1, 4, 2, 0 }
        };
 
        // Flow matrix
        List<List<int>> locations = new List<List<int>>
        {
            new List<int> { 0, 1, 2, 3 },
            new List<int> { 1, 0, 4, 2 },
            new List<int> { 2, 4, 0, 1 },
            new List<int> { 3, 2, 1, 0 }
        };
 
        int n = facilities.Count;
 
        // Generate initial assignment (0, 1, 2, 3)
        List<int> assignment = Enumerable.Range(0, n).ToList();
 
        // Calculate the initial total cost
        int minCost = CalculateTotalCost(facilities, locations, assignment);
        List<int> minAssignment = assignment;
 
        // Generate all permutations of the assignment
        while (NextPermutation(assignment))
        {
            int cost = CalculateTotalCost(facilities, locations, assignment);
            if (cost < minCost)
            {
                minCost = cost;
                minAssignment = assignment.ToList();
            }
        }
 
        // Print the optimal assignment and total cost
        Console.Write("Optimal Assignment: ");
        for (int i = 0; i < n; i++)
        {
            Console.Write($"F{minAssignment[i] + 1}->L{i + 1} ");
        }
        Console.WriteLine();
        Console.WriteLine($"Total Cost: {minCost}");
    }
 
    static bool NextPermutation(List<int> list)
    {
        int i = list.Count - 2;
        while (i >= 0 && list[i] >= list[i + 1])
        {
            i--;
        }
        if (i < 0)
        {
            return false;
        }
 
        int j = list.Count - 1;
        while (list[j] <= list[i])
        {
            j--;
        }
 
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
 
        Reverse(list, i + 1, list.Count - 1);
        return true;
    }
 
    static void Reverse(List<int> list, int start, int end)
    {
        while (start < end)
        {
            int temp = list[start];
            list[start] = list[end];
            list[end] = temp;
            start++;
            end--;
        }
    }
}

Javascript

function calculateTotalCost(facilities, locations, assignment) {
    let totalCost = 0;
    const n = facilities.length;
 
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            const facility1 = assignment[i];
            const facility2 = assignment[j];
            const location1 = i;
            const location2 = j;
 
            totalCost += facilities[facility1][facility2] * locations[location1][location2];
        }
    }
 
    return totalCost;
}
 
function generateInitialAssignment(n) {
    const assignment = [];
    for (let i = 0; i < n; i++) {
        assignment[i] = i;
    }
    return assignment;
}
 
function findOptimalAssignment(facilities, locations) {
    const n = facilities.length;
 
    // Generate initial assignment (0, 1, 2, 3)
    const initialAssignment = generateInitialAssignment(n);
 
    let minCost = calculateTotalCost(facilities, locations, initialAssignment);
    let minAssignment = [...initialAssignment];
 
    // Generate all permutations of the assignment
    const factorial = (n) => {
        let result = 1;
        for (let i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    };
 
    const numberOfPermutations = factorial(n);
 
    for (let i = 0; i < numberOfPermutations; i++) {
        const assignment = generateInitialAssignment(n);
        if (i > 0) {
            // Generate the next permutation
            let j = n - 1;
            while (j > 0 && assignment[j - 1] >= assignment[j]) {
                j--;
            }
            let k = n - 1;
            while (assignment[j - 1] >= assignment[k]) {
                k--;
            }
            [assignment[j - 1], assignment[k]] = [assignment[k], assignment[j - 1]];
            k = n - 1;
            while (j < k) {
                [assignment[j], assignment[k]] = [assignment[k], assignment[j]];
                j++;
                k--;
            }
        }
 
        const cost = calculateTotalCost(facilities, locations, assignment);
        if (cost < minCost) {
            minCost = cost;
            minAssignment = [...assignment];
        }
    }
 
    return { minAssignment, minCost };
}
 
// Facilities cost matrix
const facilities = [
    [0, 2, 3, 1],
    [2, 0, 1, 4],
    [3, 1, 0, 2],
    [1, 4, 2, 0]
];
 
// Flow matrix
const locations = [
    [0, 1, 2, 3],
    [1, 0, 4, 2],
    [2, 4, 0, 1],
    [3, 2, 1, 0]
];
 
const n = facilities.length;
 
const { minAssignment, minCost } = findOptimalAssignment(facilities, locations);
 
// Print the optimal assignment and total cost
console.log("Optimal Assignment: " + minAssignment.map((facility, location) => `F${facility + 1}->L${location + 1}`).join(" "));
console.log("Total Cost: " + minCost);

Output

Optimal Assignment: F1->L1 F3->L2 F2->L3 F4->L4 
Total Cost: 44

The solution generates all possible permutations of the assignment and calculates the total cost for each assignment. The optimal assignment is the one that results in the minimum total cost.

To calculate the total cost, we look at each pair of facilities in (i, j) and their respective locations (location1, location2). We then multiply the cost of assigning facility1 to facility2 (facilities[facility1][facility2]) with the flow from location1 to location2 (locations[location1][location2]). This process is done for all pairs of facilities in the assignment, and the costs are summed up.

Overall, the output tells us that assigning facilities to locations as F1->L1, F3->L2, F2->L3, and F4->L4 results in the minimum total cost of 44. This means that Facility 1 is assigned to Location 1, Facility 3 is assigned to Location 2, Facility 2 is assigned to Location 3, and Facility 4 is assigned to Location 4, yielding the lowest cost based on the given cost and flow matrices.This example demonstrates the process of finding the optimal assignment by considering the costs and flows associated with each facility and location. The objective is to find the assignment that minimizes the total cost, taking into account the interactions between facilities and locations.

Applications of the QAP include facility location, logistics, scheduling, and network architecture, all of which require effective resource allocation and arrangement.

Reffered: https://www.geeksforgeeks.org

Algorithms

Related
Game of Matchsticks
Check if it is possible to construct an array with the given conditions
Introduction to Knapsack Problem, its Types and How to solve them
10 Most Important Algorithms For Coding Interviews
Difference between Greedy Algorithm and Divide and Conquer Algorithm

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	13