NP-obtížné úlohy v operačním výzkumu

Poskytovatel

Grantová agentura České republiky

Program

Standardní projekty

Veřejná soutěž

Standardní projekty 9 (SGA02006GA-ST)

Hlavní účastníci

—

Druh soutěže

VS - Veřejná soutěž

Číslo smlouvy

402/06/0123

Název projektu anglicky

NP-Hard Problems in Operations Research

Anotace anglicky

Operations research deals with the modeling and solving practical problems consisting in finding an optimal economic decision. Since many of these problems are NP-hard, the computational complexity and time requirements are enormous barriers for using methods of operations research. Optimization models of linear integer programming are used for solution of such models. Proposed project is aimed at the problems of industrial scheduling, production batch processing and logistical problems. The main focusis placed on the investigation of tools, which enable to solve the practical midsized applications in acceptable computational time. The branch-and-bound method will be used together with its extensions: branch-and-price and branch-and-cut algorithms. Inaddition, we will take the advantage of tools increasing the computational efficiency as the preprocessing, tightening constraints and column generation using powerful optimization software. The primary issue is the NP-hard problems as the

Kategorie VaV

ZV - Základní výzkum

CEP - hlavní obor

BB - Aplikovaná statistika, operační výzkum

CEP - vedlejší obor

AH - Ekonomie

CEP - další vedlejší obor

—

OECD FORD - odpovídající obory <br>(dle <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">převodníku</a>)

10103 - Statistics and probability<br>50201 - Economic Theory<br>50202 - Applied Economics, Econometrics<br>50203 - Industrial relations<br>50204 - Business and management<br>50205 - Accounting<br>50206 - Finance

Hodnocení poskytovatelem

U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)

Zhodnocení výsledků projektu

Grantový projekt byl zaměřen na úlohy operačního výzkumu patřící do třídy NP obtížných úloh.Nástrojem řešení byl optimalizační model s diskrétními proměnnými a heuristické metody. U všech navržených modelů a heuristik byla provedena řada číselných experi

Zahájení řešení

1. 1. 2006

Ukončení řešení

31. 12. 2008

Poslední stav řešení

U - Ukončený projekt

Poslední uvolnění podpory

25. 4. 2008

Důvěrnost údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Systémové označení dodávky dat

CEP09-GA0-GA-U/02:2

Datum dodání záznamu

22. 10. 2009

Celkové uznané náklady

1 140 tis. Kč

Výše podpory ze státního rozpočtu

1 140 tis. Kč

Ostatní veřejné zdroje financování

0 tis. Kč

Neveřejné tuz. a zahr. zdroje finan.

0 tis. Kč