[eclipse-clp-users] Bin Packing implementation issues

Its a huge mail and a compliccated query so I request the reader to please
read on with patience.

So I am writing a routine for a multidimensional bin packing scenario where
sizes of the objects to be placed varies across different time intervals and
hence the demand (sizes of objects) is an array over different time
intervals. The bin packing constraint has been relaxed in the sense that
total demands of objects placed in the bin should satisfy the bins capacity
in at least a certain percent of the total time intervals. The code to these
purposes has been outlined below.

allocatebins(NumServers,NumVMs,NumDims,NumIntervals,Percentile):-
        init_backtracks,
        dim(Map2D,[NumServers,NumVMs]),
        Map2D :: [0,1],
        open("TimeSeriesDemandMatrix",read,S),read(S,Demand),close(S),
        open("DemandAggregates",read,S1),read(S1,DemandAggregate),close(S1),
        open("Caps",read,S2),read(S2,Caps),close(S2),
        constrainColumn(Map2D,NumServers,NumVMs),  %%% There is just a
single 1 per column

constrainDemandOfRows(Demand,Caps,NumServers,NumVMs,Map2D,NumDims,NumIntervals,Percentile),
        searchColumnWise(Map2D,NumServers,NumVMs),
        write_backtracks.


constrainDemandOfRows(Demand,Caps,NumServers,NumVMs,Map2D,NumDims,NumIntervals,Percentile):-

(count(E,1,NumServers),param(NumVMs,Map2D,Demand,Caps,NumDims,NumIntervals,Percentile)
do
            Row is Map2D[E,1..NumVMs],J is Caps[E,1..NumDims],
           (count(TInterval,1,NumIntervals),
            fromto(0,Iter,Iter+ValTim,RelaxedConstraint),
            param(Demand,NumDims,J,NumVMs,Row,Percentile) do
               (count(Dim,1,NumDims),
                fromto(1,ValD,ValD*(Val$=<K),ValTim),
                param(Demand,J,NumVMs,Row,TInterval,Row)
                do
                    S is Demand[1..NumVMs,TInterval,Dim],
                    element(Dim,J,K),
                    (fromto(Row,[H|T],T,[]),
                     fromto(S,[HS|TS],TS,[]),
                     fromto(0,I,I+H*HS,Val) do
                        true
                    )
                )
        ),
           eval(RelaxedConstraint)$>=Percentile*NumIntervals
     ).

As of now this implementation takes a lot of time to run. Are there any
suggestions as to how to optimise it ?

Also there is a strange error that I face which is the following.

After putting in the constraints I start initialising the variables in a
column wise fashion ... that is move column wise and keep initialising the
variables to first 0 and then 1. The code for doing this is given below -

searchColumnWise(Map2D,NumServers,NumVMs):-
    (count(K,1,NumVMs),
         param(Map2D,NumServers,NumVMs) do
            L is Map2D[1 .. NumServers,K],
            (foreach(G,L),count(T,1,NumServers),param(K) do
                count_backtracks(T,K),indomain(G))).

The count_backtracks is used to note backtracks as and when they happen. The
code for this is written below -

:-local variable(backtracks),variable(waiting_for_failure).

init_backtracks:-
        setval(backtracks,0).

count_backtracks(T,K):-
        setval(waiting_for_failure,true).

count_backtracks(T,K):-
        getval(waiting_for_failure,true),
        setval(waiting_for_failure,false),
        incval(backtracks),
        fail.

Now, observing when the backtrack happens i see the following - that lets
say i give as input 50 objects to be placed on 50 vms over 90 time intervals


now it goes fine till the first 40 objects and since these essentially
placed in a first fit format, 7 objects are observed to be used til now

however while placing the 41st object, it shows the first backtrack, which
is strange as it says it is not able top place object 41
on bin 7 but the constraints dissatisfy and a backtrack happens. Now such a
backtrack is not expected because if it cannot be placed on this bin
then by domain reduction placing should anyways not happen. Even if it was
to happen i would have observed the first backtrack before the 41st object
when the 2nd bin was going to be used.

Now I believe that it is either a malfunctioning of the domain reduction
because i have really huge equations with reified constraints or there is
something missing in my understanding. Could you help me out with this. I
hope i could convey the problem ..

thanks a lot in advance !!!