Solution and applications of nonconvex and discrete stochastic programming problems  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
47340
Type K
Principal investigator Deák, István
Title in Hungarian Nemkonvex és diszkrét sztochasztikus programozási feladatok megoldása és alkalmazása
Title in English Solution and applications of nonconvex and discrete stochastic programming problems
Panel Mathematics and Computing Science
Department or equivalent Department of Differential Equations (Budapest University of Technology and Economics)
Participants Bukszár, József
Fábián, Csaba
Hujter, Mihály
Mádi-Nagy, Gergely
Prékopa, András
Szántai, Tamás
Starting date 2004-01-01
Closing date 2008-06-30
Funding (in million HUF) 13.262
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
A nemkonvex feladatok megoldására három területen is lényeges haladást értünk el: a valószínűségek kiszámítása, általános sztochasztikus feladatok optimalizálásában és a diszkrét sztochasztikus programozási feladatok megoldásában. A normális valószínűségek kiszámítására használt számítógépes szubrutinok olyan gyors működését értük el, hogy normális eloszlás esetén még 1000 dimenziós egyszerű konvex alakzatok valószínűségét is meg lehet határozni egy másodperc körüli időben. A poliéderek használatán alapuló módszer egy új elvi alapokat felhasználó eljárás valószínűségek kiszámítására. Ezen kívül a Dirichlet és a gamma eloszlás valószínűségeinek kiszámításában sikerült eredményeket elérni. Sztochasztikus feladatok megoldó algoritmusaira négy új eljárást dolgoztunk ki: a megengedett megoldások halmazának közelitésén (Bukszár), a szukcesszív regressziós approximációk véletlen egyenletrendszerekre való alkalmazása (Deák), metszősík algoritmusokat használó algoritmus (Fábián), a valószínűségi korláton belül tetszőleges helyen véletlent tartalmazó modell megoldása (Vizvári). A többdimenziós momentumproblémák megoldására kifejlesztett eljárásokat hasznossági függvény becslésére alkalmaztuk.
Results in English
In our research for solving nonconvex problems we achieved progress in three areas: computing probabilities, optimizing general stochastic programming problems and discrete programming problems. The computer subroutines determining multinormal probabilities became so fast, that even for 1000 dimensional simple convex sets we were able to compute probabilities in about 1 sec. Employing polyhedra is a theoretically new path in computing probabilities. Also we developed some algorithms for computing probabilities for the Dirichlet and the gamma distribution. Four new procedures have been developed fo optimizing stochastic programming models: approximating the set of feasible solutions (Bukszár), applying the successive regression approximations for solving random linear systems of equations (Deák), cutting plane techniques (Fábián), solving problems where the random variables may be in any place inside the probabilistic constraint (Vizvari. In the multidimensional discrete moment problems we proved some theorems, and using these results new algorithm could be presented for approximating the expected utility function.
Full text http://real.mtak.hu/1755/
Decision
Yes





 

List of publications

  
Gouda, A.A., Szántai, T., Monhor, D.: Stochastic programming based PERT modelling, IFIP/IIASA/GAMM Workshop on Coping with Uncertainty, 241-255., 2006
Fábián, Cs.: Decomposing CVaR minimization in two-stage stochastic model, RUTCOR Research Reports, 32-2005, 2005
Deák, I.:: Testing successive regression approximations by large-scale two-stage problems, Ann. Operations Research, Tucson, AZ, to appear, 2008
Mádi-Nagy, G.: A method to find the best bounds in a multivariate discrete moment problem if the basis structure is given, Studia Scientiarum Mathematicarum Hungarica, 42, pp. 207-226., 2005
Bukszár, J., Henrion, R., Hujter M., Szántai, T.:: Polyhedral Inclusion-Exclusion, Weierstrass Institute Berlin, Preprint No. 913, 2004. at: http://www.wias-berlin.de/publications/preprints/913/., 2004
Bukszár, J., Henrion, R., Hujter M., Szántai, T.:: Polyhedral Inclusion-Exclusion, SPEPS (Stochastic Programming E-Print Seriers), 2004-17, at: http://hera.rz.hu-berlin.de/speps/., 2004
Deák, I.:: A sztochasztikus programozás Monte Carlo módszereiről, MTA doktori értekezés, p. 178., 2004
Deák, I.:: Two-stage stochastic problems with correlated normal variables: computational experiences, Annals of Operations Research (2006) 142: 79-97., 2006
Gouda, A.A., Szántai, T.:: New sampling techniques for calculation of Dirichlet probabilities,, CEJOR 12 December 389-403, 2004
Gouda, A.A., Szántai, T.:: Estimation of rare event probabilities in stochastic networks with exponential and beta distributions,, RESIM 2004 Budapest, Rare Event Simulation and Combinatorial Optimization., 2004
Gouda, A.A., Szántai, T.:: A PERT egy új, sztochasztikus programozási modellje., Alkalmazott Matematikai Lapok 22, 95-111., 2005
Hujter, M.:: Matrix inverses, rigid circuit graphs, Fibonacci heaps, homotopies, polyhedra, and probability bounding,, Talk presented at the Veszprém Optimization Conference: Advanced Algorithms (VOCAL), December 13-15, 2004, Veszprém, Hungary; at: http://www.math.bme.hu/~hujter/vocal.pdf., 2004
Mádi-Nagy, G., Prékopa, A.:: On Multivariate Discrete Moment Problems and their Applications to Bounding Expectations and Probabilities,, Mathematics of Operations Research 29 (2), pp. 229-258., 2004
Mádi-Nagy, G., Prékopa, A.:: Egy többváltozós hasznossági függvény,, Alkalmazott Matematikai Lapok 21, 23-34., 2004
Gouda, A.A., Szántai, T.:: Estimation of rare events in stochastic networks (elfogadva), Mathematical and Computer Modeling, 2005
Fábián, Cs.: Decomposing CVaR minimization in two-stage stochastic programming models, Stochastic Programming E-Print Series 20, 1-14., 2006
Prékopa, A., G. Mádi-Nagy: A Class of Multiattribute Utility Functions, Economic Theory, 34(3) 591-602., 2008
Mádi-Nagy G: .: Az egyváltozós diszkrét momentum probléma módszereinek alkalmazása többváltozós esetre, XXVI. Operációkutatási Konferencia előadáskivonatai, 18. old. Győr., 2004
Prékopa, A., G. Mádi-Nagy: A Class of Multivariate Strong Utility Functions, 17th EURO mini Conference: Continuous Optimization in Industry, Pécs., 2005
Mádi-Nagy, G. , Prékopa, A.: Bounding expectations of functions of random vectors with given marginals and some moments: Applications of the multivariate discrete moment problem, Rutcor Research Report 11-2007., 2007
Mádi-Nagy, G.: On Multivariate Discrete Moment Problems: Generalization of the bivariate Min algorithm for higher dimensions, RUTCOR Research Report 13-2007, 2007
Fábián, C.I., Szőke, Z.: Solving two-stage stochastic programming problems with level decomposition, Computational Management Science 4, 323-353., 2007
Fábián, C.I.: Handling CVaR objectives and constraints in two-stage stochastic programming models, European Journal of Operational Research, sajtó alatt., 2008
Fábián, C.I., Veszprémi, A.: Algorithms for handling CVaR-constraints in dynamic stochastic programming models with applications to finance, The Journal of Risk, 10, 111-131., 2008
Fábián, C.I., Mitra, G., Roman, D.: Processing Second-order Stochastic Dominance models using cutting-plane representations, Technical Report 75, CARISMA, Brunel University, 2008
Hujter, M.:: Egy-két érdekes azonosságról, Haladvány Kiadvány, 2007
Hujter, M.:: Egy maximumkeresési feladat, Haladvány Kiadvány, 2007
Hujter, M.:: Ötödik háromszög, hatodik négyszög, Haladvány Kiadvány, 2007
Hujter, M.:: Százhuszonhárom éves, Haladvány Kiadvány, 2007
Deák, I.:: No degradation of efficiency in very high dimensional Monta Carlo computations, Proc. 23rd IFIP TC7 Conference on System Modelling and Optimization, Cracow, Poland, 368-369., 2007
Deák, I., Cser, L.: Random linear problems in manufactoring, Proc. Conference on Cooperative Manufacturing, COMA'07, Stellenbosch, South Africa, pp. 259-262., 2007
Deák, I.:: Applications of successive regression approximations in stochastic programming, Proc. 20th Euro Mini Conference "Continuous Optimization and Knowledge-based technologies", eds. L. Sakalauskas, G.W. Weber, E.K. Zavadskas, pp. 480-484., 2008
Deák, I., Pólik, I., Prékopa, A., Terlaky, T.: Semidefinite approximations in stochastic programming, Research Paper, McMaster University, Canada, 2008
Vizvári, B., Lakner, Z., Kovács, G., Csizmadia, Zs.: A stochastic programming and simulation based analysis of the structure of the production on the arable land in Hungary, RUTCOR, Rutgers University Research Report, RRR 16-2006, 2006
Vizvári, B., Kovács, G., Csizmadia, Zs.: A stochastic programming and simulation based analysis of the field use in a farm, RUTCOR, Rutgers University Research Report, RRR 20-2007, 2007
Szántai, T., Kovács, E.: On the approximation of a multivariate distribution using certain clustering approachn, In: Lecture Notes in Economics and Mathematical Systems, 581, Proc. of the IFIP/IIASA/GAMM-Workshop on ''Coping, 2007
Gouda, A.A., Szántai, T.:: Sztochasztikus hálózatokkal kapcsolatos, ritkán bekövetkező események valószínűségbecslése exponenciális és béta eloszlás esetén, Alkalmazott Matematikai Lapok 22, 95-111., 2007
Gouda, A.A., Szántai, T.:: Rare event probabilities in stochastic networks, Central European Journal of Operations Research, 2007
Gouda, A.A., Szántai, T.:: On numerical calculation of probabilities according to Dirichlet distribution, Annals of Operations Research, 2008
Gouda, A.A., Szántai, T.:: New sampling techniques in variance reduction Monte Carlo simulation algorithms for calculation of Dirichlet probabilities, Central European Journal of Operations Research, 12 389-403, 2004
Szántai, T.: PERT alkalmazások, Budapesti Corvinus Egyetem,, 2004
Prékopa, A., Long, J., Szántai, T.: New bounds and approcimations for the probability distribution of the length of the critical path, Lecture Notes in Economics and Mathematical Systems, 532, Dynamic Stochastic Optimization, Springer 532, 293-305, 2004
Kéri, G., Szántai, T.: Egy konstruktívan definiált többdimenziós gamma eloszlás illeszthetőségének feltételeiről, Alkalmazott Matematikai Lapok sajtó alatt, 2007
Szántai, T.: Valószínűségi becslések és alkalmazásaik, MTA Doktora disszertáció, 2003, 2005
Bodó, I., Gézsi, A., Deák, I.: VWF is cleared from the circulation with second order kinetics, Journal of Thrombosis and Haemostasis, leadva, 2008
Lakner, Z., Vizvári, B.,: Application of decision support methods in preparation for a Hungarian bio-fuel programme, Gazdálkodás, 52 (2008) 17-31., 2008



Back »