Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
8.9 kB · 266 lines
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267% Copyright (c) 2016, Jacopo Mauro. All rights reserved. % This file is licensed under the terms of the ISC License.% Please note that you will need to set the MiniZinc standard library % environment variable $MZN_STDLIB_PATH to share/minizinc to include % the MiniSearch builtinsinclude "lex_greatereq.mzn";include "lex_less.mzn";int: MAX_INT = 4096;%%%%%%%%%%%%%%%%% Input parameters%%%%%%%%%%%%%%%%% componentsset of int: comps;% portsset of int: ports;% multiple provide portset of int: multi_provide_ports;% locationsset of int: locations;% resourcesset of int: resources;% map of components with their requirements numberarray[ comps, ports] of int: requirement_port_nums;% map of components with their provided multi-ports% -1 means infinite multi-port providerarray[ comps, multi_provide_ports] of int: provide_port_nums;% map of components with their conflictsarray[ comps, ports] of bool: conflicts;% map of multi-ports with their portsarray[ multi_provide_ports, ports] of bool: multi_provides;% map of location with their costsarray[ locations ] of int: costs;% map of locations with the resouces they providearray[ locations, resources ] of int: resource_provisions;% map of components with the resources they consumearray[ comps, resources ] of int: resource_consumptions;%%%%%%%%%%%%%%%%% variables%%%%%%%%%%%%%%%%% bindings numberarray[ multi_provide_ports, ports, comps, comps] of var 0..MAX_INT: bindings;% components numberarray[ comps ] of var 0..MAX_INT: comps_num;% location to number of component maparray[ locations, comps] of var 0..MAX_INT: comp_locations; % total number of componentsvar 0..MAX_INT: sum_comp;%%%%%%%%%%%%%%%%% constraints (no location)%%%%%%%%%%%%%%%%% bind the total number of componentsconstraint sum_comp = sum( i in comps)(comps_num[i]);% bindings 0 if the multiprovide does not provide portconstraint forall(mport in multi_provide_ports, port in ports) ( if multi_provides[mport,port] then true else forall(i in comps, j in comps) ( bindings[mport,port,i,j] = 0) endif);% provides must be greater or equal to bindings & infinite provide port constraintsconstraint forall(mport in multi_provide_ports, pcomp in comps) ( if provide_port_nums[pcomp,mport]=0 then forall(port in ports, rcomp in comps) ( bindings[mport,port,pcomp,rcomp] = 0 ) else if (provide_port_nums[pcomp,mport] = -1) then forall(port in ports, rcomp in comps) ( (comps_num[pcomp] = 0) -> (bindings[mport,port,pcomp,rcomp]=0)) else sum( port in ports, rcomp in comps)( bindings[mport,port,pcomp,rcomp] ) <= comps_num[pcomp] * provide_port_nums[pcomp,mport] endif endif);% requires must be equal to bindings% note: here is possible to require also smaller than or equalconstraint forall(port in ports, rcomp in comps) ( sum( mport in multi_provide_ports, pcomp in comps)( bindings[mport,port,pcomp,rcomp] ) = comps_num[rcomp] * requirement_port_nums[rcomp,port]);% conflict constraints if component provide same portconstraint forall(port in ports, pcomp in comps) ( if (conflicts[pcomp,port] /\ exists(mport in multi_provide_ports) ( (multi_provides[mport,port]) /\ provide_port_nums[pcomp,mport] != 0)) then comps_num[pcomp] <= 1 else true endif);% conflict constraintsconstraint forall(port in ports, pcomp in comps, rcomp in comps) ( if (conflicts[rcomp,port] /\ exists(mport in multi_provide_ports) ( (multi_provides[mport,port]) /\ provide_port_nums[pcomp,mport] != 0)) then comps_num[pcomp] > 0 -> comps_num[rcomp] = 0 else true endif);% unicity constraint% note that we require that a component does not% require more than one port provided by a% multiple provide portconstraint forall(mport in multi_provide_ports, pcomp in comps, rcomp in comps) ( let { int: max_req = sum(port in ports) ( if multi_provides[mport,port] then requirement_port_nums[rcomp,port] else 0 endif ) } in if pcomp = rcomp then ( comps_num[pcomp] >= max_req -> sum(port in ports)(bindings[mport,port,pcomp,rcomp]) <= max_req * (comps_num[rcomp] - 1)) /\ ( comps_num[pcomp] < max_req -> forall (i in 1..max_req)( comps_num[pcomp] = i -> sum(port in ports)(bindings[mport,port,pcomp,rcomp]) <= i * (i-1) )) else ( comps_num[pcomp] >= max_req -> sum(port in ports)(bindings[mport,port,pcomp,rcomp]) <= max_req * comps_num[rcomp] ) /\ ( comps_num[pcomp] < max_req -> forall (i in 0..max_req)( comps_num[pcomp] = i -> sum(port in ports)(bindings[mport,port,pcomp,rcomp]) <= i * comps_num[rcomp] ) ) endif);%%%%%%%%%%%%%%%%% constraints for deciding locations%%%%%%%%%%%%%%%%% map location used or not usedarray[ locations ] of var 0..1: used_locations;constraint forall( l in locations)( sum(c in comps)(comp_locations[l,c]) = 0 <-> used_locations[l] = 0);constraint forall( c in comps) ( sum( l in locations) ( comp_locations[l,c]) = comps_num[c] );constraint forall( res in resources, loc in locations) ( sum( comp in comps)( comp_locations[loc,comp] * resource_consumptions[comp,res] ) <= resource_provisions[loc,res]);% the number of locations can not be greater than the number of components% i.e, one component per location in the worst caseconstraint sum(i in locations) (used_locations[i]) <= sum_comp;%------------------------------------------------------------------------------%% symmetry constraints (wrap in a unique predicate following minizinc specsconstraint symmetry_breaking_constraint( %if location are equal then first location has more comps than the second %in lexicographically order (based on the cost) forall( l1 in locations, l2 in locations)( if l1 < l2 /\ forall ( r in resources)(resource_provisions[l1,r] = resource_provisions[l2,r] ) then if costs[l1] > costs[l2] then lex_greatereq( [comp_locations[l2,c] | c in comps], [comp_locations[l1,c] | c in comps]) /\ (used_locations[l1] = 1 -> used_locations[l2] = 1) else lex_greatereq( [comp_locations[l1,c] | c in comps], [comp_locations[l2,c] | c in comps]) /\ (used_locations[l2] = 1 -> used_locations[l1] = 1) endif else true endif ));%------------------------------------------------------------------------------%% Redundant constraints%constraint redundant_constraint(% % Ralf constraints% forall (rcomp in comps, port in ports)(% if requirement_port_nums[rcomp,port]!=0% then % comps_num[rcomp] > 0 -> sum( mport in multi_provide_ports, pcomp in comps)(% if provide_port_nums[pcomp,mport] != 0 /\ multi_provides[mport,port]% then comps_num[pcomp]% else 0% endif ) >= requirement_port_nums[rcomp,port] % else% true% endif% ));%------------------------------------------------------------------------------%% Constraintsconstraint ( sum(l in locations)(comp_locations[l,1]) > 0 \/ sum(l in locations)(comp_locations[l,2]) > 0 )/\ forall(x in locations)(comp_locations[x,3] < 2)/\ forall(x in locations)(comp_locations[x,4] < 2);int: obj_min = sum(l in locations)(if costs[l] < 0 then costs[l] else 0 endif);int: obj_max = sum(l in locations)(if costs[l] > 0 then costs[l] else 0 endif);var obj_min..obj_max: objective;constraint objective = sum(l in locations)(used_locations[l] * costs[l]);%------------------------------------------------------------------------------%% Solve itemarray [locations] of locations: costs_asc = arg_sort(costs);array [locations] of locations: costs_desc = reverse(costs_asc);solve :: seq_search([ int_search([used_locations[costs_desc[i]] | i in locations], input_order, indomain_min, complete), int_search([comp_locations[l, i] | l in locations, i in comps], first_fail, indomain_max, complete), int_search(comps_num, first_fail, indomain_max, complete), int_search([bindings[m,p,i,j] | m in multi_provide_ports, p in ports, i,j in comps], first_fail, indomain_max, complete) ]) minimize objective;%------------------------------------------------------------------------------%% Output itemoutput [ "bindings = array4d(\(multi_provide_ports), \(ports), \(comps), \(comps), \(bindings));\n", "comps_num = \(comps_num);\n", "comp_locations = array2d(\(locations), \(comps), \(comp_locations));\n", "used_locations = \(used_locations);\n", "objective = \(objective);\n", "% [\(objective), \(sum(x in locations)(sum(y in comps)(comp_locations[x,y])))]\n"];