My Constraint Programming Blog

Mats Carlsson (designer and main implementer of SICStus Prolog) was kind enough to send me alternative versions of some of my SICStus Prolog models, which now are included in the models (marked with his name). His versions are - of course - more elegant and faster than mine. Thanks, Mats.

Assignment problem

Model: assignment.pl using the global constraint global_cardinality.

assignment2(Problem) :-
        cost(Problem, Mode, CostRows),
        format('\nProblem ~d\n~w\n', [Problem,Mode]),
        transpose(CostRows, CostCols),
        length(CostRows, R),
        length(CostCols, C),
        length(Vars, R),
        domain(Vars, 1, C),
        (   for(I,1,C),
            foreach(I-Y,Ys)
        do  Y in 0..1
        ),
        global_cardinality(Vars, Ys, [cost(Cost,CostRows)]),
        (Mode==minimize -> Dir=up ; Dir=down),
        labeling([Dir], [Cost]),
        labeling([], Vars), !,
        format('assignment = ~w, cost = ~d\n', [Vars,Cost]),
        fd_statistics, nl.

Bin Packing

Model: bin_packing.pl. Here is the global constraint cumulative used. Note: The representation of the filled bins is however not the same as in my approach.

bin_packing2(Problem) :-
        problem(Problem, StuffUnordered, BinCapacity),
        portray_clause(problem(Problem, StuffUnordered, BinCapacity)),
        length(StuffUnordered, N),
        N1 is N+1,
        (   foreach(H,StuffUnordered),
            foreach(task(S,1,E,H,1),Tasks),
            foreach(NH-S,Tagged),
            foreach(S,Assignment),
            foreach(_-X,Keysorted),
            foreach(X,Vars),
            param(N1)
        do  S in 1..N1,
            E in 2..N1,
            NH is -H
        ),
        keysort(Tagged, Keysorted),
        maximum(Max, Vars),
        cumulative(Tasks, [limit(BinCapacity)]),
        labeling([minimize(Max),step], Vars),
        portray_clause(assignment(Assignment)),
        fd_statistics,
        nl.

Post Office Problem

Model: post_office_problem2.pl. This is a much better way of solving this problem in Prolog than my translation from MiniZinc.

go2 :-
        Days = 7,
        % requirements number workers per day
        Need = [17, 13, 15, 19, 14, 16, 11],
        % Total cost for the 5 day schedule.
        % Base cost per day is 100.
        % Working saturday is 100 extra
        % Working sunday is 200 extra.
        Cost = [500, 600, 800, 800, 800, 800, 700],
        % Decision variables. X[I]: Number of workers starting at day I
        length(X, Days),
        domain(X, 0, 10),
        append(X, X, [_,_,_|Ys]),
        (   foreach(Nd,Need),
            fromto(Ys, Ys1, Ys2, _)
        do  Ys1 = [Y1|Ys2],
            Ys2 = [Y2,Y3,Y4,Y5|_],
            Y1+Y2+Y3+Y4+Y5 #>= Nd
        ),
        scalar_product(Cost, X, #=, Total),
        labeling([minimize(Total),bisect], X),
        format('assignment = ~w, total cost = ~d\n', [X,Total]),
        fd_statistics.

I also corrected a weird (and wrong) way of calculating the total cost in my version (as well as in the MiniZinc model post_office_problem2.mzn).