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

[Mudassar Majeed]

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 <address@hidden>
To: Mudassar Majeed <address@hidden>
Cc: address@hidden
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