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

[glpk xypron]

Hello Mudassar,

using option --cuts you model was solved on my system in 505 seconds:

+1473759: mip =   8.219708642e-01 >=     tree is empty   0.0% (0; 63607)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   505.2 secs
Memory used: 62.5 Mb (65485925 bytes)

Your model contains a lot of symmetries. You can reduce them with
contraints like:

s.t. dummy1{ni in 1..ceil(p/k), nj in 1..ceil(p/k) : ni > nj} :
     sum{pi in Processes, ki in 1..k} pi * x[pi,ni,ki]
  <= sum{pj in Processes, kj in 1..k} pj * x[pj,nj,kj];

s.t. dummy2{ni in 1..ceil(p/k), ki in 1..k, kj in 1..k: ki > kj} :
     sum{pi in Processes} pi * x[pi,ni,ki]
  <= sum{pj in Processes} pj * x[pj,ni,kj];

After adding these constraints and calling glpsol with
option --cuts the solution time was reduced to 310 seconds:

+1042433: mip =   8.219708642e-01 >=     tree is empty   0.0% (0; 43199)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   310.5 secs
Memory used: 45.3 Mb (47511199 bytes)

Best regards

Xypron


-------- Original-Nachricht --------
> Datum: Mon, 24 Oct 2011 11:55:42 -0700 (PDT)
> Betreff: Re: AW: Re: I need help to convert quadratic problem into linear

> Dear All, 
> 
>                 Now the model is working fine for me. But
> it takes alot of time when I increase number of processes very slightly. How
> can I see the room for speeding up the solution ? Should I use other
> solver ? but what is the way to optimize the model ? 
> 
> 
> Here is the updated model and the data that takes alot of time.
> 
> 
>  
> 
> /* 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;
> 
> /* Load on the process with rank i */
> param load{i in Processes};
> 
> param tl := sum{i in
> Processes}load[i];
> param tc := b_across_nodes * sum{i in
> Processes, j in Processes}comm[i,j];
> 
> /* 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 comcost{pi in Processes, pj in
> Processes : pi > pj}, >= b_within_node;
> var z;
> 
> s.t.
> load_on_each_core{ni in 1..ceil(p/k), ki in 1..k}:  
> z >= sum{pi
> in Processes} x[pi, ni, ki] * load[pi];
> 
> s.t.
> comm_cost{pi in Processes, pj in Processes, ni in 1..ceil(p/k),  
> nj in
> 1..ceil(p/k) : (pi > pj) and (ni != nj)}:
> comcost[pi,pj]
> >= (comm[pj,pi]+comm[pi,pj])*
> (b_within_node
> + (b_across_nodes-b_within_node)*
> (sum{ki in
> 1..k} x[pi,ni,ki] + sum{kj in 1..k} x[pj,nj,kj] – 1));
> 
> minimize
> timespan: z/tl + (sum{pi in Processes, pj in Processes: pi >
> pj}comcost[pi,pj])/tc; 
> 
> 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 b_across_nodes := 10;
> param b_within_node := 3;
> param load [1] 47 [2] 1 [3] 49 [4] 21 [5] 34 [6] 6 [7] 31 [8] 29 [9] 23
> [10] 41 [11] 11 [12] 6;
> param comm: 1 2 3 4 5 6 7 8 9 10 11 12 :=
> 1 0    0    0    0    2    6    0    0    0   
> 0    0    0    
> 2 0    0    0    7    0    0    6    0    0   
> 0    0    6    
> 3 0    0    0    0    1    7    0    2    0   
> 4    10    0    
> 4 0    6    1    0    1    0    0    0    0   
> 0    9    10    
> 5 8    4    8    0    0    0    0    8    1   
> 2    0    0    
> 6 5    0    0    5    4    0    3    6    0   
> 8    0    0    
> 7 8    0    4    0    0    0    0    0    7   
> 0    0    1    
> 8 0    0    0    9    8    1    3    0    0   
> 8    0    0    
> 9 10    0    0    5    0    4    9    6    0   
> 0    0    0    
> 10 10    0    3    0    0    0    0    0   
> 0    0    0    8    
> 11 0    9    0    0    0    0    0    0    0   
> 0    0    0    
> 12 0    0    2    0    5    2    5    0    0   
> 0    0    0;
> 
> end; 
>  
> Life is the name of establishing a clear balance between hard work and
> praying to God for success. The one who could find out and order the major
> milestones of life in a proper way and acted upon them is successful. Faith
> in, and obedience to Allah, one's values, contribution for (nation, family &
> human beings), career, earning, extra activities and hobbies.... The best
> ordered list of milestones of life...!!!
> 

-- 
Follow me at http://twitter.com/#!/xypron

NEU: FreePhone - 0ct/min Handyspartarif mit Geld-zurück-Garantie!               
Jetzt informieren: http://www.gmx.net/de/go/freephone