整數規劃是一種常見的數學規劃問題，其決策變數一般用來表示不可分割性或是/否的決策。而整數規劃問題一般也可以被詮釋成一種離散的最佳化問題，其可應用的領域很廣泛，如: 路線決策、飛機機隊規劃、飛機或飛航組員排班問題。然而因為整數規劃問題本身具有組合的特性，因此求解整數規劃問題會比求解線性規劃問題還要困難，此外，許多現實生活中的整數規劃問題規模都非常龐大，使得求解此一問題需要耗費非常多的時間。
本研究提出以梯度法求解二位元整數規劃問題，並能使大型問題得以快速求解。此演算法分為兩階段，於第一階段放鬆原始的二位元整數限制式，利用線性規劃法求得一個可行解；於第二階段，對二位元整數限制式做修正，並引入拉格朗日乘數 (Lagrange multipliers)，將原始問題轉化成拉格朗日對偶 (Lagrange dual)形式，接著利用梯度演算法快速求解得到最佳解或是近似最佳解。本研究應用此演算法求解不同規模的二位元整數規劃問題，並驗證此法其快速求解的效率，並探討縮短求解計算時間及如何更進一步提升第二階段中，梯度演算法的求解效率。

Integer Programming (IP) is a common problem class where decision variables represent indivisibility or yes/no decisions. IP can also be interpreted as discrete optimizations which are extensively used in the areas of routing decisions, fleet assignment, and aircraft/aircrew scheduling. Solving IP models is much harder than solving Linear Programming (LP) models because of their intrinsically combinatorial nature. In addition, many “real-world” problems have a huge problem size that makes solving the related IP-based model time-consuming.
This thesis proposes a gradient method for binary IP that enable large problems to be solved in a short amount of time. The algorithm is partitioned into two phases. In phase 1 of the algorithm, integrality constraints are first relaxed and the original problem is solved by the LP algorithm. In phase 2, all integrality constraints are modified again and added back. The Lagrange multipliers are then introduced to form a Lagrange dual problem. We then use the gradient method to quickly search for the optimal or nearly optimal solution. After developing the algorithm, we apply this approach to various kinds of binary IP problems, and demonstrate that the proposed algorithm has an efficient performance. In addition, discussions about the reduction in computation time and how to improve the performance in the phase 2 are also shown in this thesis.

[1] H. Sherali, et al., "Airline fleet assignment concepts, models, and algorithms," European Journal of Operational Research, vol. 172, pp. 1-30, 2006.
[2] R. K. Ahuja, et al., "A very large-scale neighborhood search algorithm for the combined through and fleet assignment model," MIT Sloan Working Paper 2001.
[3] L. TD, et al., "A study of USAF air traffic controller shiftwork: sleep, fatigue, activity, and mood analyses," Aviat Space Environ Med., vol. 68, pp. 18-23, 1997.
[4] S. C. Chang, "A new aircrew-scheduling model for short-haul routes," Journal of Air Transport Management, pp. 249-260, 2002.
[5] C. Barnhart, et al., "Formulating a mixed integer programming problem to improve solvability," Operations Research, vol. 41, pp. 1013-1019, 1993.
[6] J. Caulkins, et al., "Using integer programming to optimize investments in security countermeasures: A practical tool for fixed budgets," (2006). Heinz Research. Paper 14. http://repository.cmu.edu/heinzworks/14.
[7] H. G. Kwatny, et al., "Optimal shipboard power system management via mixed integer dynamic programming," presented at the IEEE Electric Ship Technologies Symposium, 2005.
[8] G. Lancia, "Integer programming models for computational biology problems," Journal of Computer Science and Technology vol. 19, pp. 60-77, 2006.
[9] C. Guéret, et al., Applications of optimization with Xpress-MP. London: Dash Optimization Ltd., 2002.
[10] P. Ratprasert, et al., "Ant colony optimization applied on weekly fleet assignment model," presented at the 14th ATRS World Conference, 2010.
[11] A. H. Land and A. G. Doig, "An automatic method of solving discrete programming problems," Econometrica, vol. 28, pp. 497-520, 1960.
[12] J. J. Forrest and D. Goldfarb, "Steepest-edge simplex algorithms for linear programming," Mathematical Programming vol. 57, pp. 341-374, 1992.
[13] G. B. Dantzig, Linear programming and extensions. Princeton, NJ: Princeton University Press, 1963.
[14] M. W. P. Savelsbergh, "Preprocessing and probing techniques for mixed integer programming problems," INFORMS Journal on Computing, vol. 6, pp. 445-454 1994.
[15] C. Barnhart, et al., "Branch-and-Price: Column generation for solving huge integer programs," Operations Research, vol. 46, pp. 316-329, 1998.
[16] M. J. Brusco and L. W. Jacobs, "A simulated annealing approach to the solution of flexible labour scheduling problems," The Journal of the Operational Research Society, vol. 44, pp. 1191-1200 1993.
[17] T.-C. Jung and J. Chung, "Genetic algorithms: Airline fleet assignment using genetic algorithm," presented at the Genetic and Evolutionary Computation Conference New York, USA, 2002.
[18] B. A. McCarl and T. H. Spreen. (1997). Applied mathematical programming using algebraic systems. Available for downloading (on the Internet at http://agecon2.tamu.edu/people/faculty/mccarl-bruce/books.htm).
[19] D. G. Luenberger, Linear and nonlinear programming: Addison-Wesley 1984.
[20] V. Klee and G. J. Minty, "How good is the simplex algorithm," Academic Press, New York,1972.
[21] G. L. Nemhauser, "The age of optimization: solving large-scale real-world problems," Operations Research, vol. 42, pp. 5-13, 1994.
[22] S. Leyffer, "Deterministic methods for mixed integer nonlinear programming," PhD, Department of Mathematics & Computer Science, University of Dundee, Dundee, 1993.
[23] H. A. Taha, Operations research: an introduction. Upper Saddle River, N.J.: Pearson Prentice Hall, 2007.
[24] S. J. Sugden, "A class of direct search methods for nonlinear integer programming," PhD, School of Information & Computing Sciences, Bond University, Gold Coast, 1992.
[25] G. MITRA, et al., "A distributed processing algorithm for solving integer programs using a cluster of workstations," Parallel Computing, vol. 23, pp. 733-753, 1997.
[26] R. E. Gomory, "Outline of an algorithm for integer solutions to linear programs," Bulletin of the American Mathematical Society, vol. 64, pp. 275-278, 1958.
[27] A. M. Geoffrion, "Lagrangean relaxation for integer programming," in Mathematical Programming Study 2, ed: Morth-Holland Publishing Company, 1974, pp. 82-114.
[28] S. H. Zanakis, "Heuristic 0-1 linear programming an experimental comparison of three methods," Management Science, vol. 24, pp. 91-104, 1977.
[29] H. P. Williams, "The problem with integer programming," IMA Journal of Management Mathematics, 2010.
[30] E. Balas, et al., "A lift-and-project cutting plane algorithm for mixed 0–1 programs," Mathematical Programming, vol. 58, pp. 295-324, 1993.
[31] J. E. Mitchell, "Cutting plane algorithms for integer programming," in Encyclopedia of Optimization vol. 2, ed: Kluwer Academic, 2001, pp. 525-533.
[32] K. Farwell, "Gomory cutting plane algorithm using exact arithmetic," PhD., Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York, 2006.
[33] X. Zhao and P. B. Luh, "A Fuzzy gradient method in Lagrangian relaxation for integer programming problems," presented at the 37th IEEE Conference on Decision and Control, 1998.
[34] M. L. Fisher, "The Lagrangian relaxation method for solving integer programming problems," Management Science, vol. 50, pp. 1861-1871, 2004.
[35] P. Gang, et al., "An evolutionary multiple heuristic with genetic local search for solving TSP," International Journal of Information Technology, vol. 14, pp. 1-11, 2008.
[36] S. Boyd and L. Vandenberghe, Convex optimization: Cambridge University Press, 2004.
[37] G. Strang, Introduction to applied mathematics Wellesley-Cambridge Press, 1986.
[38] M. S. Bazaraa and C. M. Shetty, Nonlinear programming: theory and algorithms. New York: Wiley, 1979.
[39] D. P. Bertsekas, Constrained optimization and Lagrange multiplier methods. Belmont, Mass.: Athena Scientific, 1996.
[40] F. S. Hillier and G. J. Lieberman, Introduction to operations research: McGraw-Hill College, 2006.
[41] Z.-J. Shi and J. Shen, "Step-size estimation for unconstrained optimization methods," Computational and Applied Mathematics, vol. 24, pp. 399-416, 2005.
[42] R. Fletcher and C. M. Reeves, "Function minimization by conjugate gradients," The Computer Journal, vol. 7, pp. 149-154, 1964.
[43] B. T. Polyak, "The conjugate gradient method in extremal problems," USSR Computational Mathematics and Mathematical Physics, vol. 9, pp. 94-112, 1969.
[44] Y. Liu and C. Storey, "Efficient generalized conjugate gradient algorithms, Part 1: Theory," Journal of Optimization Theory and Applications vol. 69, pp. 129-137, 1991.
[45] Y. H. Dai and Y. Yuan, "A nonlinear conjugate gradient method with a strong global convergence property," SIAM J. on Optimization, vol. 10, pp. 177-182 1999.
[46] M. J. D. Powell, "Restart procedures for the conjugate gradient method " Mathematical Programming vol. 12, pp. 241-254, 1977.
[47] W. W. Hager and H. Zhang, "A survey of nonlinear conjugate gradient methods," Pacific Journal of Optimization, vol. 2, pp. 35-58, 2006.
[48] A. S. Nemirovski and M. J. Todd, "Interior-point methods for optimization," Acta Numerica, vol. 17, pp. 191-234, 2008.
[49] G. Yuan, "A conjugate gradient method for unconstrained optimization problems," International Journal of Mathematics and Mathematical Sciences, vol. 2009, pp. 1-14, 2009.
[50] Z. Wei, et al., "The convergence properties of some new conjugate gradient methods," Applied Mathematics and Computation, vol. 183, pp. 1341-1350 2006.