1 Telar

Quadratic Assignment Problem Solution

Program¶

Thanks to LocalSolver’s non-linear operators, the model is really straightforward (no linearization required). It is not even necessary to introduce a quadratic number of decision variables . Indeed what we are considering is a permuation of all facilities, what 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. It will be 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).

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

You will 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.

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

localsolver qap.lsp inFileName=instances/esc32a.dat [lsTimeLimit=] [solFileName=]

/********** qap.lsp **********/useio;/* Reads instance data */functioninput(){localusage="Usage : localsolver qap.lsp "+"inFileName=inName [solFileName=solName] [lsTimeLimit=limit]";if(inFileName==nil)throwusage;localinFile=io.openRead(inFileName);n=inFile.readInt();// Distance between locationsA[0..n-1][0..n-1]=inFile.readInt();// Flow between facilites (indices of the map must start at 0// to access it with an "at" operator")B[0..n-1][0..n-1]=inFile.readInt();}/* Declares the optimization model */functionmodel(){// Permutation such that p[i] is the facility on the location ip<-list(n);// The list must be completeconstraintcount(p)==n;// Minimize the sum of product distance*flowobj<-sum[iin0..n-1][jin0..n-1](A[i][j]*B[p[i]][p[j]]);minimizeobj;}/* Parameterizes the solver. */functionparam(){if(lsTimeLimit==nil)lsTimeLimit=300;}/* Writes the solution in a file with the following format: * - n objValue * - permutation p */functionoutput(){if(solFileName==nil)return;localsolFile=io.openWrite(solFileName);solFile.println(n+" "+obj.value);for[iin0..n-1]{solFile.print(p.value[i]+" ");}solFile.println();}
Execution (Windows)

set PYTHONPATH=%LS_HOME%\bin\python27\

python qap.py instances\esc32a.dat

Execution (Linux)

export PYTHONPATH=/opt/localsolver_XXX/bin/python27/

python qap.py instances/esc32a.dat

########## qap.py ##########importlocalsolverimportsysiflen(sys.argv)<2:print("Usage: python qap.py inputFile [outputFile] [timeLimit]")sys.exit(1)defread_integers(filename):withopen(filename)asf:return[int(elem)foreleminf.read().split()]withlocalsolver.LocalSolver()asls:## Reads instance data #file_it=iter(read_integers(sys.argv[1]))# Number of pointsn=file_it.next()# Distance between locationsA=[[file_it.next()forjinrange(n)]foriinrange(n)]# Flow between factoriesB=[[file_it.next()forjinrange(n)]foriinrange(n)]## Declares the optimization model#model=ls.model# Permutation such that p[i] is the facility on the location ip=model.list(n)# The list must be completemodel.constraint(model.eq(model.count(p),n));# Create B as an array to be accessed by an at operatorarray_B=model.array(model.array(B[i])foriinrange(n))# Minimize the sum of product distance*flowobj=model.sum(A[i][j]*model.at(array_B,p[i],p[j])forjinrange(n)foriinrange(n));model.minimize(obj)model.close()## Parameterizes the solver#iflen(sys.argv)>=4:ls.create_phase().time_limit=int(sys.argv[3])else:ls.create_phase().time_limit=300ls.solve()## Writes the solution in a file with the following format:# - n objValue# - permutation p#iflen(sys.argv)>=3:withopen(sys.argv[2],'w')asoutfile:outfile.write("%d%d\n"%(n,obj.value))foriinrange(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\localsolver.dll.lib

qap instances\esc32a.dat

Compilation / Execution (Linux)

g++ qap.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o qap

./qap instances/esc32a.dat

//********* qap.cpp *********#include <iostream>#include <fstream>#include <vector>#include "localsolver.h"usingnamespacelocalsolver;usingnamespacestd;classQap{public:// Number of points intn;// Distance between locationsvector<vector<int>>A;// Flow between facilitesvector<vector<lsint>>B;// Solver. LocalSolverlocalsolver;// LS Program variables LSExpressionp;// Objective LSExpressionobj;// Reads instance data voidreadInstance(conststring&fileName){ifstreaminfile;infile.exceptions(ifstream::failbit|ifstream::badbit);infile.open(fileName.c_str());infile>>n;A.resize(n);for(inti=0;i<n;i++){A[i].resize(n);for(intj=0;j<n;j++){infile>>A[i][j];}}B.resize(n);for(inti=0;i<n;i++){B[i].resize(n);for(intj=0;j<n;j++){infile>>B[i][j];}}}voidsolve(intlimit){// Declares the optimization model. LSModelmodel=localsolver.getModel();// Permutation such that p[i] is the facility on the location ip=model.listVar(n);// The list must be completemodel.constraint(model.count(p)==n);// Create B as an array to be accessed by an at operatorLSExpressionarrayB=model.array();for(inti=0;i<n;i++){arrayB.addOperand(model.array(B[i].begin(),B[i].end()));}// Minimize the sum of product distance*flowobj=model.sum();for(inti=0;i<n;i++){for(intj=0;j<n;j++){obj+=A[i][j]*model.at(arrayB,p[i],p[j]);}}model.minimize(obj);model.close();// Parameterizes the solver. LSPhasephase=localsolver.createPhase();phase.setTimeLimit(limit);localsolver.solve();}// Writes the solution in a file with the following format:// - n objValue// - permutation pvoidwriteSolution(conststring&fileName){ofstreamoutfile;outfile.exceptions(ofstream::failbit|ofstream::badbit);outfile.open(fileName.c_str());outfile<<n<<" "<<obj.getValue()<<"\n";LSCollectionpCollection=p.getCollectionValue();for(inti=0;i<n;i++){outfile<<pCollection.get(i)<<" ";}outfile<<endl;}};intmain(intargc,char**argv){if(argc<2){cerr<<"Usage: qap inputFile [outputFile] [timeLimit]"<<endl;return1;}constchar*instanceFile=argv[1];constchar*solFile=argc>2?argv[2]:NULL;constchar*strTimeLimit=argc>3?argv[3]:"300";try{Qapmodel;model.readInstance(instanceFile);model.solve(atoi(strTimeLimit));if(solFile!=NULL)model.writeSolution(solFile);return0;}catch(constexception&e){cerr<<"Error occurred:"<<e.what()<<endl;return1;}}
Compilation/Execution (Windows)

copy %LS_HOME%\bin\*net.dll .

csc Qap.cs /reference:localsolvernet.dll

Qap instances\esc32a.dat

/********** Qap.cs **********/usingSystem;usingSystem.IO;usinglocalsolver;publicclassQap:IDisposable{// Number of pointsintn;// Distance between locationsint[][]A;// Flow between faciliteslong[][]B;// Solver.LocalSolverlocalsolver;// LS Program variablesLSExpressionp;// ObjectiveLSExpressionobj;publicQap(){localsolver=newLocalSolver();}privateintreadInt(string[]splittedLine,refintlastPosRead){lastPosRead++;returnint.Parse(splittedLine[lastPosRead]);}// Reads instance datavoidReadInstance(stringfileName){stringtext=File.ReadAllText(fileName);string[]splitted=text.Split((char[])null,StringSplitOptions.RemoveEmptyEntries);intlastPosRead=-1;n=readInt(splitted,reflastPosRead);A=newint[n][];for(inti=0;i<n;i++){A[i]=newint[n];for(intj=0;j<n;j++){A[i][j]=readInt(splitted,reflastPosRead);}}B=newlong[n][];for(inti=0;i<n;i++){B[i]=newlong[n];for(intj=0;j<n;j++){B[i][j]=readInt(splitted,reflastPosRead);}}}publicvoidDispose(){if(localsolver!=null)localsolver.Dispose();}voidSolve(intlimit){// Declares the optimization modelLSModelmodel=localsolver.GetModel();// Permutation such that p[i] is the facility on the location ip=model.List(n);// The list must be completemodel.Constraint(model.Count(p)==n);// Create B as an array to be accessed by an at operatorLSExpressionarrayB=model.Array(B);// Minimize the sum of product distance*flowobj=model.Sum();for(inti=0;i<n;i++){for(intj=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();// Parameterizes the solver.LSPhasephase=localsolver.CreatePhase();phase.SetTimeLimit(limit);localsolver.Solve();}// Writes the solution in a file with the following format:// - n objValue// - permutation pvoidWriteSolution(stringfileName){using(StreamWriteroutput=newStreamWriter(fileName)){output.WriteLine(n+" "+obj.GetValue());LSCollectionpCollection=p.GetCollectionValue();for(inti=0;i<n;i++){output.Write(pCollection.Get(i)+" ");}output.WriteLine();}}publicstaticvoidMain(string[]args){if(args.Length<1){Console.WriteLine("Usage: Qap inputFile [solFile] [timeLimit]");Environment.Exit(1);}stringinstanceFile=args[0];stringoutputFile=args.Length>1?args[1]:null;stringstrTimeLimit=args.Length>2?args[2]:"300";using(Qapmodel=newQap()){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_XXX/bin/localsolver.jar

java -cp /opt/localsolver_XXX/bin/localsolver.jar:. Qap instances/esc32a.dat

/********** Qap.java **********/importjava.util.*;importjava.io.*;importlocalsolver.*;publicclassQap{// Number of pointsprivateintn;// Distance between locationsprivateint[][]A;// Flow between facilitesprivatelong[][]B;// Solver.private

The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.

The problem models the following real-life problem:

There are a set of n facilities and a set of n locations. For each pair of locations, a distance is specified and for each pair of facilities a weight or flow is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations 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.

Formal mathematical definition[edit]

The formal definition of the quadratic assignment problem is as follows:

Given two sets, P ("facilities") and L ("locations"), of equal size, together with a weight functionw : P × PR and a distance function d : L × LR. Find the bijectionf : PL ("assignment") such that the cost function:
is minimized.

Usually weight and distance functions are viewed as square real-valued matrices, so that the cost function is written down as:

In matrix notation:

where are the permutation matrices, "W" is the weight matrix and "D" is the distance matrix.

Computational complexity[edit]

The problem is NP-hard, so there is no known algorithm for solving this problem in polynomial time, and even small instances may require long computation time. It was also proven that the problem does not have an approximation algorithm running in polynomial time for any (constant) factor, unless P = NP.[1] The travelling salesman problem may be seen as a special case of QAP if one assumes that the flows connect all facilities only along a single ring, all flows have the same non-zero (constant) value. Many other problems of standard combinatorial optimization problems may be written in this form.

Applications[edit]

In addition to the original plant location formulation, QAP is a mathematical model for the problem of placement of interconnected electronic components onto a printed circuit board or on a microchip, which is part of the place and route stage of computer aided design in the electronics industry.

See also[edit]

References[edit]

Notes
Sources

External links[edit]

Leave a Comment

(0 Comments)

Your email address will not be published. Required fields are marked *