在這篇論文中，我們首先回顧了三個在S. Safarina等人(2017) 中提出的錐鬆弛問題：半定規劃(SDP)、線性規劃(LP)及二階錐規劃(SOCP)，目的是為了選擇最佳的基因型，以最大化基因的獲益。然而，我們考慮LP鬆弛問題的魯棒優化，並結合最陡峭上升法，以獲得不確定數據之平等部署(ED)問題的合適解。最後，我們進行了數值實驗，以測試所產生的擾動之可行性。

In this thesis, we first review the three conic relaxation: SDP (Semi-definite programming), LP (Linear programming), and SOCP (Second-order cone programming), proposed in S. Safarina et al.(2017) for the optimum selection of genotypes that maximize genetic gain.
Then, we consider the robust optimization to the LP relaxation and incorporate with a steepest ascent method to acquire an appropriate solution for the equal deployment(ED) problem subject to uncertainty data.
At last, we conduct numerical experiments to test the feasibility incurred by the perturbation.

[1]F. Alizadeh and D. Goldfarb. "Second-order cone programming." Mathematical programming, 95(1):3-51, 2003.
[2]J. Ahlinder, T.J. Mullin, and M. Yamashita. "Using semidefinite programming to optimize unequal deployment of genotypes to a clonal seed orchard." Tree genetics &
genomes, 10(1):27-34, 2014.
[3]L. Bomosssoul and D. Lindgren. "Optimal utilization of clones and genetic thinning of seed orchards." Silvae Genetica, 42:4-5, 1993.
[4]A. Ben-Tal and A. Nemirovski. "Robust solutions to uncertain linear programs." Operations Research Letters, 25,1-13, 1999.
[5]C.C. Cockerham. "Group inbreeding and coancestry." Genetics, 56(1):89-104, 1967.
[6]D. Charlesworth and B. Charlesworth. "Inbreeding depression and its evolutionary consequences." Annual review of ecology and systematics, 18(1):237-268, 1987.
[7]M.A. Duran and I.E. Grossmann. "An outer-approximation algorithm for a class of mixed-integer nonlinear programs." Mathematical programming, 36(3):307-339, 1986.
[8]方述誠, 邢文訓. "線性錐優化/運籌與管理科學叢書". 科學出版社, 111-112, 2013.
[9]M.X. Goemans and D.P. Williamson. "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming." J. Assoc. Comput. Mach., 42(6):1115–1145, 1995.
[10]B. Grundy, B. Villanueva, J.A. Wooliams. "Dynamic selection procedures for constrained inbreeding and their consequences for pedigree development." Genet. Res. 72(2), 159–168 , 1998.
[11]D. Hinrichs, M. Wetten, et al. "An algorithm to compute optimal genetic contributions in selection programs with large numbers of candidates." Journal of animal science, 84(12):3212–3218, 2006.
[12]J. Hallander and P. Waldmann. "Optimum contribution selection in large general tree breeding populations with an application to scots pine." Theoretical and applied genetics, 118(6):1133–1142, 2009.
[13]D. Hinrichs, T.H.E. Meuwissen. "Analyzing the effect of different approaches of penalized relationship in multistage selection schemes." J. Anim. Sci. 89(11), 3426–3432, 2011.
[14]S. Kim and M. Kojima. "Second order cone programming relaxation of nonconvex quadratic optimization problems." Optimization Methods and Software, 15(3-4):201–224, 2001.
[15]D. Lindgren, W.S. Libby, and F.L. Bondesson. "Deployment to plantations of numbers and proportions of clones with special emphasis on maximizing gain at a constant diversity." Theor. Appl. Genet., 77(6):825–831, 1989.
[16]B.L. Miller, "On minimizing nonseparable functions defined on the integers with an investory application." SIAM J. Appl. Math., vo1.21, 166-185, 1971.
[17]K. Murota. "Convexity and Steinitz's exchange property". Adv. Math., 124, 272–311, 1996.
[18]T.H.E. Meuwissen. "Maximizing the response of selection with a predefined rate of inbreeding." J. Anim. Sci., 75:934–940, 1997.
[19]K. Murota. "Algorithms in discrete convex analysis, IEICE Trans." Systems and Information,E83-D, 344–352, 2000.
[20]K. Murota. "Discrete Convex Analysis—An Introduction." Kyoritsu, Tokyo, 2001 (in Japanese).
[21]S. Moriguchi, K. Murota, and A. Shioura. "Scaling algorithms for M-convex function minimization." IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E85-A, 922–929, 2002.
[22]T.H.E. Meuwissen. "Gencont: an operational tool for controlling inbreeding in selection and conservation schemes." In Proceedings of the 7th Congress on Genetics Applied to Livestock Production, 19-23, 2002.
[23]K. Murota. "Discrete Convex Analysis." SIAM, Philadelphia, 2003.
[24]K. Murota. "On steepest descent algorithms for discrete convex functions." SIAM Journal on
Optimization, 14(3):699–707, 2004.
[25]T.J. Mullin, J. Hallander, O. Rosvall, and B. Andersson. "Using simulation to optimise tree breeding programmes in Europe: an introduction to POPSIM." Technical Report Nr. 711-2010, Arbetsrapport fran Skogforsk, 2010.
[26]T.J. Mullin. "OPSEL 1.0: A computer program for optimal selection in forest tree breeding by mathematical programming." Technical Report Nr. 841-2014, Arbetsrapport fran Skogforsk, 2014.
[27]T.J. Mullin and P. Belotti. "Using branch-and-bound algorithms to optimize selection of a fixed-size breeding population under a relatedness constraint." Tree genetics & genomes, 12(1):4, 2016.
[28]T.J. Mullin. "OPSEL 2.0: a computer program for optimal selection in tree breeding." Technical Report Nr. 954-2017, Arbetsrapport fran Skogforsk, 2017.
[29]R. Pong-Wong, J.A. Woolliams. "Optimisation of contribution of candidate parents to maximise genetic gain and restricting inbreeding using semidefinite programming. Genet." Sel. Evol. 39, 3–25, 2007.
[30]A. Shioura. "Minimization of an M-convex function." Discrete Appl. Math., 84, 215–220, 1998.
[31]S. Safarina, S. Moriguchi, T.J. Mullin, and M. Yamashita. "Conic relaxation approaches for equal deployment problems". arXiv preprint arXiv:1703.03155, 2017.
[32]P. Tseng. "Further results on approximating nonconvex quadratic optimization by semidefinite programming relaxation." SIAM Journal on Optimization, 14(1):268–283, 2003.
[33]N. Tsuchimura, S. Moriguchi, and K. Murota. "Discrete convex optimization solvers and demonstration softwares." Transactions of the Japan Society for Industrial and Applied Mathematic, 23(2):233–252, 2013. (In Japanese).
[34]S. Wright. "Coefficients of inbreeding and relationship." The American Naturalist, 56(645):330–338, 1922.
[35]C.G. Williams and O. Savolainen. "Inbreeding depression in conifers: implications for breeding strategy." Forest Science, 42(1):102–117, 1996.
[36]J. Woolliams. "Genetic contributions and inbreeding." In:Oldenbroek, K. (ed.)Utilisation and Conservation of Farm Animal Genetic Resources, 147–165. Wageningen Academic Publishers,Wageningen, 2007.
[37]M. Yamashita, K. Fujisawa, and M. Kojima. "Implementation and evaluation of SDPA6.0 (SemiDefinite Programming Algorithm 6.0)." Optim. Methods Softw., 18(4):491–505, 2003.
[38]M. Yamashita, K. Fujisawa, M. Fukuda, K. Kobayashi, K. Nakta, and M. Nakata. "Latest developments in the SDPA family for solving large-scale SDPs." In M. F. Anjos and J. B. Lasserre, editors, Handbook on Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, chapter 24, 687–714. Springer, NY, USA, 2012.
[39]M. Yamashita, T.J. Mullin, and S. Safarina. "An efficient second-order cone programming approach for optimal selection in tree breeding." Optimization Letters, 1-15, 2017.