Quadratic assignment problem¶

/********** Qap.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;

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

    // Distance between locations
    int[][] A;
    // Flow between facilites
    long[][] B;

    /* Solver. */
    LocalSolver localsolver;

    /* LS Program variables */
    LSExpression p;

    /* Objective */
    LSExpression obj;

    /* Reads instance data */
    void readInstance(String fileName){
        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();
                }
            }
        } catch(IOException e){
            e.printStackTrace();
        }
    }

    void solve(int limit){
        try{
            localsolver = new LocalSolver();

            /* Declares 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();
            for(int i = 0; i < n; i++) {
                arrayB.addOperand(model.array(B[i]));
            }

            // 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();

            /* Parameterizes the solver. */
            LSPhase phase = localsolver.createPhase();
            phase.setTimeLimit(limit);
            localsolver.solve();

        }catch(LSException e){
            System.out.println("LSException:" + e.getMessage());
            System.exit(1);
        }
    }

    /* Writes the solution in a file with the following format:
     *  - n objValue
     *  - permutation p  */
    void writeSolution(String fileName){
        try{
            BufferedWriter output = new BufferedWriter(new FileWriter(fileName));
            output.write(n + " " + obj.getValue() + "\n");
            LSCollection pCollection = p.getCollectionValue();
            for (int i = 0; i < n; i++) 
                output.write(pCollection.get(i) + " ");
            output.write("\n");
            output.close();

        } catch(IOException e){
            e.printStackTrace();
        }
    }

    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] : "300";

        Qap model = new Qap();
        model.readInstance(instanceFile);
        model.solve(Integer.parseInt(strTimeLimit));
        if(outputFile != null) {
            model.writeSolution(outputFile);
        }
    }
}