Re: [Caml-list] Problème_de_l'achat_par_lots

From: "alphablock" <alphablock@wanadoo.fr>
To: "Diego Olivier Fernandez Pons" <Diego.FERNANDEZ_PONS@etu.upmc.fr>,
	<caml-list@inria.fr>
Subject: Re: [Caml-list] Problème_de_l'achat_par_lots
Date: Sun, 31 Jul 2005 19:26:00 +0200	[thread overview]
Message-ID: <004401c595f5$1f131e80$92e7f8c1@oemcomputer> (raw)
In-Reply-To: <Pine.A41.4.44.0507311702350.1478660-100000@ibm1>

Bonsoir,

Vous n'avez pas trouvé le code Caml ?
C'est la fonction "place_order", en bas de page, sur un fond-cadre
légèrement grisé.

En fait j'ai programmé cette fonction "à l'intuition" et je suis bien
incapable de dire à quelle catégorie de solution elle appartient
(l'autodidacte a toujours ses lacunes). Ce que je peux affirmer c'est que je
l'ai testée sur des exemples non triviaux dans le domaine qui m'intéresse
(décomposition d'une maquette lego en un inventaire de boîtes de legos à
acheter) et qu'elle fonctionne à merveille. Reste à savoir comment elle va
se comporter en performance quand le catalogue va grossir jusqu'à  plus de
6500 boîtes legos connues. Si vous en avez une idée, ne vous privez pas de
la partager.

Ma page d'exercice
http://www.ocaml-tutorial.org/implement_an_inventory_facility
est sur un Wiki, donc éditable, si vous trouvez un meilleur lien pour le
problème du sac à dos, vous pouvez cliquer sur [edit].

Considérations,

- damien

----- Original Message -----
From: "Diego Olivier Fernandez Pons" <Diego.FERNANDEZ_PONS@etu.upmc.fr>
To: <caml-list@inria.fr>
Cc: <damien.guichard@wanadoo.fr>
Sent: Sunday, July 31, 2005 5:21 PM
Subject: Re: [Caml-list] Problème_de_l'achat_par_lots

    Bonjour,

> Cepandant j'ai choisi la méthode du "backpack problem" (problème du
> sac-à-dos), bien plus facile à implémenter, et j'en ai fait un
> exercice visible sur http://www.ocaml-tutorial.org.

Traditionnellement, on dit plutôt knapsack (problème du sac à dos),
c'est la terminologie adoptée par les ouvrages de référence :
- Knapsack problems. Martello et Toth 1990
- Knapsack problems. Kellerer, Pferschy et Pisinger 2003

Les problèmes de packing et de covering sont symétriques : dans le
premier cas on maximise le coût sans dépasser la borne (sac à dos),
dans l'autre on minimise le coût sans passer en dessous de la borne
(set-cover).

Votre problème est proche des deux classes sans s'y mouler vraiment.

Cela dit, pour résoudre le problème de sac à dos il y a (encore et
toujours) 3 méthodes :
- programmation linéaire en nombres entiers
- énumération implicite
- programmation dynamique

Je n'avais pas cité la dernière dans mon courrier précèdent car je ne
sais pas si elle est appliquable à votre problème spécifique.

Notez également que subset-sum problem pour lequel j'ai fourni du code
Caml est un cas particulier de knapsack.

> voir ici l'énoncé de l'exercice et la solution à l'aide de la
> méthode du sac-à-dos:
>
> http://www.ocaml-tutorial.org/implement_an_inventory_facility
>

Je n'ai pas trouvé de code Caml.

La page que vous pointez dans l'exercice est très intéressante :
l'auteur dit qu'utiliser une méthode d'énumération implicite est trop
lourd pour le problème de sac à dos, il propose donc une méthode ...
d'énumération implicite.

        Diego Olivier

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs