Non sovrapposizione fra rettangoli

Ho scritto questo codice come soluzione dell'esame del 27/07/2009. E` corretto?

rettangolo(N,X,Y,D,R,S):-
		% uso di cumulative
		length(S,N),
		length(D1,N),
		length(R1,N),
		S :: 0..N,
		D1 :: 1..N,
		R1 :: 1..N,
		X :: 0..100,
		Y :: 0..100,

		%genera la lista D=[1,2,...N] (un po' come le durate nello scheduling)
		genList(N,D1),
		sorted(D1,D),

		%genera la lista R=[1,2,...N] (un po' come le risorse nello scheduling)
		genList(N,R1),
		sorted(R1,R),

		%applico il cumulative per imporre che i quadrati siano < Y
		cumulative(S,D,R,Y),

		% per evitare la sovrappozione dei quadrati
		fd_global:alldifferent(S),
		%ottengo il max sull'asse delle X
		sommaList(S,D,L),
		maxlist(L,M),
		% impongo che questo max sia <=X per fare stare tutti i quadrati entro X
		M#<=X,

		%calcolo l'area  che poi minimizzero`
		Cost #=X*Y,
		flatten([X,Y,S],All),
		min_max(labeling(All),Cost).


sommaList([],[],_).
sommaList([X1|R1],[X2|R2],[X3|R3]):- X3 #= X1+X2,
				sommaList(R1,R2,R3).

genList(0,_).
genList(N,[N|Rest]):-N1 is N-1,
		    genList(N1,Rest).

Risposta: nella sua soluzione lei impone questo vincolo:

    % per evitare la sovrapozione dei quadrati
    fd_global:alldifferent(S),

che però non è richiesto e non garantisce la non sovrapposizione dei quadrati: impone soltanto che due quadrati non possano avere la stessa ascissa.

Questo taglia alcune soluzioni; ad esempio il suo programma con N=5 trova una soluzione con costo 70, mentre il programma che c'è nella soluzione in rete trova un valore migliore: 60.

Per evitare la sovrapposizione fra rettangoli non è sufficiente imporre il vincolo cumulativo: il vincolo cumulativo si preoccupa solo di far sì che in ogni istante di tempo il consumo totale di risorse dei vari task non superi il limite.

Ad esempio, supponga di voler collocare dei rettangoli di dimensione:

1x2, 3x1, 2x1, 3x1, 1x2

dentro una scatola di dimensione 4x3. Il vincolo

cumulative([1,1,2,2,4],[1,3,2,3,1],[2,1,1,1,2],3)

ha successo, perché considera la soluzione in figura:

Come vede, il task di colore rosa non può però essere rappresentato come rettangolo. È quindi necessario che venga imposto un vincolo simile al no_overlap che è nella soluzione proposta. La stessa soluzione è anche a pag 204 dei lucidi.