ogólnobarokowy problem optymizacyjny
Wlodzimierz Holsztynski
reprezentantów czyli pracowników. Z każdym pracownikiem
firmy F_k związujemy wektor w \in R^n, który ma
współrzędną w(k) ujemną, a pozostałe nieujemne.
Współrzędna w(k) oznacfza (-1)*dochód, który firmie
F(k) należy się za godzinę pracy jej reprezentanta w.
Pozostałe współrzędne w(j) oznaczają wartość
godzinnej pracy w dla firmy F_j. Powstaje pytanie,
czy istnieje zespół pracowników, co najwyżej po
jednym z każdej firmy, który nie przynosi straty
żadnej z firm, a więc jest samowystarczalny:
chodzi o to by suma wybranych wektorów miała
wszystkie współrzędne nieujemne.
Ogólnie, wektor o dokładnie jednej wspólrzędnej
ujemnej nazywam studnią. Zatem wszyscy pracownicy
razem, ze wszystkich Firm F_1 ... F_n tworzą pewien
zbiór studni F, zawarty w R^n. Sformułuję pytanie raz
jeszcze:
ZADANIE 0 Dany jest skończony zbiór studni F
========= w przestrzeni R^n. Znajdź podzbiór
A zbioru F, taki, że dla każdego k=1...n istnieje
co najwyżej jedna studnia w \in F taka, że w(k) < 0,
oraz suma A ma mieć wszystkie wspólrzędne nieujemne:
Sum (w(k) : w \in A) >/ 0 dla każdego k=1...n
Ściślej mówiąc chodzi o algorytmy, i o szybkośc
otrzymania rozwiązania lub zdecydowanie, że go nie ma,
w terminach n oraz |F|. Można rozpatrywac też
wypadki szczególne, gdy nakładamy ograniczenia
na zbiór F. Wtedy złożoność algorytmów powinna
się obniżać. Na przykład, gdy zakładamy, że
F jest zawarte w Z^n (czyli wszystkie współrzędne
wektorów studni są całkowite), to złożoność
zależy nie tylko od n i |F| (liczebność F, zwana mocą),
ale także od normy F:
||F|| := max ( |w(k)| : w \in F, k=1...n)
ZADANIE 1 Znajdź rozwiązanie A Zadania 0,
========= o największym nośniku, czyli o
największej mocy |A|.
Pozdrawiam,
Włodek
Mirek
>
> Mamy n firm: F_1 ... F_n. Każda ma pewną liczbę
> reprezentantów czyli pracowników. Z każdym pracownikiem
> firmy F_k związujemy wektor w \in R^n, który ma
> współrzędną w(k) ujemną, a pozostałe nieujemne.
> Współrzędna w(k) oznacfza (-1)*dochód, który firmie
> F(k) należy się za godzinę pracy jej reprezentanta w.
O tym samym wspominałem na naszej grupie w wątku
"Algorytmika - kolejny szalony pomysł"
gdzie dałem odsyłacz do mojej dyskysji na sci.op-research
http://groups.google.pl/group/sci.op-research/msg/e2c8119afb91ff6b
Wg ludzi, którzy tam odpowiedzieli, obecny stan
wiedzy (a raczej ogólnodostępnego oprogramowania)
nie zmienił się od wielu lat.
Takie samo pytanie (z taką samą odpowiedzią) było
na sci.op-research w 1997 roku. A autorem tamtego
wątku był sam Ron Sorli ;)
Z tego co można wywnioskować z wygooglanych jego
publikacji (w tym doktoratu) to wg mnie wiele
więcej nie zrobił, poza przeniesieniem obliczeń
na klaster maszyn. Tzn. dokładniej z programu z
sci.op-research raczej korzystał tylko na
początku - jest on bowiem zbyt ogólny. Ale nie
dokonał raczej żadnych istotnych postępów
algorytmicznych. Grant miał na technikę obliczeń
rozproszonych, a nie na liczby barokowe ;)
Choć trzeba by to jeszcze raz przeanalizować, czy
miał jakieś przyspieszacze - ale nic mi się nie
rzuciło w oczy w pobieżnej lekturze.
> Ogólnie, wektor o dokładnie jednej wspólrzędnej
> ujemnej nazywam studnią. Zatem wszyscy pracownicy
> razem, ze wszystkich Firm F_1 ... F_n tworzą pewien
> zbiór studni F, zawarty w R^n. Sformułuję pytanie raz
> jeszcze:
Ogólnie: w terminologii OR czy optymalizacji tak
sformułowane zadanie to problem poszukiwania
rozwiązań dopuszczalnych. Ponieważ jest to
wstępny podproblem ogólnego zadania
optymalizacji, to wielu traktuje go per noga :(
> ZADANIE 0 Dany jest skończony zbiór studni F
[...]
> Ściślej mówiąc chodzi o algorytmy, i o szybkośc
> otrzymania rozwiązania lub zdecydowanie, że go nie ma,
> w terminach n oraz |F|.
Moim skromnym zdaniem w naszych dyskusjach
i w przeglądanej literaturze dla tak "ogólnego
zadania" nie zauważyłem żadnych jak Ty nazywasz
rakiet. Jedyne co można i trzeba wykorzystać to
lista rekomendacji.
W swoim (nieoptymalnym) programie nic odkrywczego
nie wymyśliłem. Wybieram "studnię" z p_max^1 i
dla danego przebiegu próbuję zapychać ją
korzystając z rekomendacji. Używam tylko liczb
mniejszych od p_max. W tym procesie pojawiają się
więcej niż jedna współrzędne wektora o ujemnych
współczynnikach. Z moich obserwacji wynika, że w
przynajmniej większości przypadków opłacalna jest
strategia zapychania najpierw "dziur" dla
największych liczb pierwszych.
W aktualnym stanie program robi ok 400.000 kroków
na sekundę, a że dla niektórych p_max liczba
kroków jest atronomiczna to nie wygląda to
obiecująco. Obliczenia testowe robiłem na bazie
tabeli 5000+.
Po wakacjach zamierzam się skontaktować z tym
niemieckim profesorem, co pisał (w abstrakcie),
że istnieje "efektywny" algorytm poszukiwania
liczb barokowych dla danej p_max. Ale nie jestem
pewien czy to się uda, gdyż jego strona nie jest
aktualizowana od kilku lat. W razie czego
spróbowałbym zaczepić Achima - jemu łatwiej
byłoby poszukać "tubylcze" kontakty.
> ZADANIE 1 Znajdź rozwiązanie A Zadania 0,
> ========= o największym nośniku, czyli o
> największej mocy |A|.
Czarno na razie to widzę - w sensie znalezienia
jakiś ulepszeń/przyspieszeń w stosunku do Zadania 0.
Ciągle nie mam czasu aby przyjżeć się dokładniej
temu co stosują chyba wszyscy wymienieni w
innym liście współcześni barokowcy komputerowi:
sigma chains. Wg tego co na mersenne forum
napisał Joseph Chen wygląda to tak - jest baza
potęg małych liczb pierwszych, w której
rekomendacje są w jakiś sposób zredukowane do
bardziej użytecznej postaci, następnie losują
dużą liczbę pierwszą i próbują czy daje się
znaleźć ścieżkę łączącą ja z bazą sigma chains.
Mirek
Wlodzimierz Holsztynski
O, odezwałeś się jednak. Nie spodziewałem się,
i równolegle dałem sformułowanie ogólnego
barokowego problemu (moja termionologia--z tego
co piszesz, to problem nie jest nowy?)
na sci.math, sci.math.research i alt.pl.matematyka.
Z tym, że dałem tam suchsze sformułowanie. Już obecną,
siepniową wersję programu napiszę w tym duchu, czysto,
program będzie wciąż nieco ładniejszy.
Mirku, jestem rozżalony, że nie piszesz nic o liczbach
barokowych, otrzymanych przez mój program brqJul.
Prosiłem Cię więcej niż raz, żebyś poświadczył, że mój
program rzeczywiście daje liczby barokowe, w tym
największe znane przy ograniczeniu ord_2(b) \< 29. Masz
mój program od dłuższego czasu, trochę się nim bawiłeś,
ale nie chcesz potwierdzić, że daje wyniki, które ogłosiłem.
(No nic, dostanę nowe liczby barokowe i obejdę się bez
poświadczeń, to tylko kwestia tygodni, maksimum miesięcy).
> On Tue, Aug 07, 2007 at 12:21:33AM -0700, Wlodzimierz Holsztynski wrote:
>
> > Mamy n firm: F_1 ... F_n. Każda ma pewną liczbę
> > reprezentantów czyli pracowników. Z każdym pracownikiem
> > firmy F_k związujemy wektor w \in R^n, który ma
> > współrzędną w(k) ujemną, a pozostałe nieujemne.
> > Współrzędna w(k) oznacfza (-1)*dochód, który firmie
> > F(k) należy się za godzinę pracy jej reprezentanta w.
>
> [...]
>
> O tym samym wspominałem na naszej grupie w wątku
>
> "Algorytmika - kolejny szalony pomysł"
>
> gdzie dałem odsyłacz do mojej dyskysji na sci.op-research
Odsyłacz wyglądał jak coś ze środka (jak psu z gardłą
wyjęty :-). Ponadto skrzętnie skryłeś fakt, że inspirował
Cię nasz projekt barokowy. Tym bardziej oczom trudno
było się zatrzymać, o coś zahaczyć. Przy następnych
okazjach będę wspominał, że doszedłeś do sformułowania
tego problemu w czerwcu. Piszesz, że problem był
podany przez Rona Sorli już w 1997 rokou (tak?).
Po trochu Twoje pisanie i moje Ciebie rozumienie
będą się przybliżać, byleś przykładał się do
komunikowania, bo ja staram się. Pamiętaj, że
wszyscy, na pewno ja, mamy wszelakie kłopoty
codzienne, że jest wiele do czytan ia, itd. Też
staram się o tym pamiętać. Ponadto jednak powołuj
się na swoje źródła i odskocznie.
> http://groups.google.pl/group/sci.op-research/msg/e2c8119afb91ff6b
> Takie samo pytanie (z taką samą odpowiedzią) było
> na sci.op-research w 1997 roku. A autorem tamtego
> wątku był sam Ron Sorli ;)
A możesz dać link do Sorliego?
> Moim skromnym zdaniem w naszych dyskusjach
> i w przeglądanej literaturze dla tak "ogólnego
> zadania" nie zauważyłem żadnych jak Ty nazywasz
> rakiet.
Nie pamiętam "rakiet". Poszukam :-)
> Jedyne co można i trzeba wykorzystać to
> lista rekomendacji.
Zajęło Ci zrozumienie tego sporo czasu, wreszcie
cyknęło, ale to od początku o to mi chodziło,
choć może dopiero teraz zechciało m i się to
kompletnie napisać, bo tak programuję. Cały
czas de facto pisałem, że o samych liczbach
pierwszych można zapomnieć, są jakby końcową
dekoracją i nagrodą, ale używam indeksów
liczb pierwszych, wykładników, rekomendacji.
> W swoim (nieoptymalnym) programie nic odkrywczego
> nie wymyśliłem. Wybieram "studnię" z p_max^1 i
> dla danego przebiegu próbuję zapychać ją
> korzystając z rekomendacji.
Mniej więcej Cię chyba rozumiem. Chyba wielu ludzi
tak postępowało. Pierwsze (znane) baroki odkrywałem
na nowo ręcznie w ten sposób lub podobny. Z tym że
kierowałem się teorio-liczbowymi względami
w dobieraniu startu, dzięki czemu nawet ręcznie
znajdywałem baroki. Jeden podałem chyba pod
psem. Zacząłem wtedy od rozkładu liczby Mersenna
M(n), która nie była pierwsza (to była M(11)).
> > ZADANIE 1 Znajdź rozwiązanie A Zadania 0,
> > ========= o największym nośniku, czyli o
> > największej mocy |A|.
>
> Czarno na razie to widzę - w sensie znalezienia
> jakiś ulepszeń/przyspieszeń w stosunku do Zadania 0.
Algorytm s.a. ma tendencję obniżania wielkości
nośnika liczb pierwszych, gdyż przy małej liczbie
czynników pierwszych kara ma tendencje do mbycia małą.
Zaradzam temu w swoim nowszym programie, będącym
nieznaczną wariacją tego co Ci posłałem. Jest
to delikatna sprawa. Należy uważać, żeby algorytmu
nie ukatrupić, ani nie skazać na marną egzystencję.
Pozdrawiam,
Włodek