NP-Hard Problems in Operations Research
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 9 (SGA02006GA-ST)
Main participants
—
Contest type
VS - Public tender
Contract ID
402/06/0123
Alternative language
Project name in Czech
NP-obtížné úlohy v operačním výzkumu
Annotation in Czech
Operační výzkum se zabývá modelováním a řešením úloh z praxe spočívajícím v hledání optimálního ekonomického rozhodnutí. Řada těchto úloh je NP obtížná a proto jejich výpočetní složitost je v praxi velkou překážkou pro řešení těchto problémů metodami operačního výzkumu pro vysoké nároky na výpočetní čas. Řeší se pomocí optimalizačních modelů, které představují úlohy lineárního celočíselného programování. Navrhovaný projekt je zaměřen na problémy průmyslového rozvrhování, zpracování výrobních dávek a logistické úlohy. Soustředí se na hledání prostředků, které umožní řešit tyto úlohy v přijatelném výpočetním čase pro úlohy střední velikosti, které se vyskytují v praktických aplikacích. Bude využita zejména metoda větvení a hranic a její další formy: metoda větvení a oceňování, metoda větvení a řezů s využitím nástrojů zvyšující efektivitu výpočtu, jako jsou metody preprocesingu, metody zesilování omezení, generování řezů spojené s využitím výkonného software pro řešení matematických modelů těchto
Scientific branches
R&D category
ZV - Basic research
CEP classification - main branch
BB - Applied statistics, operational research
CEP - secondary branch
AH - Economics
CEP - another secondary branch
—
OECD FORD - equivalent branches <br>(according to the <a href="http://www.vyzkum.cz/storage/att/E6EF7938F0E854BAE520AC119FB22E8D/Prevodnik_oboru_Frascati.pdf">converter</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
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project was aimed at the problems of operational research which belong to the class of NP-hard problems. As the solving tool the optimization model with discrete variables and heuristic methods were used. Many computer experiments were realized for a
Solution timeline
Realization period - beginning
Jan 1, 2006
Realization period - end
Dec 31, 2008
Project status
U - Finished project
Latest support payment
Apr 25, 2008
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP09-GA0-GA-U/02:2
Data delivery date
Oct 22, 2009
Finance
Total approved costs
1,140 thou. CZK
Public financial support
1,140 thou. CZK
Other public sources
0 thou. CZK
Non public and foreign sources
0 thou. CZK