how to implement parallel integer optimization with petsc?
hello group because i'm not sure what kind (MILP or IP) of optimization it is I attached short example at the end of this email my real problem is to find integer solution for matrix which is about 100X3500 large. I think it is good idea to do this task in parallel mode. I found yesterday PETSC pakage. It is incredible (for me), but compilation and testing proces has passed smooooth on my cluster (as much as 2x1PC :-)). Because of such painless implementation it would be great if icould use PETSC for solving my problem. my question is: is it posible with PETSC? if yes could you count(and shortly describe) consecutive steps? maybe someone already have done it? thank you for any replyes and sugesstions. tom ps. short example suposse we have two kinds of elements type A nad B which has such features like price. A1 200$ A2 300$ A3 400$ B1 500$ B2 600$ B3 700$ B4 900$ we want to find set of pairs AxB which acomplish constrain for mean price. (when we make pair we sum prices of their elements) additionaly constrain is that we may use elements A only once and elements B only twice. so, our solution is binary matrix (1=make pair)like bellow B1 B2 B3 B4 B5 A1 1 0 0 0 0 A2 1 0 0 0 0 A3 0 1 0 0 0 ######################################################## # [email protected] # # jay.au.poznan.pl/~tomjan/ # ########################################################
Tomasz Jankowski <[email protected]> writes: PETSc basically offers parallel linear algebra and nonlinear solvers. If you can phrase the algorithm in linear algebraic terms, then we can probably help. In addition, it appears that you have a logically Cartesian space, so the DA object could handle allocation, etc. Matt
hello group
because i'm not sure what kind (MILP or IP) of optimization it is I attached short example at the end of this email
my real problem is to find integer solution for matrix which is about 100X3500 large. I think it is good idea to do this task in parallel mode. I found yesterday PETSC pakage. It is incredible (for me), but compilation and testing proces has passed smooooth on my cluster (as much as 2x1PC :-)). Because of such painless implementation it would be great if icould use PETSC for solving my problem.
my question is:
is it posible with PETSC? if yes could you count(and shortly describe) consecutive steps? maybe someone already have done it?
thank you for any replyes and sugesstions.
tom
ps. short example suposse we have two kinds of elements type A nad B which has such features like price. A1 200$ A2 300$ A3 400$ B1 500$ B2 600$ B3 700$ B4 900$
we want to find set of pairs AxB which acomplish constrain for mean price. (when we make pair we sum prices of their elements) additionaly constrain is that we may use elements A only once and elements B only twice. so, our solution is binary matrix (1=make pair)like bellow B1 B2 B3 B4 B5 A1 1 0 0 0 0 A2 1 0 0 0 0 A3 0 1 0 0 0
######################################################## # [email protected] # # jay.au.poznan.pl/~tomjan/ # ########################################################
-- "Failure has a thousand explanations. Success doesn't need one" -- Sir Alec Guiness
PETSc basically offers parallel linear algebra and nonlinear solvers. If you can phrase the algorithm in linear algebraic terms, then we can probably help.
unfortunetly I can't (sorry I'm not mathematicst) but I can phrase my problem in AMPL language. please look at the two files which I have pasted at the end of this email. mate-selection.mod contain optimization model in AMPL. the second file mate-selection.dat contain the example data. Please forgive me my previous email with unclear description of my problem (its because of my english).once again I need to assert that I don't expect the full recipe for implementation of my problem with PETSc. I will realy appreciate if you give some sugesstion. Thank you for your reply tom (ps. if AMPL model is not good I provide my algorithm in algebraic terms) ---------mate-selection.mod---------------- set BULLS; set COWS; param ebv {COWS,BULLS} >= 0; param cost {BULLS} > 0; param f {COWS,BULLS} >= 0; param l_cows > 0; var Pairs {COWS,BULLS} binary; maximize Total_Ebv: sum {i in COWS, j in BULLS} ebv[i,j] * Pairs[i,j]; subject to Max_cows {i in COWS}: sum{j in BULLS} Pairs[i,j] = 1; subject to Max_bulls {j in BULLS}: sum{i in COWS} Pairs[i,j] <= 2; subject to F: (sum{i in COWS, j in BULLS} f[i,j] * Pairs[i,j])/l_cows <= 0.03; subject to Cost: sum{ i in COWS, j in BULLS} Pairs[i,j] * cost[j] <=500; --------------------------------------------- -----------------mate-selection.dat--------------------- data; set BULLS := male0 male1 male2 male3 male4; set COWS := female0 female1 female2; param ebv: male0 male1 male2 male3 male4:= female0 290 410 298 400 471 female1 901 807 956 653 173 female2 185 453 733 316 367 ; param f: male0 male1 male2 male3 male4:= female0 0.076 0.048 0.068 0.064 0.064 female1 0.078 0.057 0.035 0.018 0.014 female2 0.068 0.042 0.062 0.076 0.059 ; param cost:= male0 72 male1 544 male2 822 male3 825 male4 127 ; param l_cows := 3; end; --------------------------------------------
Tomasz Jankowski <[email protected]> writes: Unfortunately, AMPL does a lot of processing. It would be a big job to translate this to PETSc. Matt
PETSc basically offers parallel linear algebra and nonlinear solvers. If you can phrase the algorithm in linear algebraic terms, then we can probably help.
unfortunetly I can't (sorry I'm not mathematicst) but I can phrase my problem in AMPL language. please look at the two files which I have pasted at the end of this email. mate-selection.mod contain optimization model in AMPL. the second file mate-selection.dat contain the example data.
Please forgive me my previous email with unclear description of my problem (its because of my english).once again I need to assert that I don't expect the full recipe for implementation of my problem with PETSc.
I will realy appreciate if you give some sugesstion.
Thank you for your reply
tom
(ps. if AMPL model is not good I provide my algorithm in algebraic terms)
---------mate-selection.mod---------------- set BULLS; set COWS;
param ebv {COWS,BULLS} >= 0; param cost {BULLS} > 0; param f {COWS,BULLS} >= 0; param l_cows > 0; var Pairs {COWS,BULLS} binary;
maximize Total_Ebv: sum {i in COWS, j in BULLS} ebv[i,j] * Pairs[i,j];
subject to Max_cows {i in COWS}: sum{j in BULLS} Pairs[i,j] = 1; subject to Max_bulls {j in BULLS}: sum{i in COWS} Pairs[i,j] <= 2; subject to F: (sum{i in COWS, j in BULLS} f[i,j] * Pairs[i,j])/l_cows <= 0.03; subject to Cost: sum{ i in COWS, j in BULLS} Pairs[i,j] * cost[j] <=500; ---------------------------------------------
-----------------mate-selection.dat---------------------
data;
set BULLS := male0 male1 male2 male3 male4; set COWS := female0 female1 female2; param ebv: male0 male1 male2 male3 male4:= female0 290 410 298 400 471 female1 901 807 956 653 173 female2 185 453 733 316 367 ; param f: male0 male1 male2 male3 male4:= female0 0.076 0.048 0.068 0.064 0.064 female1 0.078 0.057 0.035 0.018 0.014 female2 0.068 0.042 0.062 0.076 0.059 ; param cost:= male0 72 male1 544 male2 822 male3 825 male4 127 ; param l_cows := 3; end;
--------------------------------------------
-- "Failure has a thousand explanations. Success doesn't need one" -- Sir Alec Guiness
participants (2)
-
Matthew Knepley -
Tomasz Jankowski