## 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¶

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.

## 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 LocalSolver’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 LocalSolver 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-1][j in 0..n-1]( 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 LocalSolver against MIP solvers on this Quadratic Assignment Problem.

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

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

if (inFileName == nil) throw usage;

// Distance between locations
// Flow between facilites (indices of the map must start at 0
// to access it with an "at" operator")
}

/* Declares 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-1][j in 0..n-1](A[i][j] * B[p[i]][p[j]]);
minimize obj;
}

/* Parameterizes the solver. */
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 300;
}

/* Writes 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-1]{
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_10_5/bin/python
python qap.py instances/esc32a.dat
########## qap.py ##########

import localsolver
import sys

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

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

with localsolver.LocalSolver() as ls:

#
#

# 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)]

#
# Declares 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()

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

#
# Writes 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\localsolver105.lib
qap instances\esc32a.dat
Compilation / Execution (Linux)
g++ qap.cpp -I/opt/localsolver_10_5/include -llocalsolver105 -lpthread -o qap
./qap instances/esc32a.dat
//********* qap.cpp *********

#include <iostream>
#include <fstream>
#include <vector>
#include "localsolver.h"

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<lsint> > B;

// Solver.
LocalSolver localsolver;

// LS Program variables
LSExpression p;

// Objective
LSExpression obj;

ifstream infile;
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) {
// Declares 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++) {
}

// Minimize the sum of product distance*flow
obj = model.sum();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
}
}
model.minimize(obj);

model.close();

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

localsolver.solve();
}

// Writes the solution in a file with the following format:
//  - n objValue
//  - permutation p
void writeSolution(const string& fileName) {
ofstream outfile;
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] : "300";

try {
Qap model;
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
/********** Qap.cs **********/

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;

// Solver.
LocalSolver localsolver;

// LS Program variables
LSExpression p;

// Objective
LSExpression obj;

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

{
}

{
string[] splitted = text.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);

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

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

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

void Solve(int limit)
{
// Declares 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)
}
}
model.Minimize(obj);

model.Close();

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

localsolver.Solve();
}

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

using (Qap model = new Qap())
{
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_10_5/bin/localsolver.jar
java -cp /opt/localsolver_10_5/bin/localsolver.jar:. Qap instances/esc32a.dat
/********** Qap.java **********/

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;

// Solver.
private final LocalSolver localsolver;

// LS Program variables
private LSExpression p;

// Objective
private LSExpression obj;

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

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) {
// 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(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();
}
}
model.minimize(obj);

model.close();

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

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

try (LocalSolver localsolver = new LocalSolver()) {
Qap model = new Qap(localsolver);