BFC, A branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0-1 programs
| dc.contributor.author | Ortuño Sánchez, María Teresa | |
| dc.contributor.author | Alonso Ayuso, Antonio | |
| dc.contributor.author | Escudero Bueno, Laureano Fernando | |
| dc.date.accessioned | 2023-06-20T09:43:14Z | |
| dc.date.available | 2023-06-20T09:43:14Z | |
| dc.date.issued | 2003-12-16 | |
| dc.description.abstract | We present a framework for solving some types of 0-1 multi-stage scheduling/planning problems under uncertainty in the objective function coefficients and the right-hand-side. A scenario analysis scheme with full recourse is used. The solution offered for each scenario group at each stage takes into account all scenarios but without subordinating to any of them. The constraints are modelled by a splitting variables representation via scenarios. So, a 0-1 model for each scenario is considered plus the non-anticipativity constraints that equate the 0-1 variables from the same group of scenarios in each stage. The mathematical representation of the model is very amenable for the proposed framework to deal with the 0-1 character of the variables. A branch-and-fix coordination approach is introduced for coordinating the selection of the branching nodes and branching variables in the scenario subproblems to be jointly optimized. Some computational experience is reported for different types of problems. | en |
| dc.description.department | Depto. de Estadística e Investigación Operativa | |
| dc.description.faculty | Fac. de Ciencias Matemáticas | |
| dc.description.faculty | Instituto de Matemática Interdisciplinar (IMI) | |
| dc.description.refereed | TRUE | |
| dc.description.sponsorship | Comisión Interministerial de Ciencia y Tecnología (España) | |
| dc.description.sponsorship | Comunidad de Madrid | |
| dc.description.status | pub | |
| dc.eprint.id | https://eprints.ucm.es/id/eprint/17501 | |
| dc.identifier.citation | Alonso-Ayuso, Antonio, Laureano F. Escudero, y M. Teresa Ortuño. «BFC, A Branch-and-Fix Coordination Algorithmic Framework for Solving Some Types of Stochastic Pure and Mixed 0–1 Programs». European Journal of Operational Research 151, n.o 3 (diciembre de 2003): 503-19. https://doi.org/10.1016/S0377-2217(02)00628-8. | |
| dc.identifier.doi | 10.1016/S0377-2217(02)00628-8 | |
| dc.identifier.issn | 0377-2217 | |
| dc.identifier.officialurl | https//doi.org/10.1016/S0377-2217(02)00628-8 | |
| dc.identifier.relatedurl | http://www.sciencedirect.com/science/article/pii/S0377221702006288 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.14352/50244 | |
| dc.issue.number | 3 | |
| dc.journal.title | European journal of operational research | |
| dc.language.iso | eng | |
| dc.page.final | 519 | |
| dc.page.initial | 503 | |
| dc.publisher | Elsevier Science | |
| dc.relation.projectID | TIC2000-1750-C06-04/05 | |
| dc.relation.projectID | 07T/0005/2001 | |
| dc.rights.accessRights | restricted access | |
| dc.subject.cdu | 519.8 | |
| dc.subject.keyword | Stochastic programming | |
| dc.subject.keyword | Multistage scenario tree | |
| dc.subject.keyword | Mixed 0-1 programs | |
| dc.subject.keyword | Splitting variables representation | |
| dc.subject.keyword | Twin node families | |
| dc.subject.keyword | Flow management problem | |
| dc.subject.keyword | Integer recourse | |
| dc.subject.keyword | Decomposition | |
| dc.subject.ucm | Investigación operativa (Matemáticas) | |
| dc.subject.unesco | 1207 Investigación Operativa | |
| dc.title | BFC, A branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0-1 programs | en |
| dc.type | journal article | |
| dc.volume.number | 151 | |
| dcterms.references | Ahmed, S., King, A.J., Parija, G., 2000. A multi-stage stochastic integer programming approach for capacity expansion under uncertainty. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA. Alonso-Ayuso, A., 1997. Optimización combinatoria estocástica (aplicada al control del tráfico aéreo), Ph.D. Thesis, Universidad Complutense de Madrid, Madrid. Alonso-Ayuso, A., Escudero, L.F., Ortuño, M.T., 2000. A stochastic 0–1 program based approach for air traffic management. European Journal of Operational Research 120, 47–62. Alonso-Ayuso, A., Escudero, L.F., Garín, A., Ortuño, M.T., Pérez, G., 2002. An approach for strategic supply chain planning under uncertainty based on stochastic 0–1 programming. Journal of Global Optimization. Applegate, D., Bixby, R.E., Chvatal, V., Cock, W.J., 1997. A BCC TSP, 16th International Symposium on Mathematical Programming, Lausanne, Switzerland. Atamtürk, A., Nemhauser, G.L, Savelsbergh, M.W.P., 2000. Conflict graphs in solving integer programming problems. European Journal of Operational Research 121, 40–55. Beale, E.M.L., 1955. On minimizing a convex function subject to linear inequalities. Journal of Royal Statistical Society 17b, 173–184. Benders, J.F., 1962. Partitioning procedures for solving mixed variables programming problems. Numeische Mathematik 4, 238–252. Bertsimas, D.J., Stock, S., 1998. Air traffic flow management problem with enroute capacities. Operations Research 46, 406–422 (Made available as a MIT report in 1994). Birge, J., Louveaux, F.V., 1997. Introduction to Stochastic Programming. Springer, Berlin. Caroe, C.C., Schultz, R., 1998. A two-stage stochastic program for unit commitment under uncertainty in a hydro power systems, SC 98-13, Konrad-Zuse-Zentrum f€ur Informationstechnik Berlin (ZIB), Berlin. Caroe, C.C., Schultz, R., 1999. Dual decomposition in stochastic integer programming. Operational Research Letters 24, 37–45 (Made available as a ZIB report in 1996). Caroe, C.C., Tind, J., 1998. L-shaped decomposition of twostage stochastic programs with integer recource. Mathematical Programming 83, 451–464. Dantzig, G.B., 1955. Linear programming under uncertainty. Management Science 1, 197–206. Escudero, L.F., de la Fuente, J.L., Garc_ıa, C., Prieto, F.J., 1999a. A parallel computation approach for solving multistage stochastic network problems. Annals of Operations Research 90, 131–160. Escudero, L.F., Galindo, E., G_omez, E., Garc_ıa, G., Sabau, V., 1999b. SCHUMANN, a modelling framework for supply chain management under uncertainty. European Journal of Operational Research 119, 13–34. Guignard, M., Spielberg, K., 1981. Logical reduction methods in zero-one programming (minimal preferred variables). Operations Research 29, 49–74. Higle, J.L., Sen, S., 1996. Stochastic decomposition. A statistical method for large-scale stochastic linear programming. Kluwer Academic Publishers, Boston. Hemmecke, R., Schultz, R., 2001. Decomposition methods for two-stage stochastic integer programs. In: Grötschel, M., Krumke, S.O., Rambau, J. (Eds.), Online Optimization of Large Scale Systems. Springer, Berlin, pp. 601–622. Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W.P., 2000. Progress in linear programming-based algorithms for integer programming: An exposition. INFORMS Journal of Computing 12, 2–23. Kall, P., Wallace, S.W., 1994. Stochastic Programming. J. Wiley & Sons, New York. Klein Haneveld, W.K., Van der Vlerk, M.H., 1999. Stochastic integer programming: General models and algorithms. Annals of Operations Research 85, 39–57. Laporte, G., Louveaux, F.V., 1993. The integer L-shaped method for stochastic integer programs with complete recourse. Operations Research Letters 13, 133–142. Linderoth, J., Savelsbergh, M.W.P., 1999. Search strategies for mixed integer programming. INFORMS Journal of Computing 11, 173–187. Lokketangen, A., Woodruff, D.L., 1996. Progressive hedging and tabu search applied to mixed integer (0,1) multi-stage stochastic programming. Journal of Heuristics 2, 111–128. Mulvey, J.M., Vanderbei, R.J., Zenios, S.A., 1995. Robust optimisation of large-scale systems: General modeling framework and computations. Operations Research 43, 244–281. Rockafellar, R.T., Wets, R.J.-B., 1991. Scenario and policy aggregation in optimisation under uncertainty. Mathematics of Operations Research 16, 119–147. Römisch, W., Schultz, R., 2001. Multi-stage stochastic integer programs: An introduction, In: Grötschel, M.,Krumke, S.O., Rambau, J., (Eds.), Online Optimization of Large Scale Systems. Springer, Berlin, pp. 581–600 Savelsbergh, M.W.P., 1994. Preprocessing and probing techniques for mixed integer programming models. ORSA Journal of Computing 6, 445. Schultz, R., Stougie, L., Van der Vlerk, M.H., 1998. Solving stochastic programs with integer recourse by enumeration: A framework using Gr€obner basis reductions. Mathematical Programming 83, 229–252. Stougie, L., Van der Vlerk, M.H., 1997. Stochastic Integer Programming. In: Dell_Amico, M., Maffioli, F., Martello, S. (Eds.), Annotated Bibliography in Combinatorial Optimization. John Wiley, NY, pp. 127–141. Takriti, S., Birge, J.R., 2000. Lagrangean solution techniques and bounds for loosely coupled mixed-integer stochastic programs. Operations Research 48, 91–98. Van der Vlerk, M.H., 1995. Stochastic Programming with Integer Recourse, Ph.D. Thesis, Institute of Economics, University of Groningen, The Netherlands. Van Slyke, R., Wets, R.J.-B., 1969. L-shaped linear programs with applications to optimal control and stochastic programming. SIAM Journal on Applied Mathematics 17, 638– 663. Wets, R.J.-B., 1989. The aggregation principle in scenario analysis and stochastic optimisation. In: Wallace, S.W. (Ed.), Algorithms and model formulations in Mathematical Programming. Springer, Berlin, pp. 92–113. | |
| dspace.entity.type | Publication | |
| relation.isAuthorOfPublication | 6f9ad449-8cec-4e55-aca2-7dedcde6b101 | |
| relation.isAuthorOfPublication | 8f791af6-0fef-4e4a-92bf-85ea2e321e00 | |
| relation.isAuthorOfPublication | 1896c3b5-d17b-4208-9fc4-3ed788be31ae | |
| relation.isAuthorOfPublication.latestForDiscovery | 6f9ad449-8cec-4e55-aca2-7dedcde6b101 |
Download
Original bundle
1 - 1 of 1