% Rectangle Packing model (based on [Simonis & O'Sullivan, CPAIOR'08]) % % Find the smallest rectangle (bin) containing % N squares (items) of sizes 1*1, 2*2, ..., N*N. % import('rules2cp/lib/pkml/pkml'). % Data structures & handy macro defs % make_object_shape_area(S, OL, A) = {shapes=[S], shape_index=1, origin=OL, area=A}. bin = make_object_shape_area(make_shape_box([_, _]), [1, 1], _). items(N) = map(S, squares(N), item(S)). item(S) = {shapes = [S], shape_index = 1, origin = [_,_]}. items_area(Items) = sum(map(I, Items, volume(I))). square(S) = make_shape_box([S, S]). squares(N) = map(Size, reverse_list([2 .. N]), square(Size)). w(O) = size(O, 1). h(O) = size(O, 2). l(O) = size(O, 3). xs(Items) = map(I, Items, x(I)). ys(Items) = map(I, Items, y(I)). reverse_list(L) = foldl(X, L, flip(cons), [], X). % Search strategy definition % % interval splitting % interval_predicate(E, List) = let(X, nth(1, List), let(L, nth(2, List), let(XDLBL, domain_min(X) + L, X =< XDLBL or (X > XDLBL and E)))). interval_split(X, Min, Max, L) = foldl(Cut, [1..((Max - Min) / (L + 1)) + 1], interval_predicate, true, [X, L]). % dychotomic splitting % dichotomy_predicate(List, X) = let(XDM, (domain_min(X) + domain_max(X)) / 2, X =< XDM or X > XDM). dichotomic_split(X) = let(L, domain_max(X) - domain_min(X) + 1, foldl(Cut, [1..log(2, L)], dichotomy_predicate, true, X)). state_items_domain(Items, W, H) = forall(It, Items, let(X, x(It), let(Y, y(It), let(S, w(It), domain(X, 1, W - S + 1) and domain(Y, 1, H - S + 1) )))) and lower_quadrant(Items, W, H). lower_quadrant(Items, W, H) = let(FstIt, nth(1, Items), let(X, x(FstIt), let(Y, y(FstIt), let(S, w(FstIt), domain(X, 1, (W - S + 2) / 2) and domain(Y, 1, (H + 1) / 2) )))). state_items_constraints(Items, W, H) = let(Xs, map(It, Items, x(It)), let(Ys, map(It, Items, y(It)), let(Ss, map(It, Items, w(It)), disjoint2(Xs, Ys, Ss) and cumulative(Xs, Ss, Ss, H) and cumulative(Ys, Ss, Ss, W) ))). state_items_search(Items, W, H) = let(XSs, map(It, Items, {coord = x(It), siz = w(It)}), let(YSs, map(It, Items, {coord = y(It), siz = h(It)}), let(Min, 1, let(MaxX, W + 1, let(MaxY, H + 1, dynamic( search( forall(XS, XSs, siz(XS) > 6 implies interval_split(coord(XS), Min, MaxX, max(1, (siz(XS)*3)/10))) and forall(XS, XSs, dichotomic_split(coord(XS))) and forall(YS, YSs, interval_split(coord(YS), Min, MaxY, max(1, (siz(YS)*3)/10))) and forall(YS, YSs, dichotomic_split(coord(YS))) ))))))). % Items subproblem definition % solve_items_subproblem(Items, W, H) = state_items_domain(Items, W, H) and state_items_constraints(Items, W, H) and state_items_search(Items, W, H). state_bin_domain(W, H, A, L, U, N) = domain([W, H], N, L) and domain([A], L, U). state_bin_constraints(W, H, A, N) = let(K, (W + 1)/2, A = W * H and W =< H and (W >= 2 * N - 1 or H >= (N * N + N - (K - 1) * (K - 1) - (K - 1)) / 2)). state_bin_search = variable_ordering([is(area(^)), is(w(^)), is(h(^))]) and labeling(bin). % Bin subproblem definition % solve_bin_subproblem(W, H, A, L, U, N) = state_bin_domain(W, H, A, L, U, N) and state_bin_constraints(W, H, A, N) and state_bin_search. % Query % % N : problem instance size (N = card(Items)) % Items : item records {box(K, K) | forall K in 1..N} % Width : bin width (length in the first dimension (x)) % Height : bin height (length in the second dimension (y)) % Area : bin area % LB : optimal solution lower bound % UB : optimal solution upper bound ? let(N, 22, let(Items, items(N), let(Width, size(bin, 1), let(Height, size(bin, 2), let(Area, area(bin), let(LB, items_area(Items) + 1, let(UB, LB + 200, solve_bin_subproblem(Width, Height, Area, LB, UB, N) and solve_items_subproblem(Items, Width, Height) ))))))).