Discussion :

[sidahmed]

Bonjour,

j'ai un stock infini de baguettes en bois de longueur L, et j'ai un certain nombre de cadres à fabriquer, chacun a sa quantité et ses dimensions :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
Stock de Q baguettes de longueur L cm
 
N cadres à fabriquer :
cadre 1 : x1 / y1 cm avec une quantité Q1,
cadre 2 : x2 / y1 cm avec une quantité Q2,
...
cadre n : xn / yn cm avec une quantité Qn
 
xi : longueur   yi : largeur
 
Chaque cadre i contient 2 morceaux de xi cm et 2 morceaux de yi cm

Le problème est comment dois-je procéder pour couper les B baguettes afin de réduire les chutes (petits morceaux à jeter) au minimum ?

Merci de votre aide.

Cordialement,
Sidahmed.

[alex_pi]

En reformulant un peu, tu as des boites de capacité L, et tu dois ranger dedans des éléments de capacités x1, y1, etc. Bref, ça ressemble à un bin packing problème. Je dis bien que ça *ressemble*, parce qu'il y a à chaque fois un nombre paire éléments de longueur x1 (etc). Mais ça m'étonnerait que ça leve la NP-complétude du problème décisionnel associé (mais je ne l'ai pas prouvé).

[sidahmed]

Bonjour,

je me pose la question suivante : est-ce qu'on va minimiser les chutes de l'ensemble des baguettes (minimum global) ou bien minimiser les chutes par baguettes (une chute par baguette) : ce qui représente un minimum local par chaque baguette et la somme de ces minima représentent les chutes restantes mais ne constituent pas nécessairement le minimum global ?

Bref, minimum global (ce que je pense) ou somme des minima locaux ?

Si le but est la recherche du minimum global, comment peut-on déterminer le nombre de baguettes nécessaire qui dépend des chutes ?

Merci d'avance.

Cordialement,
Sidahmed.

[FrancisSourd]

C'est une petite variante du Cutting Stock problem.

[sidahmed]

Bonjour,

merci Monsieur FrancisSourd, c'est bien le problème recherché.

Je n'ai pas encore compris la méthode mais je compte l'implémenter, cependant je voudrais obtenir un devis estimatif à propos de l'implémentation de cette méthode d'optimisation.

Merci d'avance.

Cordialement,
Sidahmed.

[FrancisSourd]

Je suppose que tu parles toujours d'un algorithme de résolution exacte.

C'est difficile de répondre car cela dépend beaucoup de ce que tu connais en programmation linéaire et en génération de colonnes. C'est typiquement un projet de niveau bac+5 pour un étudiant qui a eu un bon cours d'optimisation discrète.

Ensuite, les chercheurs s'intéressent toujours à améliorer la résolution de ce problème. Je pense donc que tu peux y investir ta vie entière si cela te motive!

Si tu ne veux quasiment rien investir, j'ai vu cette applet en ligne:
http://www-fp.mcs.anl.gov/otc/GUIDE/...ing/index.html

J'imagine qu'il y a également beaucoup de codes disponibles en ligne.

[sidahmed]

Bonjour,

Je suppose que tu parles toujours d'un algorithme de résolution exacte.

Oui, je cherche la solution optimale.

C'est difficile de répondre car cela dépend beaucoup de ce que tu connais en programmation linéaire et en génération de colonnes. C'est typiquement un projet de niveau bac+5 pour un étudiant qui a eu un bon cours d'optimisation discrète.

Merci pour ces conseils, logiquement j'ai le niveau requis.

À propos de la programmation linéaire, j'ai étudié le module de recherche opérationnelle, mais c'était uniquement une introduction à la programmation linéaire avec l'utilisation de la méthode graphique pour les problèmes à deux variables, et la méthode du Simplexe pour tous les cas.

Mais ça reste de la programmation linéaire en nombre réels, or ce problème nécessite une méthode de résolution se basant sur les nombres entiers.

Ensuite, les chercheurs s'intéressent toujours à améliorer la résolution de ce problème. Je pense donc que tu peux y investir ta vie entière si cela te motive!

Ah bon ! Je pensais que l'article vers lequel tu m'as envoyé décrivait la méthode de résolution optimale.

Si tu ne veux quasiment rien investir, j'ai vu cette applet en ligne:
http://www-fp.mcs.anl.gov/otc/GUIDE/...ing/index.html

J'imagine qu'il y a également beaucoup de codes disponibles en ligne.

Merci beaucoup pour ces liens, cependant je voudrais bien coder moi-même la solution, histoire de s'entraîner, comprendre la logique de fonctionnement et pour une éventuelle reprise de code ...

Je suis très reconnaissant, merci beaucoup.

Cordialement,
Sidahmed.

[FrancisSourd]

Mais ça reste de la programmation linéaire en nombre réels, or ce problème nécessite une méthode de résolution se basant sur les nombres entiers.

Effectivement. Je te conseille vivement de lire un article ou un livre assez détaillé sur la génération de colonne appliquée à ce problème (outre le lien précédent, p.ex. linear programming de Chvatal).

Ah bon ! Je pensais que l'article vers lequel tu m'as envoyé décrivait la méthode de résolution optimale.

Le problème est effectivement bien résolu... mais on peut toujours essayer de faire mieux (et d'étudier des variantes).

[sidahmed]

Bonsoir,

Effectivement. Je te conseille vivement de lire un article ou un livre assez détaillé sur la génération de colonne appliquée à ce problème (outre le lien précédent, p.ex. linear programming de Chvatal).

Ok, je vais me documenter sur l'approche Delayed Column Generation et la méthode Branch and Bound car franchement je n'ai aucune idée sur la programmation linéaire en nombres entiers.

Le problème est effectivement bien résolu... mais on peut toujours essayer de faire mieux (et d'étudier des variantes).

D'accord, je comprends mieux, merci FrancisSourd.

Bref, minimum global (ce que je pense) ou somme des minima locaux ?

Si le but est la recherche du minimum global, comment peut-on déterminer le nombre de baguettes nécessaire qui dépend des chutes ?

Tout à fait, on doit minimiser la différence entre la longueur totale des baguettes découpées et la longueur totale des différents morceaux rectangles à fabriquer, d'où la recherche du minimum global.

Cependant, je ne savais pas qu'on devait procéder en deux étapes :
Déterminer les plans de découpe des baguettes;
Formuler le PLNE puis le résoudre.

Exemple :
Baguette de longueur L = 150 cm
432 morceaux de 40 cm, 500 morceaux de 60 cm et 400 morceaux de 70 cm.
Il y a six plans de découpes, à savoir :
2 * 70 cm
60 + 70 cm
2 * 40 + 70 cm
2 * 60 cm
2 * 40 + 60 cm
3 * 40 cm

Mon problème est comment trouver tous ces motifs de découpage (non pas à la main, bien sûr !).
Je ne vois qu'un seul algorithme bourrin :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
nb40Max <- L / 40;
nb60Max <- L / 60;
nb70Max <- L / 70;
 
Varier ces trois variables de 0 à nb?0Max 
(? = 4, 6 ou 7) et voir si la somme de ces 
variables multipliées par leur longueur respective 
ne dépasse pas L !

Est-ce que cette méthode est bonne ? Existe-il d'autres méthodes plus efficaces que celle-ci ? Merci d'avance.

Cordialement,
Sidahmed

[FrancisSourd]

Est-ce que cette méthode est bonne ? Existe-il d'autres méthodes plus efficaces que celle-ci ? Merci d'avance.

Oui, cela me semble être la bonne méthode: comme il faut trouver toutes les solutions, la méthode est forcément énumérative (i.e. bourrin).

Tu peux un peu améliorer la chose: une fois que tu as fixé le nombre de baguettes de longueur 40, tu connais la longueur restante à couvrir par les deux autres baguettes. Donc tu peux mettre à jour dynamiquement nb60Max (et pareil ensuite pour nb70max).

[sidahmed]

Tu peux un peu améliorer la chose: une fois que tu as fixé le nombre de baguettes de longueur 40, tu connais la longueur restante à couvrir par les deux autres baguettes. Donc tu peux mettre à jour dynamiquement nb60Max (et pareil ensuite pour nb70max).

Franchement, je n'ai pas compris ton idée !

[FrancisSourd]

Voici un petit bout de code pour être plus clair:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
pour i=0 à L/40
  pour j =0 à (L-40i)/60
    pour k=0 à (L-40i-60j)/70
       ecrire i j k

[sidahmed]

Bonjour,

Nos deux algorithmes fournissent des résultats erronées, c'est-à-dire qu'ils affichent des plans de découpe en plus : ils affichent 12 motifs, au lieu des six plans de découpe sus-cités !

C'est clair, le problème vient du fait que ces deux algorithmes considèrent que toute somme des variables i, j et k multipliées par leur longueur respective 40, 60 et 70, inférieure à L = 150, comme plan de découpe, ce qui n'est pas logique. En fait, c'est pas une erreur si on considère que i = 40, j = 60 et k = 70 sont des plans de découpe, mais bon...

Je pense qu'il faut considérer ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Si (L - i * 40 + j * 60 + k * 70) < min(40, 60, 70) alors
(i, j, k) représente un plan de découpe.

Et je ne pense même pas de tous ces plans de découpe vont intervenir dans la recherche de la solution optimale, car ça va vite exploser ! D'où, comme vous l'avez proposé, la méthode de génération de colonnes ! Car je ne sais plus comment calculer les plans de découpe si j'ai n morceaux rectangles différents à fabriquer (dans l'exemple précédent, n valait 3).

Il y a un autre problème de passage du PLNE vers sa forme standard pour qu'il puisse être résolu avec l'algorithme du Simplexe (méthode arborescente de Dakin par exemple), voici la modélisation du PLNE de ce problème avec des contraintes sous forme d'inégalités de supériorité :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Min Z = Somme(xj * L) - Somme(Qi * Li)
                     j = 1...n            i = 1...p

Ou tout simplement : Min Z = Somme(xj)
                                        j = 1...n

Pour i = 1...p : Somme(aij * xj) >= Qi
                    j = 1...p

Pour j = 1...n : xj Є IN

n : nombre des motifs de découpe;
p : nombre des types de morceaux à fabriquer;
L : hauteur d'une baguette;
Qi : quantité du morceau i à fabriquer;
Li : son hauteur;
xj : nombre de baguettes découpées selon le plan de découpe j;
aij : nombre de morceaux de type i contenus dans le plan j;
Somme(Qi * Li) est une  constante qu'on peut l'omettre.

Donc pour obtenir la forme standard de ce PLNE, on va introduire des variables d'écart, mais on perd la matrice identité qui nous fournissait une base initiale évidente pour pouvoir démarrer l'algorithme du Simplexe.

Est-ce que je vais utiliser la méthode des deux phases ou bien celle du grand M pour remédier à ce problème de standardisation ? À moins qu'il faut considérer le PLNE dual du PLNE primal.

À suivre...

[FrancisSourd]

Nos deux algorithmes fournissent des résultats erronées, c'est-à-dire qu'ils affichent des plans de découpe en plus : ils affichent 12 motifs, au lieu des six plans de découpe sus-cités !

Si je comprends bien, ceux cités correspondent à des "motifs maximaux" au sens de l'inclusion. Toutefois, pour avoir la garantie de l'optimalité, il faut tout générer (i.e. les 12 motifs).

Par exemple, si dans la commande, il n'y a qu'une seule baguette de 40 à couper, les 6 motifs générés ne permettent pas de satisfaire exactement la commande car les motifs génère soit 0 soit 2 soit 3 baguettes de 40.

Bonjour,
Est-ce que je vais utiliser la méthode des deux phases ou bien celle du grand M pour remédier à ce problème de standardisation ? À moins qu'il faut considérer le PLNE dual du PLNE primal.

J'utilise en général des solveurs existants (commercial ou opensource) qui m'évitent de me poser ces questions.

Sinon, effectivement, la méthode à deux phases permet effectivement de trouver une base réalisable. Mais, comme tu connais ton problème (ie la signification des variables), il ne doit pas être difficile de fabriquer une base réalisable même lorsque tu as ajouté les variables d'écart.