NP-Hard Problems in Operations Research
Project goals
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
Keywords
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
—
10103 - Statistics and probability
50201 - Economic Theory
50202 - Applied Economics, Econometrics
50203 - Industrial relations
50204 - Business and management
50205 - Accounting
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
Recognised costs
1 140 CZK thou.
Public support
1 140 CZK thou.
0%
Provider
Czech Science Foundation
CEP
BB - Applied statistics, operational research
Solution period
01. 01. 2006 - 31. 12. 2008