Egészértékű programozás

Tartalom

Jelölések 9
I. rész Az egészértékű programozás alapjai 21
1. Bevezetés 23
1.1. Az egészértékű programozás tárgya 13
1.2. Feladatok és modellek 14
1.3. A feladatok osztályozása 22
1.4. Megjegyzések és irodalom 24
2. Az egészértékű programozás matematikai alapjai 25
2.1. A feladatok megoldhatósága 25
2.2. Hilbert-bázisok 36
2.3. Poliéderben fekvő rácspontok konvex burkának bonyolultsága 41
2.4. Sperner-rendszerek 44
2.5. Egyenletekkel definiált diszkrét ponthalmazok 49
2.6. Egyenlőtlenségekkel definiált bináris ponthalmazok 54
2.7. Egyetlen egyenlőtlenséggel jellemzett bináris ponthalmazok 68
2.8. Bináris fák 82
2.9. Megjegyzések és irodalom 87
3. Két alapvető elv 91
3.1. A relaxációs elv 91
3.2. Az egészértékű programozási feladatok egy gráfelméleti modellje 92

II. rész A matematikai programozás általános módszereinek alkalmazása az egészértékű programozásban 101
4. Vágás típusú módszerek 105
4.1. A Gomory-módszer 106
4.2. Egyéb Gomory-vágások 117
4.3. Általános vágások 124
4.4. Egy konvex vágás 127
4.5. Megjegyzések és irodalom 131
5. Dinamikus programozás 133
5.1. A Bellman-elv 133
5.2. Gráfban legrövidebb utat kereső algoritmusok 135
5.3. Lineáris diofantoszi egyenlet megoldhatósága 142
5.4. Felső korlátos változókat tartalmazó hátizsák feladat megoldása 151
5.5. A hátizsák feladat megoldása explicit felső korlátok nélküli feladat esetén 158
5.6. A dinamikus programozás alkalmazása több feltételt tartalmazó feladatok esetén 165
5.7. Megjegyzések és irodalom 167
6. A korlátozás és szétválasztás 169
6.1. A módszer elméleti váza 169
6.2. Korlátos egész változókat tartalmazó feladat megoldása a korlátozás és szétválasztás módszerével 174
6.3. Az adatszerkezet 186
6.4. Megjegyzések és irodalom 190
7. A Balas-féle korlátozás és vágás módszere 193
7.1. Merőleges vetítés és szekvenciális konvexifikáció 193
7.2. Néhány szó a diszjunktív programozásról 199
7.3. Normalizáció 202
7.4. Az algoritmus egy véges változata 204
7.5. A bázis inverzéből kapható vágások 206
7.6. A korlátozás és vágás elve 208
7.7. A vágások felemelése 210
7.8. Megjegyzések és irodalom 212
8. Lagrange-szorzók 215
8.1. A Lagrange-szorzók használata a matematikai programozásban - néhány alapvető eredmény 215
8.2. Módszerek a szorzók megválasztására 220
8.3. Egy további optimalitási kritérium 232
8.4. Egészértékű programozási feladatok méretének redukciója 235
8.5. Dekompozíció Lagrange-szorzók segítségével 239
8.6. Megjegyzések és irodalom 250
9. Lokális keresés - egy általános heurisztikus módszer 251
9.1. A módszer általános váza 251
9.2. A módszer alkalmazása az egészértékű programozásban 253
9.3. A módszer termodinamikai változata, a szimulált lehűlés 257
9.4. A tabukeresés 259
9.5. Megjegyzések és irodalom 259
10. A mohó módszer 261
10.1. A módszer általános alakja 261
10.2. A belső pontos mohó eljárások néhány általános tulajdonsága 266
10.3. A mohó módszer néhány tulajdonsága hátizsák feladat esetén 275
10.4. Megjegyzések és irodalom 290

III. rész Az egészértékű programozás speciális módszerei 293
11. A leszámlálási algoritmus 295
11.1. A leszámlálási algoritmusok alapvető struktúrája 295
11.2. Tesztek a lineáris egészértékű programozási feladat esetében 304
11.3. Az algoritmus részletei a lineáris egészértékű programozási feladat esetén 311
11.4. Megjegyzések és irodalom 320
12. A csoportelméleti módszer 321
12.1. A csoport feladat 321
12.2. A mátrixok Smith-féle normálalakja 323
12.3. A csoportfeladat előállítása a Smith-féle normálforma segítségével 331
12.4. A csoportfeladat megoldása dinamikus programozással 332
12.5. A csoportfeladat optimális megoldásának néhány tulajdonsága 338
12.6. A csoportelméleti módszer beágyazása a korlátozás és szétválasztás algoritmusába 340
12.7. Megjegyzések és irodalom 345
Irodalom 347

Témakörök