Originally posted by: Mambo12345

Hello everybody,

i have a problem with the formulatoin of a QAP (Quadratic asignment problem).
I have a train station with 5 platforms and I consider 8 trains. I also have a 8x8 matrix with the number of changing persons (see below). From this matrix I take the information how many persons will go from for example train1 to all other trains. I also know the times when the trains arrive and leave and now I have to park the trains optimally that the walking distance of the changing persons is minimal.
I know how it works when I have 5 or less trains and 5 platforms and I already solved this.
But now I have to look when the next train is coming and which platform is available for parking. I will also post my data here:
 

This is the matrix with the number of changing persons.

How can I solve this ? I have no idea how to tell Matlab / Cplex that the platforms are available again. What do you think ?

Best regards !

For every minute in your time horizon and each platform you have to add a variable that tells whether the platform is available at this point time (maybe you don't want single minute but 2, 3, 4, 5 minute steps to keep things smaller).

Then you have to add constraints that model things like "if train 6 is pared at platform P at time T then for time T, T+1, ..., T+15 no other train can park at platform P".

Originally posted by: Mambo12345

Thank you for your answer, I think I know what you mean and I also think that 5 minute steps is a good idea to keep the problem smaller.
But I don't know how to construct the matrix for the constraints.
Since I have a quadratic binary integer problem I have to use cplexmiqp and I set ctype = 'B' for binary optimization.
I have to create matrices and vectors of the form A*x = b and B*x <= c.
If I have a fixed time horizon it is easy to create these matrices,, but I don't know how to create a mtrix in this case.
Actually that are quadratic constraints, right ?!
If d_i is the departure time of train i and a_i is the arrival time of train i than my constraint would be the following:
x_{i,k} x_{j,k} (d_j - a_i) (d_i - a_j)  <= 0

But how can I write this quadratic constraints in the form B*x <= 0 ???

Best regards and thank you for your help !

 

Since you have quadratic constraints you should use cplexmiqcp() instead of cplexmiqp() (note the additional 'c'). That allows quadratic constraints as well.

Note that you may be better off using the CPLEX class API rather than those toolbox functions. The class API is more flexible.

Originally posted by: Mambo12345

Hello Daniel, thank you very much for your answer.
The function cplexmiqcp should solve my problem.
I read the function description and I can formulate the quadratic constraint as x' * Q * x <= 0.
I already know that the constraint should look as follows: x_{i,k} x_{j,k} (d_j - a_i) (d_i - a_j)  <= 0
But now I have a more mathematical problem to understand how the matrix Q should look like that it fulfills my constraint.

Of cours the values (d_j - a_i) (d_i - a_j) will be in the matrix but I dont know on which position they have to be.
I also think that x' * Q * x <= 0 is just a number and not a vector, right ?!
 

I have never tried the class API but thank you very much for the advice !
But anyway, I can not find how the matrix Q should look like.

Best regards and I hope that you can help me again with the matrix Q.

Your advices are pure gold for me !

The matrix Q must be setup so that (symbollicaly) evaluating x'Qx gives the desired expression.

You say your constraint should be: x_{i,k} x_{j,k} (d_j - a_i) (d_i - a_j)  <= 0

I don't understand this since your variable x seems to have two indices, i.e., it looks two-dimensional. For cplexmiqcp() the x vector is however assumed to be 1-dimensional. You first have to flatten your twodimensional vector. After doing that it might be clearer how the matrix should look like?