Quadratic Assignment Problem (QAP)

import hexaly.optimizer
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 hexaly.optimizer.HexalyOptimizer() as optimizer:
    #
    # 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 = optimizer.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(B)

    # 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 optimizer
    if len(sys.argv) >= 4:
        optimizer.param.time_limit = int(sys.argv[3])
    else:
        optimizer.param.time_limit = 30
    optimizer.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")

#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace hexaly;
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;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Hexaly Program variables
    HxExpression p;

    // Objective
    HxExpression 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
        HxModel model = optimizer.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
        HxExpression 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 optimizer
        optimizer.getParam().setTimeLimit(limit);

        optimizer.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";
        HxCollection 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;
    }
}

using System;
using System.IO;
using Hexaly.Optimizer;

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

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

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

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Hexaly Program variables
    HxExpression p;

    // Objective
    HxExpression obj;

    public Qap()
    {
        optimizer = new HexalyOptimizer();
    }

    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 (optimizer != null)
            optimizer.Dispose();
    }

    void Solve(int limit)
    {
        // Declare the optimization model
        HxModel model = optimizer.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
        HxExpression 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 optimizer
        optimizer.GetParam().SetTimeLimit(limit);

        optimizer.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());
            HxCollection 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);
        }
    }
}

import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

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

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

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

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Hexaly Program variables
    private HxExpression p;

    // Objective
    private HxExpression obj;

    private Qap(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    // 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
        HxModel model = optimizer.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 HxExpression 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)
        HxExpression[] pElements = new HxExpression[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
        HxExpression 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) {
                HxExpression 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 optimizer
        optimizer.getParam().setTimeLimit(limit);
        optimizer.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());
            HxCollection 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 (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            Qap model = new Qap(optimizer);
            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);
        }
    }
}