Problema de optimizare ! Ajutor !

[•Grimley]

Buna ziua, de ceva timp caut ajutor in rezolvarea unei probleme si nu am gasit, ori nu am stiut unde sa ma uit sa pot gasi ceva asemanator sa ma ajute sa gasesc o solutie buna. Lucrez la o aplicatie pentru un constructor de case si am ajuns in momentul in care trebuie sa ii fac un raport de materiale consum care de fapt ma duce intr-o problema, la prima vedere clasica, de optimizare. Sa trec direct la subiect. Pe parcursul unui proiect se folosesc scanduri de diferite marimi in functie de marimea unei usi, unui dulap etc. Toate aceste produse finite( usa, dulap, podea) se construiesc folosind scanduri . Astfel, la finalizarea proiectului se emite un raport de materiale care ii spune omului, in fctie de ce produse finite are cate scanduri are nevoie. De ex:

PRODUS   SCANDURI MARIME
----------------------------
USA        2             2 m          = 4m
USA        2             1 m          = 2m
DULAP     6             1.5 m       = 9m
DULAP     4             1 m          = 4m

TOTAL                                     19m scandura necesar

Totul este simplu pana acum, numai ca constructorul nu poate cumpara scanduri de 1.9 m sau 0.8 ci el cumpara scanduri la dimensiune standard de 5 m.In cazul meu daca are nevoie de 19m scandura ar trebui sa cumpere 4 scanduri la 5m si cu asta a terminat. Problema apare insa la taiere, astfel incat degeaba cumpara el 4 scanduri de 5 m, daca dupa ce a facut dulapul de exemplu a ramas cu mai multe bucati care insumeaza in total 6 m sa spunem, dar bucatile fiind mici nu mai pot fi refolosite. Raportul trebuie sa ii furnizeze si un numar minim de scanduri standard fix 5 m, care sa acopere taierile si sa nu exista, sau sa existe pierderi cat mai putine. Fiind vorba de bani...optimizare trebuie sa fie cat mai buna.


Asta ar fi situati, transpusa in problema de algoritmi ar arata asa:

Se da limita L = 5.
Se da un vector de dimensiune N cu valori reale.
 

In cazul meu v = {2 , 2 , 1 , 1 , 1.5 , 1.5 , 1.5 , 1.5 , 1.5 , 1.5 , 1 , 1 , 1 , 1}

Sa se genereze o matrice(sau ceva) astfel incat fiecare linie sa se compuna din elementele vectorului dat. Scopul este ca pe fiecare linie a matricii , suma elementelor sa nu depaseasca limita L iar diferenta intre suma elementelor si limita L sa fie minima.

in cazul prezentat solutia ar fi urmatoarea:

M=
{
  {2 , 2 , 1}                                //pierdere 0
  {1 , 1.5 , 1.5, 1 }                       //pierdere 0
  {1.5 , 1.5 , 1 , 1}                       //pierdere 0
  {1.5 , 1.5, 1}                            // pierdere 1
}

Total Piederi : 1


Un alt exemplu mai putin ideal ar fi:

v = {2,4,1,4.5}

M=
{
{ 4 , 1 }             //Pierdere 0
{ 4.5 }              //Piedere 0.5
{ 2}                  //Pierdere 3
}

Total Piederi: 3.5



Orice ajutor, orice sfat este binevenit. Un link la o problema similara, sau la un algoritm, o sguestie sau un sut in spate....sunt bine primite.

Va multumesc anticipat 

[•crawler]

pentru cazuri mici baga backtracking. [cel mult 10-11 scanduri]

pentru cazuri mari imparte cazuri mici random de mai multe ori  [ai incredere in mine ]

vezi ca ai mai multe optimizari de genu:

- scoti afara scandurile care au lungimi standard
- scoti perechile si tripletele care au suma lunigimilor lungimi standard [sau care se incadreaza intro pierdere medie gen 5%]
- poti calcula validitatea unei solutii in backtracking pe parcursul generarii
- poti sa nu generezi pentru un caz o solutie mai proasta decat una gasita pana acum
- poti palaleliza
- poti baga o implementare in C++ si nu in Java/Python

spor la treaba

PS: sa folosesti Mersenne twister http://en.wikipedia.org/wiki/Mersenne_twister

[•Grimley]

In primul rand multumesc pentru raspuns.

Chestia e ca nu am prea multe cazuri cu putine scanduri. Vorbesc aici de sute. Evident toate scandurile care sunt mai mari decat Limita (5) sunt scoase separat. Nu ma intereseaza alea. Trebuie sa lucrez numai cu cele sub 5m.
O marja de eroare oricum am, adica problema e mult mai complexa, se da o marja de eroare se da o limita variabila...dar am redus-o la o problema cu cat mai putine date de intrare ca sa pot sa ii stabilesc un core.  In C++ , Borland 6 este aplicatia.

De scos perechile care au suma egala cu limita e mai greu ca trebuie sa le caut oricum. Adica daca scot perechile astea am rezolvat problema:)

Ideea cu validitatea solutiei e f buna si nota cu random. Dar daca prin paralelizare de referi la threaduri, atunci ai nimerit-o. Asta e f buna ideea.

Backtracking-ul este probabil o solutie dar nu cea mai buna. Evident un back tracking modificat poate fi o solutie.

O idee:
Ma gandeam ca la o limita de 5 nu am cum sa pun 2 scanduri de marime 3, mai exact nu am cum sa pun 2 scanduri care au marimea mai mare decat limita/2. Deci odata pornesc cu un atu, ca voi avea o matrice finala cu un numar de linii cel putin egal cu numarul scandurilor care au lungime mai mare decat Limita/2. De aici se poate extinde. Trebuie sa ma duc sa pun pe foaie treburile astea.

Mercik de ajutor. Revin cu o implementare de indata ce am ceva, sa o vedeti si voi...si sa o comentati.

[•crawler]

eu ti-am spus ceva de genu asta

rezolva_grup_scanduri(A)
    daca A are suma lungimilor <= o scandura standard => o folosesti pe aia
    daca A are mai putin de 11 scanduri => rezolva cu back
    altfel de X ori imparte A in doua grupuri B si C apeleaza rezolva_grup_scanduri(B) si rezolva_grup_scanduri(C) compune solutia si vezi daca e mai buna

recomand X cel putin 30 da trebuie testat

ok ... si chestia asta se poate umple de optimizari si smenuri.

[•pauldb]

Daca am inteles bine problema, problema se afla deja pe infoarena cu un enunt putin modificat. Aici gasesti o explicatie a solutiei, iar accesul la surse la problema respectiva e liber. Din pacate, dupa cum vei vedea, noi stim sa calculam rezultatul exact in complexitate O(2^N *N²), unde N e numarul total de scanduri. Asta totusi inseamna ca poti calcula rezultatul exact pentru N aproximativ 20 (depinde si cat de repede doresti sa dai rezultatul inapoi). In problema nu se cere reconstituirea solutiei, dar este posibila (pentru fiecare stare din programarea dinamica tii indicii din care ai venit).

Nu cunosti o limita pentru numarul de tipuri diferite de scanduri dintr-o comanda? Asta ar putea ajuta mult, cred.

[•Grimley]

Buna,

  Am vazut acum link-ul catre problema care mai exista deja. O sa arunc o privire. Situatia este in felul urmator. Se poate ajunge pana la un numar de 2000 de scanduri. Si mai multe chiar. Partea buna a lucrurilor este ca dimensiunile se repeta.  Adica eu construiesc un produs, la care am nevoie de 2 scanduri de 2 metri si 2 de 1.4 In proiectul meu pot sa am 2 mii de produse de acelasi fel, dar dimensiunile diferite pe scandura nu sunt foarte multe de obicei. Adica nu cred ca sunt mai mult de 20. Si ma gandesc sa aplic un algoritm pt un numar mai mic de scanduri si apoi sa ma folosesc de rezultate ca sa multiplic rezultatul final. Hai sa dau un rezultat mult mai concret si sa spun ce am facut eu pana acum.

Plecand de la ideea ca oricum ar fi daca am o limita de L = 6, orice scandura mai mare de L/2 (3 m) formeaza un vector solutie, deci deja scot pe cele mari. Aplicand acest principiu am facut un algoritm care arata astfel:

- vectorul V este vectorul initial, fiecare elemet reprezinta o scandura din necesar
- matricea M a solutiilor, fiecare linie reprezinta o scandura standard de lungimea L iar componentele liniilor (coloanele) sunt dimensiunile din necesar care compun scandura de lungime L


De ex:
Am din raport un necesar de 10 bare sa spunem de urmatoarele dimensiuni:
V( 4,3,3,4,2,3,2,2,3,4)
LIMITA L=6
M = matricea finala a solutiilor care initial este nula

1) Sortez vectorul desc
V=(4,4,4,3,3,3,3,2,2,2)

2) Pun primul element din V in M
V = (4.4,3,3,3,3,2,2,2)
M = ((4))

3) Incerc sa pun urmatorul element din V, dar verific daca elementtul poate fi adaugat pe aceiasi linie (Suma elementelor pe linie nu depaseste LIMITA 6) In cazul meu 4+4 = 8 deci depaseste limita si trebuie sa mai creez o linie in M. V si M arata astfel:
V = (4,3,3,3,3,2,2,2)
M =
(
(4)
(4)
)

4)
V = (3,3,3,3,2,2,2)
M =
(
(4),
(4),
(4),
)

5)
V = (3,3,3,2,2,2)
M =
(
(4),
(4),
(4),
(3)
)

6) Pasul 6 aduce ceva nou, pentru prima oara am un element care poate fi adaugat. Evident verifica daca poate fi adaugat in prima linie in a doua samd pana ajung la linia a 4a care  imi permite sa adaug noul element din V deoarece 3+3 =<= L care este 6

V = (3,3,2,2,2)
M =
(
(4),
(4),
(4),
(3,3)
)

7)
V = (3,2,2,2)
M =
(
(4),
(4),
(4),
(3,3),
(3)
)

7)
V = (2,2,2)
M =
(
(4),
(4),
(4),
(3,3),
(3,3)
)

Pasul 8 aduce ceva nou, elementele vectorului V pot fi integrate in partea initiala a matricii finale deoarece V fiind sortat desc, elementele din V devin din ce in ce mai mici
V = (2,2)
M =
(
(4,2),
(4),
(4),
(3,3),
(3,3)
)

9)
V = (2)
M =
(
(4,2),
(4,2),
(4),
(3,3),
(3,3)
)

10)
V = ()
M =
(
(4,2),
(4,2),
(4,2),
(3,3),
(3,3)
)

11) PAS FINAL ;' o mica analiza
V = ()
M =
(
(4,2), = necesar 4+2 = 6 ; LIMITA - total necesar = 6 - 6; Pierdere = 0
(4,2),= necesar 4+2 = 6 ; LIMITA - total necesar = 6 - 6; Pierdere = 0
(4,2),= necesar 4+2 = 6 ; LIMITA - total necesar = 6 - 6; Pierdere = 0
(3,3),= necesar 3+3 = 6 ; LIMITA - total necesar = 6 - 6; Pierdere = 0
(3,3)= necesar 3+3 = 6 ; LIMITA - total necesar = 6 - 6; Pierdere = 0
)
Total Pierderi = 0

Concluzii : Acesta este un caz ideal evident dar solutie este foarte rapida, datorita numarului mic de iteratii si rezultatul este satisfacator. Am rulat exemplul pentru 20 de numere reale de aceasta data , toate diferite si am avut o pierdere de 5-10%.
Ma bucuram de rezultate cand clientul a aplicat algoritmul pe o situatie reala si a aplicat alg unui alt soft(nemtesc - si care in opinia lui e cel mai bun, iar noi toti suntem prosti) iar comparatia dintre rezultatele mele si rezultatele lui au fost devastatoare pentru mine. El a avut o pierdere de 3 ori mai mica. O sa mai scriu un post si cu rezultatele algoritmului meu si cu rezultatele algoritmului lui , cu concluziile ce le-am tras...sa mai avem pe ce discuta.

Mercik

[•Grimley]

Am revenit. Am promis ca o sa scriu rezultatele algoritmului meu aplicate unui caz real si rezultatele algoritmului marelui soft nemtesc aplicate pe acelasi caz:

Am urmatorul caz:
NECESAR:
Bucati scanduri   Marime
100                   2.5 m
100                   2.4 m
400                   1.58 m
400                   1.39 m

Limita este de 6, adica nu se pot cumpara scanduri decat de 6 m. Intrebarea clasica, de cate scanduri am nevoie ca sa pot sa tai toate scandurile din NECESAR.

               
Nr Scanduri 6m   Nr Sc. Necesar   Lung.Scandura Nec.   Total Folosit Pe Scandura   Total Pierdere Pe Scandura    Pierdere
--------------------------------------------------------------------------------------------------------------------------
50                   2                   2.5                           5                                   1                                   50
--------------------------------------------------------------------------------------------------------------------------
50                   2                   2.4                           4.8                                   1.2                                   60
--------------------------------------------------------------------------------------------------------------------------
100                   3                   1.58                           4.74                                   1.26                                   126
--------------------------------------------------------------------------------------------------------------------------
33                   3                   1.58                           4.74                                   1.26                                   41.58
--------------------------------------------------------------------------------------------------------------------------
1                   1                   1.58         
                   3                   1.39                           5.75                                   0.25                                   0.25
--------------------------------------------------------------------------------------------------------------------------
99                   4                   1.39                           5.56                                   0.44                                   43.56
--------------------------------------------------------------------------------------------------------------------------
1                   1                   1.39                           1.39                                   4.61                                   4.61
--------------------------------------------------------------------------------------------------------------------------
                                                                                                                                Total Pierderi 326m (cam 50 sc)

Rezultatele softului nemtesc pe acelas necesar:


Nr Scanduri 6m   Nr Sc. Necesar   Lung.Scandura Nec.   Total Folosit Pe Scandura   Total Pierdere Pe Scandura    Pierdere
--------------------------------------------------------------------------------------------------------------------------
50                   2                   2.5                            5                                   1                                   50
--------------------------------------------------------------------------------------------------------------------------
50                   2                   2.4                            4.8                                   1.2                                   60
--------------------------------------------------------------------------------------------------------------------------
200                   2                   1.58         
              2                   1.39                            5.94                                   0.06                                   12
--------------------------------------------------------------------------------------------------------------------------
                                                                                                                                 Total Pierderi 112m (cam 19 sc)

E foarte logic cum sunt puse in raportul al doilea, si eu le-as pune la fel daca le-as lua la mana, chestia e ca timpul lui de calcul e f ok si rezultatul de asemenea. Intrebarea ?..cu ce algoritm a ajuns el la acest rezultat.

[•Cosmin]

Cred ca problemei tale ii zice m-dimensional knapsack problem.

La concursul ginfo prin 2003 s-a dat ceva de genul asta si strategia cu care am luat 100 de puncte a fost 2opt. Porneam de la o configuratie random de repartizare a ce scanduri se obtin din ce bucata si cu o functie distanta de la solutia curenta la o solutie perfecta. Pentru distanta am incercat diverse functii ca suma patratelor erorilor, suma erorilor, maximul erorilor, numarul erorilor sadm.
La fiecare pas incercam sa interschimb 2 scanduri intre ele si sa vad daca obtin o solutie egala sau mai buna.
Cand ma blocam in optim local incercam acelasi lucru permutand 3 scanduri. Dupa un anumit numar de iteratii in care solutia nu a fost imbunatatita incercam o noua configuratie initiala.