Cjelobrojno i
kombinatorno optimiziranje
| |
Smjer: |
Teorijska kompjuterska nauka, Primjenjena matematika |
| |
Semestar: |
VIII |
| |
Tip kursa: |
Izborni |
| |
Fond sati: |
2+1+1 |
| |
Broj
ECTS kredita: |
7 |
Nastavni program:
- Teorija i algoritmi
cjelobrojnog programiranja: Formulacija; Geometrijska predstava;
Jednomodularnost (jednoekstremalnost), Dualnost u linearnom programiranju;
-
Algoritmi cjelobrojnog programiranja:
Gomory-jev algoritam presjecajućih ravni; Branch-and-bound algoritam;
-
Aproksimativne i heurističke metode
pretraživanja;
- Mješovito i
kombinatorno linearno programiranje; Problem ranca tipa 0-1;
-
Egzaktni algoritmi za NP-hard probleme:
Dinamičko programiranje; Redukcija broja stanja; Ograničenja;
Branch-and-bound algoritmi; Branch-and-cut algoritmi; Branch-and-price
algoritmi;
-
Branch-and-bound algoritmi: Šema grananja
(branching); Popuštanja: neprekidnost, lagranžijan, surogat; Primjena na
višestruki problem ranca; Procedura redukcije;
- Aproksimativni
algoritmi: Eksperimenalna analiza; Vjerovatnost; Najgori slučaj; Heuristički
i metaheuristički algoritmi;
- Primjene razmotrenih
tehnika na Travelling Salesman probleme;
-
Korištenje softverskih alata za rješavanje
problema cjelobrojnog i mješovitog linearnog programiranja;
Literatura:
-
Donald A. Pierre: Optimization Theory
with Application, Dover Publications, Inc.
-
Charles S. Beightler, Don T. Phillips,
Douglass J. Wile: Foundations of Optimization, Prentice Hall
-
P. Toth, Discreet D. Vigo (edited by):
The Vehicle Routing Problem, SIAM Monographs on Mathematics and
Applications, 2002
-
S. Hammer, P. Toth; Knapsack Problems:
Algorithms and Computer Implementations, J. Wiley, 1990
-
G. Gutin, To Punnen (edited by): The
Traveling Salesman Problem and its Variations, Kluwer 2002
-
C. Papadimitriou, K. Steiglitz:
Combinatorial Optimization, Prentice Hall, 1982
-
S. Martello, P. Toth: Knapsack Problems:
Algorithms and Computer Implementations, Wiley, 1990