TP4 : Problème de recouvrement

Soit un « grand » carré de taille T et n « petits » carrés de tailles T₁, T₂, ..., T_n. Placer les n petits carrés à l'intérieur du grand, sans qu'ils se chevauchent et afin que le grand carré soit complètement couvert.

Indications :

Contraintes nécessaires et suffisantes : non recouvrement des petits carrés deux à deux placés à l'intérieur du grand.
Contraintes redondantes (utiles pour améliorer l'efficacité) : pour toute horizontale (resp. verticale) coupant les petits carrés i₁, ..., i_p, on a å_j=1^p T_i_{_j} = T.
L'utilisation de BestGenerate (remise en cause de la variable choisie à chaque choix de valeur) avec une stratégie de choix de variable bien choisie améliore considérablement la recherche.
gnuplot permet d'afficher à peu de frais le résultat : écrire dans un fichier des séries, séparées par des lignes blanches, de 4 lignes contenant les coordonnées des coins des carrés à dessiner. La commande gnuplot
```
gnuplot> plot "nom du fichier" with lines
```
lit le fichier, affiche et relie les points.

Données pour 4 problèmes (~serveur/ILOG/recouvrement.txt) :

T	T₁, T₂, ...
3	2,1,1,1,1,1
19	10,9,7,6,4,4,3,3,3,3,3,2,2,2,1,1,1,1,1,1
112	50,42,37,35,33,29,27,25,24,19,18,17,16,15,11,9,8,7,6,4,2
175	81,64,56,55,51,43,39,38,35,33,31,30,29,20,18,16,14,9,8,5,4,3,2,1

This document was translated from L^AT_EX by H^EV^EA.