×

Stochastic nuclear outages semidefinite relaxations. (English) Zbl 1273.90133

Summary: This paper deals with stochastic scheduling of nuclear power plant outages. Focusing on the main constraints of the problem, we propose a stochastic formulation with a discrete distribution for random variables, that leads to a mixed 0/1 quadratically constrained quadratic program. Then we investigate semidefinite relaxations for solving this hard problem. Numerical results on several instances of the problem show the efficiency of this approach, i.e., the gap between the optimal solution and the continuous relaxation is on average equal to 53.35 % whereas the semidefinite relaxation yields an average gap of 2.76 %. A feasible solution is then obtained with a randomized rounding procedure.

MSC:

90C15 Stochastic programming
90C31 Sensitivity, stability, parametric optimization
90C09 Boolean programming

Software:

COL; CSDP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adasme P, Lisser A, Soto I (2012) A quadratic semidefinite relaxation approach for OFDMA resource allocation. Networks 59(1): 3–12 · Zbl 1242.90150 · doi:10.1002/net.20475
[2] Benson SJ, Ye Y, Zhang X (2000) Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J Optim 10: 443–461 · Zbl 0997.90059 · doi:10.1137/S1052623497328008
[3] Borchers B (1999) CSDP, a C library for semidefinite programming. Optim Methods Softw 11: 613–623 · Zbl 0973.90524 · doi:10.1080/10556789908805765
[4] Boyd S, Vandenberghe L (1996) Semidefinite programming. SIAM Rev 38: 49–95 · Zbl 0845.65023 · doi:10.1137/1038003
[5] Calafiore G, Campi MC (2004) Decision making in an uncertain environment: the scenario-based optimization approach. In: Andrysek J, Karny M Kracik J (eds) Multiple participant decision making. Advanced Knowledge International, pp 99–111
[6] Fortet R (1960) Applications de l’algebre de boole en recherche opérationnelle. Revue Francaise de Recherche Operationnelle 4: 17–26
[7] Fourcade F, Eve T, Socroun T (1997) Improving Lagrangian relaxation: an application to the scheduling of pressurized water reactor outages. IEEE Trans Power Syst 12(2): 919–925 · doi:10.1109/59.589770
[8] Fourcade F, Johnson E, Bara M, Cortey-Dumont P (1997) Optimizing nuclear power plant refueling with mixed-integer programming. Eur J Oper Res 97: 269–280 · Zbl 0930.90063 · doi:10.1016/S0377-2217(96)00197-X
[9] Gaivoronski A, Lisser A, Lopez R (2011) Knapsack problem with probability constraints. J Glob Optim 49(3): 397–413 · Zbl 1213.90213 · doi:10.1007/s10898-010-9566-0
[10] Goemans MX (1998) Semidefinite programming and combinatorial optimization. Documenta Mathematica Extra Volume ICM 1998 3: 657–666 · Zbl 0904.90129
[11] Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 1115–1145 · Zbl 0885.68088
[12] Gorge A, Lisser A, Zorgati R (2012) Semidefinite Relaxations for the scheduling nuclear outages problem. In: Accepted in the 1st international conference on operations research and enterprise systems (ICORES) proceedings · Zbl 1273.90133
[13] Helmberg C, Rendl F (2000) A spectral bundle method for semidefinite programming. SIAM J Optim 10: 673–696 · Zbl 0960.65074 · doi:10.1137/S1052623497328987
[14] Henrion R (2004) Introduction to chance constraint programming. Tutorial paper for the stochastic programming community HomePage. http://www.wias-berlin.de/people/henrion/publikat.html
[15] Helmberg C, Rendl F (1998) Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math Program 82: 291–315 · Zbl 0919.90112
[16] Khemmoudj MOI, Porcheron M, Bennaceur H (2006) When constraint programming and local search solve the scheduling problem of electricité de France nuclear power plant outages. In: 12th international conference on principles and practice of constraint programming (CP), Springer LNCS 4204, Nantes, France, pp 271–283
[17] Kosuch S, Lisser A (2011) On two-stage stochastic knapsack problems with or without probability constraint. Discrete Appl Math 159(16): 1827–1841 · Zbl 1250.90061 · doi:10.1016/j.dam.2010.04.006
[18] Laurent M, Rendl F (2005) Semidefinite programming and integer programming. In: Aardal K, Nemhauser G, Weismantel R (eds) Handbook on discrete optimization. Elsevier, Amsterdam, pp 393–514 · Zbl 1194.90066
[19] Lisser A, Lopez R (2010) Application of semidefinite relaxation and VNS for multiuser detection in synchronous CDMA. Networks 5: 187–193 · Zbl 1200.90040
[20] Lovász L (1979) On the Shannon capacity of a graph. IEEE Trans Inf Theory 25: 1–7 · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985
[21] Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0-1 optimization. SIAM J Optim 1: 166–190 · Zbl 0754.90039 · doi:10.1137/0801013
[22] Nemirovski A, Shapiro A (2004) Scenario approximations of chance constraints. In: Calafiore, Campi (eds) Probabilistic and randomized methods for design under uncertainty, vol 45. Springer, London, http://www.optimization-online.org
[23] Nesterov Y, Nemirovski A (1994) Interior point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics, Philadelphia · Zbl 0824.90112
[24] Porcheron M, Gorge A, Juan O, Simovic T, Dereu G (2009) Challenge ROADEF/EURO 2010: a large-scale energy management problem with varied constraints. EDF R&D report. http://challenge.roadef.org
[25] Prekopa A (1995) Stochastic programming. Kluwer, Dordrecht, p 34 · Zbl 0447.90070
[26] Todd MJ (2001) Semidefinite optimization. Acta Numer 10: 515–560 · Zbl 1105.65334
[27] Wolkowicz H, Saigal R, Vandenberghe L (2000) Handbook of semidefinite programming: theory, algorithms and applications. Kluwer Academic Publishers, Dordrecht, The Netherlands · Zbl 0962.90001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.