臺灣博碩士論文加值系統

線性二階規劃（bilevel linear programming）問題是多階規劃問題的特例之一，它是處理分權式決策問題的一種數學模式。在線性二階規劃問題中，雖然高階與低階目標函數都是線性函數，且限制式解集合是凸集合，
然而一般而言，它的理性反應解集合（亦稱為可行解集合）是非凸集合，
因此，線性二階規劃問題是歸類為非線性最佳化問題。
在此論文中，我們以仿射比例內點主演算法（primal affine scaling algorithm）及主對偶（primal-dual）演算法為基礎，建立了求解線性二階規劃問題的內點演算法。我們進而求解隨機產生之線性二階規劃問題，以驗證演算法的正確性與有效性。測試結果顯示，與其它演算法比較，我們所建立之內點演算法非常適合求解較大型的線性二階規劃問題。
另一方面，只要些許的修訂，我們所建立的內點演算法也可以用來求解多目標規劃問題中的有效解集合線性最佳化（linear optimization over the efficient set）問題。經由求解隨機產生之有效解集合線性最佳化問題，結果顯示我們所建立的內點演算法不但正確、有效，而且比其它演算法更適合求解較大型的問題。

Linear bilevel programming (BLP) problem is a special case of multilevel programming problem, which is a mathematical programming model for decentralized decision problems. In a linear BLP problem, the higher and the lower levels objective functions are both linear functions and the constraints region is a convex set, however, the rational reaction set (or, the feasible set) is generally nonconvex. Hence the linear BLP problem is mathematically classified as a nonlinear optimization problem.
In this dissertation, based on primal and primal-dual affine scaling algorithms, we develop interior point algorithms for solving linear BLP problems. We test the accuracy and efficiency of the proposed algorithms by solving randomly generated problems. The computational results show that the interior point method is suitable for solving relatively larger scale linear BLP problems.
On the other hand, after modification, the proposed interior point algorithm also provides an effective and accurate approach to solve linear optimization over the efficient set (OES) problems. The computational results also show that the modified algorithm can solve relatively larger scale linear OES problems.

1 Introduction 1
1.1 Problem Definition . . . . . . . . . . . . . . . . . . . 1
1.2 General Properties and Complexity . . . . . . . . . . . 3
1.3 Applications and Existing Algorithms . . . . . . . . . . 5
1.4 Overview . . . . . . . . . . . . . . . . . . . . . . . . 8
2 The Related Problems 11
2.1 Multiple Objective Linear Programming . . . . . . . . . 11
2.2 Linear Optimization over the Efficient Set. . . . . . . 12
2.3 The Equivalency Between Linear BLP Problem and Linear
OES Problem . . . . . . . . . . . . . . . . . . . . . . 16
3 Affine Scaling Algorithms 19
3.1 Primal Affine Scaling Algorithm . . . . . . . . . . . . 19
3.1.1 Ideas of Primal Affine Scaling Algorithm. . . . . . 20
3.1.2 Starting and Terminating the Algorithm. . . . . . . 22
3.1.3 Algorithmic Procedure . . . . . . . . . . . . . . . 24
3.2 Primal-Dual Affine Scaling Algorithm. . . . . . . . . . 25
3.2.1 Ideas of Primal-Dual Affine Scaling Algorithm . . . 26
3.2.2 Algorithmic Procedure . . . . . . . . . . . . . . . 29
4 A Primal Affine Scaling Algorithm for Solving Linear BLP
Problems 30
4.1 Characteristics of the Reformulated Problems. . . . . . 30
4.2 Ideas of the Proposed Algorithm . . . . . . . . . . . . 32
4.3 The Proposed Algorithm. . . . . . . . . . . . . . . . . 37
4.4 A Numerical Example . . . . . . . . . . . . . . . . . . 39
4.5 Computational Experience. . . . . . . . . . . . . . . . 43
4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . 46
5 A Primal-Dual Affine Scaling Algorithm for Solving Linear
BLP Problems 48
5.1 Ideas of the Proposed Algorithm . . . . . . . . . . . . 48
5.2 The Proposed Algorithm. . . . . . . . . . . . . . . . . 50
5.3 An Illustrative Example . . . . . . . . . . . . . . . . 53
5.4 Computational Experience. . . . . . . . . . . . . . . . 57
5.5 Discussion. . . . . . . . . . . . . . . . . . . . . . . 61
6 A Modified Algorithm for Solving Linear OES Problems 63
6.1 Ideas of the Modified Algorithm . . . . . . . . . . . . 63
6.2 The Modified Algorithm. . . . . . . . . . . . . . . . . 65
6.3 A Numerical Example . . . . . . . . . . . . . . . . . . 68
6.4 Computational Experience. . . . . . . . . . . . . . . . 72
6.5 Discussion. . . . . . . . . . . . . . . . . . . . . . . 75
7 Conclusion 77
7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . 77
7.2 Future Research . . . . . . . . . . . . . . . . . . . . 78
Bibliography 80
Appendix 89

[1] Aiyoshi, E. and Shimizu, K. (1981), “Hierarchical Decentralized Systems and Its New Solution by a Barrier Method”, IEEE Transactions on Systems, Man, and Cybernetics, 11, 444—449.
[2] Amouzegar, M. and Moshirvaziri, K. (1998), “A Penalty Method for Linear Bilevel Programming Problems”, Multilevel Optimizations: Algorithms and Applications, Migdalas, A. et al. (eds.), 251—271, Kluwer Academic Publishers, Netherlands.
[3] Arbel, A. (1993), “An Interior Multiobjective Linear Programming Algorithm”, Computers and Operations Research, 20, 7, 723—735.
[4] Arbel, A. (1994a), “Anchoring Points and Cones of Opportunities in Interior Multiobjective Linear Programming”, Journal of Operational Research Society, 45, 1, 83—96.
[5] Arbel, A. (1994b), “Using Efficient Anchoring Points for Generating Search Directions in Interior Multiobjective Linear Programming”, Journal of Operational Research Society, 45, 3, 330—344.
[6] Arbel, A. (1995), “An Interior Multiple Objective Primal-Dual Linear Programming Algorithm Using Efficient Anchoring Points”, Journal of Operational Research Society, 46, 1121—1132.
[7] Arbel, A. and Korhonen, P. (1996), “Using Aspiration Levels in an Interactive Interior Multiobjective Linear Programming Algorithm”, European Journal of Operational Research, 89, 193—201.
[8] Arbel, A (1997), “An Interior Multiobjective Primal-Dual Linear Programming Algorithm Based on Approximated Gradients and Ecient Anchoring Points”, Computers and Operations Research, 24, 4, 353—365.
[9] Bard, J. F. and Falk, J. E. (1982), “An Explicit Solution to the Multi-Level Programming Problem”, Computers and Operations Research, 9, 1, 77—100.
[10] Bard, J. F. (1983a), “An Efficient Point Algorithm for a Linear Two-Stage Optimization Problem”, Operations Research, 31, 4, 670—684.
[11] Bard, J. F. (1983b), “Coordination of a Multidivisional Organization Through Two Levels of Management”, OMEGA, 11, 5, 457—468.
[12] Bard, J. F. (1984), “Optimality Conditions for the Bi-Level Programming Problem”, Naval Research Logistics Quarterly, 31, 13—26.
[13] Bard, J. F. and Moore, J. T. (1990), “A Branch and Bound Algorithm for the Bilevel Programming Problem”, SIAM J. on Scientific and Statistical Computing, 11, 281—292.
[14] Bard, J. F. (1991), “Technical Note: Some Properties of the Bilevel Programming Problem”, Journal of Optimization Theory and Applications, 68, 2, 371—378.
[15] Barnes, E. (1986), “A Variation on Karmarkar’s Algorithm for Solving Linear Programming Problem”, Mathematical Programming, 31, 174—182.
[16] Ben-Ayed, O. and Blair, C. E. (1990), “Computational Difficulties of Bilevel Linear Programming”, Operations Research, 38, 3, 556—560.
[17] Ben-Ayed, O. (1990), “A Bilevel Linear Programming Model Applied to the Tunisian Inter-Regional Network Design Problem”, Revue Tunisienne d’´Economie et de Gestion, 5, 235—279.
[18] Ben-Ayed, O., Blair, C. E., Boyce, D. E., and LeBlanc, L. (1992), “Construction of a Real-World Bilevel Linear Programming Model of the Highway Design Problem”, Annals of Operations Research, 34, 219—254.
[19] Ben-Ayed, O. (1993), “Bilevel Linear Programming”, Computers and Operations Research, 20, 5, 485—501.
[20] Benson, H. P. (1984), “Optimization over the Efficient Set”, Journal of Mathematical Analysis and Applications, 98, 562—580.
[21] Benson, H. P. (1991), “An All-Linear Programming Relaxation Algorithm for Optimizing over the Efficient set”, Journal of Global Optimization, 1, 83—104.
[22] Benson, H. P. (1992), “A Finite, Nonadjacent Extreme Point Search Algorithm for Optimization over the Efficient Set”, Journal of Optimization Theory and Applications, 73, 47—64.
[23] Benson, H. P. and Sayin, S. (1993), “A Face Search Heuristic Algorithm for Optimizing over the Efficient Set”, Naval Research Logistics, 40, 103—116.
[24] Benson, H. P. (1993), “A Bisection Extreme Point Search Algorithm for Optimizing over the Efficient Set”, Journal of Global Optimization, 3, 1, 95—111.
[25] Benson, H. P. and Sayin, S. (1994), “Optimization over the Efficient Set: Four Special Cases”, Journal of Optimization Theory and Applications, 80, 1, 3—18.
[26] Benson, H. P and Lee, D. (1996), “Outcome-Based Algorithm for Optimizing Over the Efficient Set of a Bicriteria Linear Programming Problem”, Journal of Optimization Theory and Applications, 88, 77—105.
[27] Benson, H. P. (1998), “Hybrid Approach for Solving Multiple-Objective Linear Programs in Outcome Space”, Journal of Optimization Theory and Applications, 98, 1, 17—35.
[28] Bialas, W. F. and Karwan, M. H. (1984), “Two-Level Linear Programming”, Management Science, 30, 1004—1020.
[29] Bisschop, J., Candler, W., Duloy, J. H., and O’Mara, G. T. (1982), “The Indus Basin Model: A Special Application of Two-Level Linear Programming”, Mathematical Programming Study, 20, 30—38.
[30] Bracken, J. and McGill, J. T. (1973), “Mathematical Programs with Optimization Problems in the Constraints”, Operations Research, 21, 37—44.
[31] Brotcorne, L., Labb´e, M., Marcotte, P., and Savard, G. (2000), “A Bilevel Model and Solution Algorithm for a Freight Tari-Setting Problem”, Transportation Science, 34, 3, 289—302.
[32] Breiner, A. and Avriel, M. (1999), “Two-Stage Approach for Quantitative Policy Analysis Using Bilevel Programming”, Journal of Optimization Theory and Applications, 100, 1, 15—27.
[33] Calamai, P. and Vicente, L. (1994), “Generating Quadratic Bilevel Programming Problems”, ACM Transactions on Mathematical Software, 20, 103—119.
[34] Candler, W., Fortuny-Amat, J., and McCarl, B. (1981), “The Potential Role of Multilevel Programming in Agricultural Economics”, American Journal of Agricultural Economics, 63, 3, 521—531.
[35] Candler, W. and Townsly, R. (1982), “A Linear Two-Level Programming Problem”, Computers and Operations Research, 9, 59—76.
[36] Candler, W. (1988), “A Linear Bilevel Programming Algorithm: A Comment”, Computers and Operations Research, 15, 3, 297—298.
[37] Clark, P. A. and Westerberg, A. W. (1990a), “Bilevel Programming for Steady- State Chemical Process Design—I. Fundamentals and Algorithms”, Computers & Chemical Engineering, 14, 87—98.
[38] Clark, P. A. and Westerberg, A. W. (1990b), “Bilevel Programming for Steady-State Chemical Process Design—II. Performance Study for Nondegenerate Problems”, Computers & Chemical Engineering, 14, 99—110.
[39] Dauer, J. P. and Liu, Y. H. (1990), “Solving Multiple-Objective Linear Programs in Objective Space”, European Journal of Operational Research, 46, 350—357.
[40] Dauer, J. P. (1991), “Optimization over the Ecient Set Using an Active Constraint Approach”, Zeitschrift f¨ur Operations Research, 35, 185—195.
[41] Dempe, S. (1987), “A Simple Algorithm for the Linear Bilevel Programming Problem”, Optimization, 18, 373—385.
[42] Dempe, S. (1995), “Computing Optimal Incentives via Bilevel Programming”, Optimization, 33, 29—42.
[43] Deng, X. (1998), “Complexity Issues in Bilevel Linear Programming”, Multilevel Optimization: Algorithms and Applications, Migdalas, A. et al. (eds.), 149—164, Kluwer Academic Publishers, Netherlands.
[44] Dessouky, M. I., Ghiassi, M., and Davis, W. J. (1986), “Estimates of the Minimum Nondominated Criterion Values in Multiple-Criteria Decision Making”, Engineering Costs and Production Economics, 10, 95—104.
[45] Ecker, J, G. and Kouada, I. A. (1975), “Finding Efficient Points for Linear Multiple Objective Programs”, Mathematical Programming, 8, 375—377.
[46] Ecker, J. G. and Song, J. (1994), “Optimizing a Linear Function over an Efficient Set”, Journal of Optimization Theory and Application, 83, 3, 541—563.
[47] Feng, S. C. and Puthenpura, S. (1993), Linear Optimization and Extensions: Theory and Algorithms, Prentice-Hall, New York.
[48] Fortuny-Amat, J. and McCarl, B. (1981), “A Representation and Economic Interpretation of a Two-Level Programming Problem”, Journal of Operational Research Society, 32, 783—792.
[49] F¨ul¨op, J. (1993), “On the Equivalency Between a Linear Bilevel Programming Problem and Linear Optimization over the Efficient Set”, technical report, Computer and Automation Institute, Budapest.
[50] Gendreau, M., Marcotte, P., and Savard, G. (1996), “A Hybrid Tabu-Ascent Algorithm for the Linear Bilevel Programming Problem”, Journal of Global Optimization, 8, 217—233.
[51] Hansen, P., Jaumard, B., and Savard, G. (1992), “New Branch-and-Bound Rules for Linear Bilevel Programming”, SIAM Journal on Scientific and Statistical Computing, 13, 5, 1194—1217.
[52] Haurie, A., Savard, G., and White, D. J. (1990), “A Note on: An Efficient Point Algorithm for a Linear Two-Stage Optimization Problem”, Operations Research, 38, 3, 553—555.
[53] Haurie, A., Savard, G., and White, D. J. (1992), “A Two Player Game Model of Power Cogeneration in New England”, IEEE Transactions on Automatic Control, 37, 1451—1456.
[54] Horst, R. and Thoai, N. V. (1997), “Utility Function Programs and Optimization over the Efficient Set in Multiple-Objective Decision Making”, Journal of Optimization Theory and Applications, 92, 3, 605—631.
[55] Isermann, H. and Steuer, R. E. (1987), “Computational Experience Concerning Payoff Tables and Minimum Criterion Values over the Efficient Set”, European Journal of Operations Research, 33, 91—97.
[56] Ishizuka, Y. and Aiyoshi, E. (1992), “Double Penalty Method for Bilevel Optimization Problems”, Annals of Operations Research, 34, 73—88.
[57] Jeroslow, R. G. (1985), “The Polynomial Hierarchy and a Simple Model for Competitive Analysis”, Mathematical Programming, 32, 146—164.
[58] J´udice, J. J. and Faustino, A. (1988), “The Solution of the Linear Bilevel Programming Problem by Using the Linear Complementary Problem”, Investigac˜ao Operacional, 8, 77—95.
[59] J´udice, J. J. and Faustino, A. (1992), “A Sequential LCP Method for Bilevel Linear Programming”, Annals of Operations Research, 34, 89—106.
[60] Karmarkar, N. (1984), “A New Polynomial Time Algorithm for Linear Programming”, Combinatorica, 4, 373—395.
[61] Kim, T. and Suh, S. (1988), “Toward Developing a National Transportation Planning Model: A Bilevel Programming Approach for Korea”, Annals of Regional Science, 22, 65—80.
[62] Korhonen, P., Salo, S., and Steuer. R. E. (1997), “A Heuristic for Estimating NADIR Criterion Values in Multiple Objective Linear Programming”, Operations Research, 45, 5, 751—757.
[63] Leblance, L. J. and Boyce, D. E. (1986), “A Bilevel Programming Algorithm for Exact Solution of the Network Design Problem with User-Optimal Flows”, Transportation Research, 20B, 259—265.
[64] Liu, B. (1998), “Stackelberg-Nash Equilibrium for Multilevel Programming with Multiple Followers Using Genetic Algorithms”, Computers and Mathematics with Applications, 36, 7, 79—89.
[65] Liu, Y. H. and Hart, S. M. (1994), “Characterizing an Optimal Solution to the Linear Bilevel Programming Problem”, European Journal of Operational Research, 73, 1, 164—166.
[66] Liu, Y. H. and Hart, S. M. (1995), “Solving a Bilevel Linear Program When the Inner Decision Maker Controls Few Variables”, European Journal of Operational Research, 81, 644—651.
[67] Marcotte, P. (1986), “Network Design Problem with Congestion Effects: A Case of Bilevel Programming”, Mathematical Programming, 34, 142—162.
[68] Marcotte, P. and Savard, G. (1991), “A Note on the Pareto Optimality of Solutions to the Linear Bilevel Programming Problem”, Computers Operations Research, 18, 4, 355—359.
[69] Megiddo, N. and Shub, M. (1989), “Boundary Behavior of Interior Point Algorithms in Linear Programming”, Mathematics of Operations Research, 14, 104—111.
[70] Meijboom, B. R. (1986), “A Two-Level Planning Procedure with Respect to Make-or-Buy Decisions, Including Cost Allocations”, European Journal of Operational Research, 23, 301—309.
[71] Migdalas, A. (1995), “Bilevel Programming in Trac Planning: Models, Methods and Challenge”, Journal of Global Optimization, 7, 381—405.
[72] Monteiro, R. C., Adler, I., and Resende, M. C. (1990), “A Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and its Power Series Extension”, Mathematics of Operations Research, 15, 191—214.
[73] ¨Onal, H. (1993), “Modified Simplex Approach for Solving Bilevel Linear Programming Problems”, European Journal of Operational Research, 67, 1, 126—135.
[74] Philip, J. (1972), “Algorithms for the Vector Maximization Problem”, Mathematical Programming, 2, 207—229.
[75] Sayin, S. (1996), “An Algorithm Based on Facial Decomposition for Finding the Efficient Set in Multiple Objective Linear Programming”, Operations Research Letters, 19, 87—94.
[76] Sayin, S. (2000), “Optimizing over the Efficient Set Using a Top-Down Search of Faces”, Operations Research, 48, 1, 65—72.
[77] Shih, H. S., Lai, Y. J., and Lee, E. S. (1996), “Fuzzy Approach for Multi-level Mathematical Programming Problems”, Computers and Operations Research 23, 1, 73—91.
[78] Shih, H. S. and Lee, E. S. (1999), “Fuzzy Multi-level Minimum Cost Flow Problems”, Fuzzy Sets and Systems, 107, 159—176.
[79] Shih, H. S. and Lee, E. S. (2000), “Compensatory Fuzzy Multiple Level Decision Making”, Fuzzy Sets and Systems, 114, 71—87.
[80] Soismaa, M. (1999), “A Note on Efficient Solutions for the Linear Bilevel Programming Problem”, European Journal of Operational Research, 112, 427—431.
[81] Steuer, R. E. (1986), Multiple Criteria Optimization: Theory, Computation, and Application, John Wiley and Sons, New York.
[82] Suh, S. and Kim, T. (1992), “Solving Nonlinear Bilevel Programming Models of the Equilibrium Network Design Problem: A Comparative Review”, Annals of Operations Research, 34, 203—218.
[83] Tuy, H., Migdalas, A., and V¨arbrand, P. (1993), “A Global Optimization Approach for the Linear Two-Level Program”, Journal of Global Optimization, 3, 1—23.
[84] Tuy, H., Migdalas, A., and V¨arbrand, P. (1994), “A Quasiconcave Minimization Method for Solving Linear Two-Level Program”, Journal of Global Optimization, 4, 243—263.
[85] Tuy, H. and Ghannadan, S. (1998) “A New Branch and Bound Method for Bilevel Linear Programs”, Multilevel Optimization: Algorithms and Applications, Migdalas, A. et al. (eds.), 231—249, Kluwer Academic Publishers, Netherlands.
[86] Tuy, H. (1998), “Bilevel Linear Programming, Multiobjective Programming, and Monotonic Reverse Convex Programming”, Multilevel Optimization: Algorithms and Applications, Migdalas, A. et al. (eds.), 295—314, Kluwer Academic Publishers, Netherlands.
[87] ¨Unl¨u, G. (1987), “A Linear Bilevel Programming Algorithm Based on Bicriteria Programming”, Computers and Operations Research, 14, 2, 173—179.
[88] Vanderbei, R., Meketon, M., and Freedman, B. (1986), “A Modification of Karmarkar’s Linear Programming Algorithm”, Algorithmica, 1, 395—407.
[89] Vicente, L. N., Savard, G., and J´udice, J. (1994), “Descent Approaches for Quadratic Bilevel Programming”, Journal of Optimization Theory and Applications, 81, 379—399.
[90] Vicente, L. N. and Calamai, P. H. (1994), “Bilevel and Multilevel Programming: A Bibliography Review”, Journal of Global Optimization, 5, 291—306.
[91] Wen, U. P. (1983), “A Solution Procedure for the Resource Control Problem in Two-Level Hierarchical Decision Processes”, Journal of the Chinese Institute of Engineers, 6, 2, 91—97.
[92] Wen, U. P. and Jiang, C. F. (1988), “A Multilevel Programming Approach in Commission Rate Setting Problem”, Journal of the Chinese Institute of Engineers, 5, 1, 91—97.
[93] Wen, U. P. and Hsu, S. T. (1989), “A Note on A Linear Bi-Level Programming Algorithm Based on Bi-Criterion Programming”, Computers and Operations Research, 11, 1, 79—83.
[94] Wen, U. P. and Hsu, S. T. (1991), “Linear Bi-Level Programming Problem─A Review”, Journal of Operational Research Society, 42, 125—133.
[95] Wen, U. P. and Hsu, S. T. (1992), “Efficient Solutions for the Linear Bi-Level Programming Problem”, European Journal of Operational Research, 62, 354—362.
[96] Wen, U. P. and Lin, S. F. (1996), “Finding an Efficient Solution to Linear Bilevel Programming Problem”, Journal of Global Optimization, 8, 295—306.
[97] White, D. J. and Anandalingam, G. (1994), “A Penalty Function Approach for Solving Bi-Level Linear Programs”, Journal of Global Optimization, 3, 397—419.
[98] Yu, P. L. (1986), Multiple Criteria Decision Making: Concepts, Techniques and Extensions, Plenum Press, New York.
[99] Zeleny, M. (1982), Multiple Criteria Decision Making, McGraw-Hill, New York.