Istotnym problemem w programowaniu ca kowitoliczbowym
jest badanie zbioru rozwiazan dopuszczalnych zadania.
Problem istnienia cakowitych punktów dopuszczalnych mozna
rozwiazac poprzez przedstawienie ograniczen w postaci
ukadu równan wielomianowych i wykorzystanie pewnych
wyników geometrii algebraicznej. Zaleznosc miedzy
rozmaitoscia afiniczna i ideaem generowanym przez te
wielomiany pozwala stwierdzic na podstawie twierdzenia
/,Nullstellensatz", czy badany zbiór ograniczen zawiera
punkty dopuszczalne.
Takie podejscie do problemu oraz sposób znajdowania rozwiazan dopuszczalnych zostanie przedstawiony w referacie.
Referat opracowano na podstawie pracy: D.Bertsimas, G.Perakis,
S.Tayur, A new algebraic geometry algorithm for integer
programming Management Science 46(2000) 999-1008.
|
|