%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Creates constraints for CPLEX %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Prolog code for the PF on N^2 %%% with the HP abstraction %%% 1. Energy computed on %%% odd distances only. %%% h -- p %%% | %%% h -- p %%% 2. A maximum (linear) distance %%% of sqrt(N) is set from the starting point %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% :-use_module(library(system),[]). :-use_module(library(clpfd)). :-use_module(library(lists)). :-use_module(library(charsio)). naive:- go(4,25). go(N,M):- N>M. go(N,M):- N=0, N1 is N-1, gen_list(R,N1). constrain(Primary,Length) :- length(Primary,N), M is 2*N, Min is N - integer(sqrt(N)), Max is N + integer(sqrt(N)), length(Tertiary,M), set_domain(Tertiary,Min,Max), starting_point(Tertiary,N), avoid_self_loops(Tertiary), next_constraints(Tertiary), energy_constraint(Primary,Tertiary,E), system:working_directory(DIR,DIR), name(DIR,ListDir), name('/naive',FN), append(ListDir,FN,Temp1), name(Length,FN1), append(Temp1,FN1,Temp2), name('.txt',FN2), append(Temp2,FN2,Temp), name(FilePath,Temp), open(FilePath,write,File), write(File,'Maximize\n'), write(File,' '), write(File,E), write(File,'\n'), write_constr(File), write_bound(File), write_vars(File), write_bin_vars(File), write(File,'End\n'), close(File). set_domain(Tertiary,Min,Max):- % domain(Tertiary,Min,Max), rec_dom(Tertiary,Min,Max). rec_dom([],_,_). rec_dom([New|R],Min,Max):- new_var(New), assert_var(New), add_bound([' ',Min,' <= ',New,' <= ',Max]), rec_dom(R,Min,Max). starting_point([A,B,C,D|_],N) :- N1 is N + 1, add([' ',A,' = ',N]), add([' ',B,' = ',N]), add([' ',C,' = ',N]), add([' ',D,' = ',N1]). avoid_self_loops([]). avoid_self_loops([Tx,Ty|R]):- pairs_avoid(Tx,Ty,R), avoid_self_loops(R). % positions_to_integers(Tertiary, ListaInteri), % all_different(ListaInteri). pairs_avoid(_,_,[]). pairs_avoid(Tx,Ty,[T1x,T1y|R]):- new_var(Bool), add_bin(Bool), add([' 100 ',Tx, ' + ',Ty, ' - 100 ',T1x,' - ',T1y,' - 10000 ',Bool,' <= -1']), add([' 100 ',T1x,' + ',T1y,' - 100 ',Tx, ' - ',Ty, ' + 10000 ',Bool,' <= 9999']), pairs_avoid(Tx,Ty,R). next_constraints([_,_]). next_constraints([X1,Y1,X2,Y2|C]) :- next(X1,Y1,X2,Y2), next_constraints([X2,Y2|C]). next(X1,Y1,X2,Y2):- %domain([Dx,Dy],-1,1), ---->>>>> shifted (No negative vals!!!!) new_var(Dx), new_var(Dy), % Bool in 0..1, new_var(Bool), add_bin(Bool), add_bound([' ',0,' <= ',Dx,' <= ',2]), add_bound([' ',0,' <= ',Dy,' <= ',2]), % Dx -1 #= X1-X2, % Dy -1 #= Y1-Y2, add([' ',Dx,' - ',X1,' + ',X2,' = 1 ']), add([' ',Dy,' - ',Y1,' + ',Y2,' = 1 ']), % Dx -1 + Dy -1 #=< 1, add([' ',Dx,' + ',Dy,' <= 3']), % -1* (Dx-1) - (Dy-1) #=< 1, add([' -1 ',Dx,' - ',Dy,' <= -1']), % Dx-1 + Dy-1 #=< -1 + 100 * Bool, %%% 100 = Big M add([' ',Dx,' + ',Dy,' -100 ',Bool,' <= 1']), % -1* (Dx-1) - (Dy-1) #=< -1 + 100 * (1-Bool), add([' -1 ',Dx,' - ',Dy,' + 100 ',Bool,' <= 97']). energy_constraint([_],_,V):- new_var(V), assert_var(V), add([' ',V,' = 0']). energy_constraint([A,B|Primary],[XA,YA,XB,YB|Tertiary],E) :- energy_contribution_of_A(0,A,XA,YA,Primary,Tertiary,E1), energy_constraint([B|Primary],[XB,YB|Tertiary],E2), % E #= E1 + E2. new_var(E), add([' ',E,' - ',E1,' - ',E2,' = 0']). energy_contribution_of_A(_,_,_,_,[],[],V):- new_var(V), assert_var(V), add([' ',V,' = 0']). energy_contribution_of_A(0,A,XA,YA,[_|Primary],[_,_|Tertiary],E):- energy_contribution_of_A(1,A,XA,YA,Primary,Tertiary,E). energy_contribution_of_A(1,A,XA,YA,[B|Primary],[XB,YB|Tertiary],E):- energy(A,XA,YA,B,XB,YB,C), energy_contribution_of_A(0,A,XA,YA,Primary,Tertiary,E1), % E #= E1 + C. new_var(E), add([' ',E,' - ',E1,' - ',C,' = 0']). energy(h,XA,YA,h,XB,YB,C) :- % C in 0..1, new_var(C), add_bin(C), new_var(DX), new_var(DY), % DX #= XA - XB+100, ////// shift per non avere negativi!!!!!! % DY #= YA - YB+100, add([' ',DX,' - ',XA,' + ',XB,' = 100 ']), add([' ',DY,' - ',YA,' + ',YB,' = 100 ']), assoluto(DX,ADX), assoluto(DY,ADY), % Bool in 0..1, new_var(Bool), add_bin(Bool), % ADX -100 + ADY -100 + C #>= 2, add([' ',ADX,' + ',ADY,' + ',C,' >= 202']), % ADX -100 + ADY -100 #=< 1 + 1000* Bool, add([' ',ADX,' + ',ADY,' - 1000 ',Bool,' <= 201']), % C #=< 1000 * ( 1 - Bool). add([' ',C,' +1000 ',Bool,' <= 1000']). energy(h,_,_,p,_,_,V):- new_var(V), assert_var(V), add([' ',V,' = 0']). energy(p,_,_,h,_,_,V):- new_var(V), assert_var(V), add([' ',V,' = 0']). energy(p,_,_,p,_,_,V):- new_var(V), assert_var(V), add([' ',V,' = 0']). assoluto(X,AbsX) :- %///// assumo X e Absx shiftato di 100! new_var(AbsX), %Bool in 0..1, new_var(Bool), add_bin(Bool), % -1*(AbsX-100) #=< (X-100), add([' -1 ',AbsX,' - ',X,' <= -200']), % X #=< AbsX, add([' ',X,' - ',AbsX,' <= 0']), % AbsX #=< X + Bool * 100, add([' ',AbsX,' - ',X,' - 100 ',Bool,' <= 0']), % AbsX -100 #=< -1 * (X-100) + 100 * (1-Bool). add([' ',AbsX,' + ',X,' + 100 ',Bool,' <= 300 ']). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% my_print(Energy,Tertiary) :- write('Energy: '),write(Energy),nl, myprint(0,Tertiary). myprint(4,[X,Y|Tertiary]) :- !, write('('),write(X),write(' , '),write(Y),write(')'),nl, myprint(0,Tertiary). myprint(N,[X,Y|Tertiary]) :- !, M is N + 1, write('('),write(X),write(' , '),write(Y),write(') ; '), myprint(M,Tertiary). myprint(_,_). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% Time predicates %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% initialization :- clean, %%% remove garbage if any statistics(runtime,[T|_]), assert(start(T)), retractall(totalvars(_)), retractall(constr(_)), retractall(vars(_)), retractall(bound(_)), retractall(bin_vars(_)), assert(totalvars(0)), assert(constr([])), assert(bin_vars([])), assert(vars([])), assert(bound([])). writetime(MEDIA,Str) :- start(InitialTime), statistics(runtime,[CurrentTime|_]), Delta is CurrentTime - InitialTime, stampa(MEDIA,Str), print_time(MEDIA,Delta), stampa(MEDIA,'\t'). print_time(MEDIA, K) :- K < 60000,!, S is K//1000, M is K mod 1000, stampa(MEDIA,S), stampa(MEDIA,','), stampa(MEDIA,M), stampa(MEDIA,'s'). print_time(MEDIA, K ) :- K < 3600000,!, M is K //60000, S is K mod 60000, stampa(MEDIA,M), stampa(MEDIA,'min.'), print_time(MEDIA,S). print_time(MEDIA, K ) :- H is K //3600000, M is K mod 3600000, stampa(MEDIA,H), stampa(MEDIA,'hours.'), print_time(MEDIA,M). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% stampa(video,String) :- !, write(String). stampa(Stream,String) :- write(Stream,String). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% CLEANING PREDICATES %%% For removing side effects %%% caused by execution abort %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% clean :- retractall(start(_)). rec_int([]). rec_int([T|R]):- write(' '),write_var(T),nl, rec_int(R). add(L):- add_rec(L,[]). add_rec([],C):- assert_constr(C). add_rec([E|R],A):- add3(A,E,B), add_rec(R,B). add_bound(L):- add_bound_rec(L,[]). add_bound_rec([],C):- assert_bound(C). add_bound_rec([E|R],A):- add3(A,E,B), add_bound_rec(R,B). add3(A,Str,C):- write_to_chars(Str,B), append(A,B,C). %%% aggiunge variabile in bin e impone vincolo 0< T<1 add_bin(T):- assert_bin_var(T). assert_constr(C):- constr(A), retractall(constr(A)), append(A,[C],R), assert(constr(R)). assert_bound(C):- bound(A), retractall(bound(A)), append(A,[C],R), assert(bound(R)). assert_var(C):- vars(A), retractall(vars(A)), write_to_chars(C,Cs), append(A,[Cs],R), assert(vars(R)). assert_bin_var(C):- bin_vars(A), retractall(bin_vars(A)), write_to_chars(C,Cs), append(A,[Cs],R), assert(bin_vars(R)). write_bound(S):- write(S,'Bounds\n'), bound(A), write_rec(S,A). write_constr(S):- write(S,'Subject To\n'), constr(A), write_rec(S,A). write_vars(S):- write(S,'General\n'), vars(A), write_rec(S,A). write_bin_vars(S):- write(S,'Binary\n'), bin_vars(A), write_rec(S,A). write_rec(_,[]). write_rec(S,[A|R]):- atom_codes(X,A), write(S,X),write(S,'\n'), write_rec(S,R). new_var(New):- totalvars(N), retractall(totalvars(N)), N1 is N+1, assert(totalvars(N1)), number_codes(N,Code), atom_codes(New,[120|Code]).