Thank you so much brother for your detailed comments. I will try all what you
have proposed. The thing is, I am doing research in parallel computing. I took
this course "Practical Integer Programming" and I tried to take my research
problem as a project of this course. So tried to model it in ILP to solve it.
My basic intention was to solve this problem from C (by calling APIs of GLPK)
when my actual parallel program with thousands of processes and cores runs on
the supercomputing center. But I was not aware that the solving ILP takes alot
of time. Imagine 12 processes is taking alot of time (even 80 seconds are alot,
as far as the total time of a parallel program is concerned), then how much
time thousands of processes and cores will take. I had a publication before
where I solves the load balancing problem (alone) by adding another function in
MPI. That new function MPI_Load_create basically balances the load before the
actual computation is performed.
That function was taking time in miliseconds and performing good load
balancing. Now I wanted to extend that function for balancing both loads and
communications. I found that the ILP formulation (even takes alot of time)
gives very good solution, but it is not possible to use it during runtime in
actual application. IF I am able to use some solver that can be integrated with
MPI to solve the problem in parallel way so if I thousands of processes then
the solution takes less time, in that case I may rethink to use ILP. Anyways, I
learned alot in the course and from you people. If you have any clue for using
this solution in my situation then you are welcome to give me suggestions.
best regards,
Mudassar Majeed
________________________________
From: glpk xypron <[email protected]>
To: Mudassar Majeed <[email protected]>
Cc: [email protected]
Sent: Wednesday, October 26, 2011 6:44 AM
Subject: Re: AW: Re: I need help to convert quadratic problem into linear
Hello Mudassar,
the solution to your problem formulation leads to a CPU load
z = 76. The minimum load possible (zmin) is 52.
Your problem could be solved much faster, if you separated it into two.
First calculate the minimum possible load in a problem formulation
which does not care about the communication cost.
Second calculate the minimum possible communication cost for the
maximum CPU load (zmax) that you allow.
Solving the complete problem (with the two symmetry breaking constraints
which I proposed yesterday, and option --cuts) takes my computer
310 seconds.
Determining the minimum possible load takes 27 seconds.
Determining the minimum communication cost for zmax = 76 takes
81 seconds.
If you put a tighter constraint on the load, the solution is calculated
faster, e.g for zmax = zmin = 52: 5 seconds.
Did you think about replacing communication cost by communication time?
TotalTime >= CPU time
TotalTime >= Communication / Bandwidth
Minimize TotalTime.
In this case, you might first calculate the minimum CPU time for
unlimited bandwidth. Minimize communication for minimum CPU time,
and check if bandwidth is a problem.
If yes, minizme processing time for minimum bandwidth and check if
CPU time is limiting.
If yes, minimize total time.
Best regards
Xypron
--
Follow me at http://twitter.com/#!/xypron
Empfehlen Sie GMX DSL Ihren Freunden und Bekannten und wir
belohnen Sie mit bis zu 50,- Euro! https://freundschaftswerbung.gmx.de
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
