[Help-glpk] I need help to convert quadratic problem into linear

[Mudassar Majeed]

Dear All,
                 I am trying to solve a problem using ILP and have some problem. If some genius can help me out, I will be very thankful. I am using glpsol to solve it. Following is the code and the explanation.
I have p cores and k cores per node, where number of nodes are ceil(p/k). I have some processes, where card(Processes) > p. Every process i communicates with some other processes (more than one), such that comm[i,j] gives how much
communication i performs with j (Communication that j performs with i is in comm[j,i]). Now as I said there are ceil(p/k) nodes each having k cores, a core will have more than one processes mapped to it. Secondly any two processes
that communicate with each other and that are mapped to some cores in the same node have a weight assigned to each communication b_within_node. Similarly for two processes mapped to two separates cores on different nodes will have
costly communication given as a weight in b_across_nodes. The objective is to assign the processes to cores (in nodes) such that the overall communication cost is minimum. I have defined a variable x{pi in Processes, ni in 1...ceil(p/k), ki in 1..k}, binary.
if x[pi, ni, ki] = 1 then it means process pi is assigned to core ki of node ni. I have used another variable z that shows the communication cost of process pi (that process pi sends to others) and then tried to minimize the maximum cost a process can have. In
this way, it will provide me such solution in x (the mappings of processes to cores) such that communication will be balanced, that means those processes that communicate more will come on the same node etc.

I have written the code, now I have reached to a problem where it becomes quadratic (see the first constraint). If somebody understands my problem then suggest me how can I convert this constraint into linear, as the solver warns me of multiplication of linear variables is
not allowed.

Code is as follows. Please help me in it. Thanks in Advance.

best regards,
Mudassar Majeed.


/*----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/
/* The set of processes that will execute on different cores */

set Processes;

/* Total number of cores */

param p;

/* Number of cores per node */

param k;

/* The communication cost between processes with ranks i and j */

param comm{i in Processes, j in Processes};

/* Weight communicating across the nodes between two processes */

param b_across_nodes;

/* Weight communicating within a node between two processes */

param b_within_node;

/* x is a binary variable that shows where process pi resides on core ki of node ni */
/* If there are p cores and k cores per node then the number of nodes will be ceil(p/k) */

var x{pi in Processes, ni in 1..ceil(p/k), ki in 1..k}, binary;

var z;

s.t. comm_from_each_proc{pi in Processes}: z >= sum{ni in 1..ceil(p/k), ki in 1..k} x[pi,ni,ki] *
                        (sum{qi in Processes, nq in 1..ceil(p/k), kq in 1..k: (pi != qi)}x[qi,nq,kq]*comm[pi,qi] * (if (ni != nq) then b_across_nodes else b_within_node));
minimize timespan: z;

s.t. mapped{pi in Processes}: sum{ni in 1..ceil(p/k), ki in 1..k} x[pi, ni, ki] = 1;

data;

set Processes := 1 2 3 4 5 6 7 8 9 10 11 12;

param p := 6;

param k := 2;

param comm:   1 2 3 4 5 6 7 8 9 10 11 12 :=
        1 0 2 5 6 2 8 5 2 5 6 3 7 
        2 3 0 3 5 6 4 8 2 7 4 6 2
        3 5 4 0 5 7 2 3 2 7 5 9 3
        4 2 3 2 0 6 4 6 3 2 5 4 3
        5 6 4 6 3 0 5 3 2 6 4 5 2
        6 5 3 2 4 2 0 4 3 7 3 4 1
        7 7 4 5 6 2 8 0 4 2 2 3 4
        8 7 6 5 3 4 6 2 0 1 5 2 4
        9 8 7 2 3 1 6 4 6 0 7 5 2
       10 5 4 6 8 1 1 2 3 6 0 3 5
       11 6 2 5 4 8 3 1 1 4 2 0 4
       12 4 3 4 1 1 3 4 1 2 4 5 0;

param b_across_nodes := 10;
param b_within_node := 3;
 
end;

/*----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/