Quadratic Assignment (QAP)

Principles learned

  • Define the actual set of decision variables

  • Add a list decision variable

  • Access the list elements with an at operator

  • Constrain the number of elements in the list with operator count

  • Access a multi-dimensional array with an at operator

  • Get the value of a list variable

Problem

../_images/qap.svg

The Quadratic Assignment Problem (QAP) is a fundamental combinatorial problem in the branch of optimization and operations research. It has emerged from facility location applications and models the following real-life problem. You are given a set of n facilities and a set of n locations. A distance is specified for each pair of locations, and a flow (or weight) is specified for each pair of facilities (e.g. the amount of supplies transported between the pair). The problem is to assign each facility to one location with the goal of minimizing the sum of the distances multiplied by the corresponding flows. Intuitively, the cost function encourages factories with high flows between each other to be placed close together. The problem statement resembles that of the assignment problem, except that the cost function is expressed in terms of quadratic inequalities, hence the name. For more details, we invite the reader to have a look at the QAPLIB webpage.

Download the example


Data

Instance files are from the QAPLIB.

The format of the data is as follows:

  • Number of points

  • Matrix A: distance between each location

  • Matrix B: flow between each facility

Program

Using Hexaly’s non-linear operators, modeling the problem is really straightforward (no linearization required). It is not even necessary to introduce a quadratic number of decision variables x[f][l]. Indeed, we are considering a permutation of all facilities, which can be modeled directly in Hexaly with a single list variable. The only constraint is for the list to contain all the facilities. As for the objective, it is the sum, for each pair of locations (l1,l2), of the product between the distance between l1 and l2 and the flow between the factory on l1 and the factory on l2. This is written with “at” operators that can retrieve a member of an array indexed by an expression (see this page for more information about the “at” operator).

obj <- sum[i in 0...n][j in 0...n]( A[i][j] * B[p[i]][p[j]]);

With such a compact model, instances with thousands of points can be tackled with no resource issues.

You can find below this model for each language. You can also have a look at a performance comparison of Hexaly Optimizer against MIP solvers on this Quadratic Assignment Problem.

Execution:
localsolver qap.lsp inFileName=instances/esc32a.dat [lsTimeLimit=] [solFileName=]
use io;

/* Read instance data */
function input() {
    local usage = "Usage: localsolver qap.lsp "
            + "inFileName=inName [solFileName=solName] [lsTimeLimit=limit]";

    if (inFileName == nil) throw usage;

    local inFile = io.openRead(inFileName);
    n = inFile.readInt();
    
    // Distance between locations
    A[i in 0...n][j in 0...n] = inFile.readInt();
    // Flow between facilites (indices of the map must start at 0
    // to access it with an "at" operator")
    B[i in 0...n][j in 0...n] = inFile.readInt();
}


/* Declare the optimization model */
function model() {
    // Permutation such that p[i] is the facility on the location i
    p <- list(n);

    // The list must be complete
    constraint count(p) == n;

    // Minimize the sum of product distance*flow
    obj <- sum[i in 0...n][j in 0...n](A[i][j] * B[p[i]][p[j]]);
    minimize obj;
}

/* Parametrize the solver */
function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 30;
}

/* Write the solution in a file with the following format:
 *  - n objValue
 *  - permutation p */
function output() {
    if (solFileName == nil) return;

    local solFile = io.openWrite(solFileName);
    solFile.println(n + " " + obj.value);
    for [i in 0...n] {
        solFile.print(p.value[i] + " ");
    }
    solFile.println();
}
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python qap.py instances\esc32a.dat
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_5/bin/python
python qap.py instances/esc32a.dat
import localsolver
import sys

if len(sys.argv) < 2:
    print("Usage: python qap.py inputFile [outputFile] [timeLimit]")
    sys.exit(1)


def read_integers(filename):
    with open(filename) as f:
        return [int(elem) for elem in f.read().split()]


with localsolver.LocalSolver() as ls:
    #
    # Read instance data
    #
    file_it = iter(read_integers(sys.argv[1]))

    # Number of points
    n = next(file_it)

    # Distance between locations
    A = [[next(file_it) for j in range(n)] for i in range(n)]
    # Flow between factories
    B = [[next(file_it) for j in range(n)] for i in range(n)]

    #
    # Declare the optimization model
    #
    model = ls.model

    # Permutation such that p[i] is the facility on the location i
    p = model.list(n)

    # The list must be complete
    model.constraint(model.eq(model.count(p), n))

    # Create B as an array to be accessed by an at operator
    array_B = model.array(model.array(B[i]) for i in range(n))

    # Minimize the sum of product distance*flow
    obj = model.sum(A[i][j] * model.at(array_B, p[i], p[j])
                    for j in range(n) for i in range(n))
    model.minimize(obj)

    model.close()

    # Parameterize the solver
    if len(sys.argv) >= 4:
        ls.param.time_limit = int(sys.argv[3])
    else:
        ls.param.time_limit = 30
    ls.solve()

    #
    # Write the solution in a file with the following format:
    #  - n objValue
    #  - permutation p
    #
    if len(sys.argv) >= 3:
        with open(sys.argv[2], 'w') as outfile:
            outfile.write("%d %d\n" % (n, obj.value))
            for i in range(n):
                outfile.write("%d " % p.value[i])
            outfile.write("\n")
Compilation / Execution (Windows)
cl /EHsc qap.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver125.lib
qap instances\esc32a.dat
Compilation / Execution (Linux)
g++ qap.cpp -I/opt/localsolver_12_5/include -llocalsolver125 -lpthread -o qap
./qap instances/esc32a.dat
#include "localsolver.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace localsolver;
using namespace std;

class Qap {
public:
    // Number of points
    int n;

    // Distance between locations
    vector<vector<int>> A;
    // Flow between facilites
    vector<vector<int>> B;

    // LocalSolver
    LocalSolver localsolver;

    // LS Program variables
    LSExpression p;

    // Objective
    LSExpression obj;

    // Read instance data
    void readInstance(const string& fileName) {
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);
        infile.open(fileName.c_str());

        infile >> n;

        A.resize(n);
        for (int i = 0; i < n; ++i) {
            A[i].resize(n);
            for (int j = 0; j < n; ++j) {
                infile >> A[i][j];
            }
        }

        B.resize(n);
        for (int i = 0; i < n; ++i) {
            B[i].resize(n);
            for (int j = 0; j < n; ++j) {
                infile >> B[i][j];
            }
        }
    }

    void solve(int limit) {
        // Declare the optimization model
        LSModel model = localsolver.getModel();

        // Permutation such that p[i] is the facility on the location i
        p = model.listVar(n);

        // The list must be complete
        model.constraint(model.count(p) == n);

        // Create B as an array to be accessed by an at operator
        LSExpression arrayB = model.array();
        for (int i = 0; i < n; ++i) {
            arrayB.addOperand(model.array(B[i].begin(), B[i].end()));
        }

        // Minimize the sum of product distance * flow
        obj = model.sum();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                obj.addOperand(A[i][j] * model.at(arrayB, p[i], p[j]));
            }
        }
        model.minimize(obj);

        model.close();

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);

        localsolver.solve();
    }

    /* Write the solution in a file with the following format:
     *  - n objValue
     *  - permutation p */
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());

        outfile << n << " " << obj.getValue() << "\n";
        LSCollection pCollection = p.getCollectionValue();
        for (int i = 0; i < n; ++i) {
            outfile << pCollection.get(i) << " ";
        }
        outfile << endl;
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: qap inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }

    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "30";

    try {
        Qap model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(solFile);
        return 0;
    } catch (const exception& e) {
        cerr << "An error occurred:" << e.what() << endl;
        return 1;
    }
}
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc Qap.cs /reference:localsolvernet.dll
Qap instances\esc32a.dat
using System;
using System.IO;
using localsolver;

public class Qap : IDisposable
{
    // Number of points
    int n;

    // Distance between locations
    int[][] A;

    // Flow between facilites
    long[][] B;

    // LocalSolver
    LocalSolver localsolver;

    // LS Program variables
    LSExpression p;

    // Objective
    LSExpression obj;

    public Qap()
    {
        localsolver = new LocalSolver();
    }

    private int readInt(string[] splittedLine, ref int lastPosRead)
    {
        lastPosRead++;
        return int.Parse(splittedLine[lastPosRead]);
    }

    // Read instance data
    void ReadInstance(string fileName)
    {
        string text = File.ReadAllText(fileName);
        string[] splitted = text.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
        int lastPosRead = -1;

        n = readInt(splitted, ref lastPosRead);

        A = new int[n][];
        for (int i = 0; i < n; ++i)
        {
            A[i] = new int[n];
            for (int j = 0; j < n; ++j)
                A[i][j] = readInt(splitted, ref lastPosRead);
        }

        B = new long[n][];
        for (int i = 0; i < n; ++i)
        {
            B[i] = new long[n];
            for (int j = 0; j < n; ++j)
                B[i][j] = readInt(splitted, ref lastPosRead);
        }
    }

    public void Dispose()
    {
        if (localsolver != null)
            localsolver.Dispose();
    }

    void Solve(int limit)
    {
        // Declare the optimization model
        LSModel model = localsolver.GetModel();

        // Permutation such that p[i] is the facility on the location i
        p = model.List(n);

        // The list must be complete
        model.Constraint(model.Count(p) == n);

        // Create B as an array to be accessed by an at operator
        LSExpression arrayB = model.Array(B);

        // Minimize the sum of product distance*flow
        obj = model.Sum();
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                // arrayB[a, b] is a shortcut for accessing the multi-dimensional array
                // arrayB with an at operator. Same as model.At(arrayB, a, b)
                obj.AddOperand(A[i][j] * arrayB[p[i], p[j]]);
            }
        }
        model.Minimize(obj);

        model.Close();

        // Parametrize the solver
        localsolver.GetParam().SetTimeLimit(limit);

        localsolver.Solve();
    }

    // Write the solution in a file with the following format:
    //  - n objValue
    //  - permutation p
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(n + " " + obj.GetValue());
            LSCollection pCollection = p.GetCollectionValue();
            for (int i = 0; i < n; ++i)
                output.Write(pCollection.Get(i) + " ");
            output.WriteLine();
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Qap inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "30";

        using (Qap model = new Qap())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}
Compilation / Execution (Windows)
javac Qap.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Qap instances\esc32a.dat
Compilation / Execution (Linux)
javac Qap.java -cp /opt/localsolver_12_5/bin/localsolver.jar
java -cp /opt/localsolver_12_5/bin/localsolver.jar:. Qap instances/esc32a.dat
import java.util.*;
import java.io.*;
import localsolver.*;

public class Qap {
    // Number of points
    private int n;

    // Distance between locations
    private int[][] A;

    // Flow between facilites
    private long[][] B;

    // LocalSolver
    private final LocalSolver localsolver;

    // LS Program variables
    private LSExpression p;

    // Objective
    private LSExpression obj;

    private Qap(LocalSolver localsolver) {
        this.localsolver = localsolver;
    }

    // Read instance data
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            n = input.nextInt();

            A = new int[n][n];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    A[i][j] = input.nextInt();
                }
            }

            B = new long[n][n];
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    B[i][j] = input.nextInt();
                }
            }
        }
    }

    private void solve(int limit) {
        // Declare the optimization model
        LSModel model = localsolver.getModel();

        // Permutation such that p[i] is the facility on the location i
        p = model.listVar(n);
        
        // [] operator is not overloaded, so we create a LSExpression array for easier access
        // of the elements of the permitation (instead of creating an at operator by hand
        // everytime we want to access an element in the list)
        LSExpression[] pElements = new LSExpression[n];
        for (int i = 0; i < n; ++i) {
            pElements[i] = model.at(p, i);
        }

        // The list must be complete
        model.constraint(model.eq(model.count(p), n));

        // Create B as an array to be accessed by an at operator
        LSExpression arrayB = model.array(B);

        // Minimize the sum of product distance * flow
        obj = model.sum();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                LSExpression prod = model.prod();
                prod.addOperand(A[i][j]);
                prod.addOperand(model.at(arrayB, pElements[i], pElements[j]));
                obj.addOperand(prod);
            }
        }
        model.minimize(obj);

        model.close();

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);
        localsolver.solve();
    }

    /*
     * Write the solution in a file with the following format:
     * - n objValue
     * - permutation p
     */
    private void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            output.println(n + " " + obj.getValue());
            LSCollection pCollection = p.getCollectionValue();
            for (int i = 0; i < n; ++i)
                output.print(pCollection.get(i) + " ");
            output.println();
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Usage: java Qap inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "30";

        try (LocalSolver localsolver = new LocalSolver()) {
            Qap model = new Qap(localsolver);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}