Newsgroup: it.hobby.enigmi
Titolo: Riduttori

Vedo che ogni tanto se ne parla, e devo fare una domanda (non so se sono OT,
se del caso mi puniro' tentando di connettermi con wind per un giorno
intero):
Sia il problema generale di questo tipo (tutti i numeri sono interi):
Dato c = (1, 1, 1, .... ,1) vettore di n elementi,
E matrice di adiacenza di un grafo connesso non orientato (n nodi ciascuno
con un anello, nessun altro limite sugli archi), simmetrica con elementi
sulla diag. princ. tutti a 1,
x vettore binario di n elementi
b vettore di n elementi >= 0,
Risolvere
                  min cx
tale che     Ex >= b.
con            x elem. di {0,1}^n
Se il grafo e' composto dalle colonne del totocalcio, gli archi li mettiamo
tra colonne con distanza pari a 1 (cioe' con un segno di differenza) e b =
(1,1,1,1,..,1), stiamo cercando il ridotto del sistema e Xi alla fine indica
se la colonna i-esima fa parte o meno del ridotto.
La domanda e' questa:
Il problema cosi' posto e' di programmazione combinatoria, e si risolve ad
esempio coi tagli di gomory, B&B o altri modi, tutta roba esponenziale
Suppongo pero' di conoscere il valore del minimo. Inserisco cioe' un
ulteriore vincolo che e'
X1 + X2 + X3 + ... + Xn = tot
dove tot e' il valore che impongo. In pratica sto cercando un riduttore di
dimensione tot.
A questo punto mi trovo con un poliedro "dentro" l'ipercubo unitario, ma
tagliato in basso da una faccetta. E quella faccetta deve essere
soddisfatta, indi la soluzione intera (se c'e') deve stare su quella
faccetta.
A questo punto pero' posso abbandonare la richiesta di avere Xi binario, e
considerare il problema nel continuo.
Risolvo dunque
                  min cx
tale che     Ex >= b.
                   X1 + X2 + X3 + ... + Xn = tot
                   Xi >= 0
Questo si risolve (mi hanno detto che e' vero e ci credo) in tempo
polinomiale con un algoritmo per punti interni, o una cosa simile. Ad ogni
modo si risolve, e trovo una soluzione in genere non intera ma sicuramente
"dentro" l'ipercubo, in virtu' sia della faccetta in basso sia delle Xi >=0.
Mi trovero' quindi su uno spigolo di quella faccetta.
Arrivati a questo punto forzo cambi di base per girarmi tutta la faccetta, e
se trovo una soluzione binaria mi fermo, altrimenti il problema (nel
discreto) non si risolve.
Ricapitolando: risolvo il PL con tempo polinomiale, il cambio di base si fa
in tempo polinomiale, quindi se c'e' una soluzione del sistema con tot
colonne la trovo in tempo polinomiale.
Se la trovo riparto con tot-1 e alla fine, dopo al massimo n iterazioni,
trovo il ridotto ottimo ossia la soluzione al problema iniziale in tempo
polinomiale.
Ora: siccome so che non puo' essere cosi' senno' sarebbe P=NP (e a me
toccherebbe il nobel ma sfigurerei dopo Fo, semmai un oscar con Benigni..),
dov'e' che sbaglio?
Grazie,
Marco

                    X1 + X2 + X3 + ... + Xn = tot
Corrige
                        X1 + X2 + X3 + ... + Xn >= tot
Il >= serve per avere disponibile una soluzione di partenza per il simplesso
(o quello che si usa), che e'Xi = 1.
Marco

 dov'e' che sbaglio?
dipende... da che dipende....
Ciao, Silv:o)

 è la seconda
In realta' ho un'idea di dove potrebbe essere l'inghippo, ma non l'ho
dimostrata e forse non e' neppure vera.
Ho postato il msg per vedere se qualcuno ha un'idea diversa dalla mia (sulla
natura dell'inghippo) e magari piu' semplice.
Resta da dire che, comunque, passando all'atto pratico il tutto e' comunque
ingestibile e ritengo di esclusivo interesse gli algoritmi polinomiali di
ricerca di riduzioni "buone" anche se non ottime. Anche per agganciarmi al
discorso riguardo l'utilita' (o l'interesse) degli algoritmi per determinati
problemi: in questo campo non se ne puo' fare a meno, e tranne alcuni rari
casi gestibili "a mano" in virtu' di particolari simmetrie o condizioni,
senza un programma che macina numeri non si puo' trovare nulla di valido,
imho.
Marco





Posso dirti semplicemente che circa 
due


anni fa ho provato ad applicare un 
metodo


di ottimizzazione binaria, che teoricamente 
è


il modello matematico del problema del 
riduttore,


ma, dovo aver scritto, entusiasta, un 
programma


in basic, ho scornato brutalmente contro i 
tempi


di elaborazione, che mi sono 
sembrati


"piuttosto esponenziali" per non dire 
eterni.


 


Tengo però a dirti che, per i casi semplici, 



la riduzione 
"ottima" è sempre stata trovata


dal mio 
programma, a testimoniare la bontà 


del 
metodo.


Per il resto, quello che mi ha separato 



dal Nobel per 
la 
riduzione sono stati quei


non trascurabili 1200 secoli di 
elaborazione


che si sarebbero resi necessari per 
casi più


complessi; casi che in realtà, oggigiorno 



farebbero 
ridere 
anche un bambino 


(7 doppie,ecc...).


 


Resto però convinto, come mi sembra lo sia 
tu,


che tra tutti quelli che sulle riviste 
"specializzate"


si affannano a trovare i record di 
riduzione,


in realtà in pochissimi conoscono 
l'algoritmo


del simplesso.


 


 


Ciao e buona ricerca


 


Antonio Misericordia


 



Mi pare che l'argomento non sia di interesse.. :)
Ad ogni modo se qualcuno risolvesse l'enigma e volesse segnalarmelo (cosa
molto gradita) puo' farlo scrivendomi qui
in...@fabisoft.it
Marco