Abstract
An algorithm for solving quadratic, two-stage stochastic problems is developed. The algorithm is based on the framework of the Branch and Fix Coordination (BFC) method. These problems have continuous and binary variables in the first stage and only continuous variables in the second one. The objective function is quadratic and the constraints are linear. The nonanticipativity constraints are fulfilled by means of the twin node family strategy. On the basis of the BFC method for two-stage stochastic linear problems with binary variables in the first stage, an algorithm to solve these stochastic quadratic problems is designed. In order to gain computational efficiency, we use scenario clusters and propose to use either outer linear approximations or (if possible) perspective cuts. This algorithm is implemented in C++ with the help of the Cplex library to solve the quadratic subproblems. Numerical results are reported.
Chapter PDF
Similar content being viewed by others
Keywords
References
Alonso-Ayuso, A., Escudero, L.F., Ortuño, M.T.: BFC, a branch-and-fix coordination algorithm framework for solving some types of stochasticpure and mixed 0-1 programs. European Journal of Operational Research 151, 503–519 (2003)
Corchero, C., Mijangos, E., Heredia, F.J.: A new optimal electricity market bid model solved through perspective cuts. Top (2012), doi:10.1007/s11750-011-0240-6 (published online 2011)
Escudero, L.F., GarÃn, M., Merino, M., Pérez, G.: A general algorithm for solving two-stage stochastic mixed 0-1 first-stage problems. Computers & Operations Research 36, 2590–2600 (2009)
Escudero, L.F., GarÃn, M., Merino, M., Pérez, G.: An algorithmic framework for solving large-scale multistage stochastic mixed 0-1 problems with nonsymmetric scenario trees. Computers & Operations Research 39(5), 1133–1144 (2012)
Frangioni, A., Gentile, C.: Perspective cuts for a class of convex 0-1 mixed integer programs. Mathematical Programming 106, 225–236 (2006)
Heredia, F.J., Corchero, C., Mijangos, E.: Solving Electricity Market Quadratic Problems by Branch and Fix Coordination Methods. In: Hömberg, D., Tröltzsch, F. (eds.) CSMO 2011. IFIP AICT, vol. 391, pp. 516–525. Springer, Heidelberg (2013)
Laporte, G., Louveaux, F.: An integer L-shaped algorithm for the capacited vehicle routing problem with stochastic demands. Operations Research 50, 415–423 (2002)
Sen, S., Sherali, H.: Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming. Mathematical Programming Series A 105, 203–223 (2006)
Sherali, H.D., Fraticelli, B.M.P.: A modification of Bender’s decomposition algorithm for discrete subproblems: an approach for stochastic programs with integer recourse. Journal of Global Optimization 22, 319–342 (2002)
Wets, R.J.-B.: Programming under uncertainty: the equivalent convex program. SIAM Journal on Applied Mathematics 14, 89–105 (1966)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 IFIP International Federation for Information Processing
About this paper
Cite this paper
Mijangos, E. (2013). An Algorithm for Two-Stage Stochastic Quadratic Problems. In: Hömberg, D., Tröltzsch, F. (eds) System Modeling and Optimization. CSMO 2011. IFIP Advances in Information and Communication Technology, vol 391. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36062-6_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-36062-6_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36061-9
Online ISBN: 978-3-642-36062-6
eBook Packages: Computer ScienceComputer Science (R0)