學術產出-Theses
Article View/Open
Publication Export
-
題名 著色數的規畫模型及應用 作者 王竣玄 貢獻者 劉明郎
王竣玄關鍵詞 選點問題
著色問題
最小著色數
極大團
團
指派問題
node packing problem
graph coloring problem
chromatic number
maximal clique
clique
assignment problem日期 2002 上傳時間 9-May-2016 16:39:26 (UTC+8) 摘要 著色問題(graph coloring problem)的研究已行之有年，並衍生出廣泛的實際應用，但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型，其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型，其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式，取代原有的選點限制式，縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。
The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem.
摘要 ABSTRACT 摘要-----iii 目次-----v 表目次-----vi 圖目次-----vii 第一章 緒論-----1 1.1 前言-----1 1.2 文獻回顧-----2 第二章 建構著色問題的0/1整數規畫模型-----4 2.1 選點問題(NPP)-----4 2.2 著色問題(GCP)-----5 2.3 完全圖-----9 2.4 點著色有限制時的GCP-----12 第三章 特殊指派問題-----14 3.1 問題描述-----14 3.2 尋找極大團的演算法-----18 3.3 實例及計算結果-----20 第四章 結論與建議-----25 參考文獻-----26 附錄 GAMS程式-----28 表目次 表一 10件工作的時段-----21 表二 人員被雇用的底薪要求-----21 表三 每位人員執行每項工作所要求的薪資-----21 表四 實例計算結果之比較-----24 圖目次 圖一 範例2.2中的圖形G=(V,E)-----9 圖二 特殊指派問題範例的工作時間區段-----16 圖三 工作1至工作7所生成的圖形H-----17 圖四 G1是一個區間圖-----19 圖五 G1的區間表示重新排序-----20 圖六 工作的時段區間分佈圖-----22 圖七 將不連續的工作時段區間重新命名-----22 圖八 利用演算法3.1將工作時段的區間重新排序-----23 圖九 實例問題的最佳指派-----24參考文獻 Akkoyunlu, E. A., The enumeration of maximal cliques of large graphs, SIAM Journal on Computing 2, 1-6 (1973). Balakrishnan, R. and K. Ranganathan, A Textbook of Graph Theory, Springer, New York, NY (1991). Balas, E. and C. Yu, Finding a maximum clique in an arbitrary graph, SIAM Journal on Computing 15, 1054-1068 (1986). Balas, E. and J. Xue, Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM Journal on Computing 20, 209-221 (1991). Bron, C. and J. Kerbosch, Finding all cliques of an undirected graph, Communications of the ACM 16, 575-579 (1973). Brooke, A., D. Kendrick, and A. Meeraus, GAMS-A User’s Guide, The Scientific Press, Redwood City, CA (1988). Chaudhry, S., S. McCormick, and I. D. Moon, Locating independent facilities with maximum weight: Greedy heuristics, Omega 14, 383-389 (1986). Joseph, D., J. Meidanis, and P. Tiwari, Determining DNA sequence similarity using maximal independent set algorithms for interval graphs, Algorithms Theory — SWAT ’92, 326-337 (1992). Leighton, F. T., A graph coloring algorithm for large scheduling problems, Journal of Research of the National Bureau of Standards 84(6), 489-496 (1979). Mehta, N. K., The application of a graph coloring method to an examination scheduling problem, Interfaces 11(5), 57-61 (1981). Moon, I. D. and S. Chaudhry, An analysis of network location problems with distance constraints, Management Science 30, 290-307 (1984). Murray, A. and R. Church, Facets for node packing, European Journal of Operational Research 101, 598-608 (1997). Nemhauser, G. L. and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, NY (1988). Padberg, M., On the facial structure of set packing polyhedra, Mathematical Programming 5, 199-215 (1973). Pardalos, P. and J. Xue, The maximal clique problem, Journal of Global Optimization 4, 301-328 (1994). Toregas, C., R. Swain, C. ReVelle, and L. Bergman, The location of emergency service facilities, Operations Research 19, 1363-1373 (1971). Tucker, A., Applied Combinatorics, Wiley, New York, NY (1995). Weintraub, A., F. Barahona, and R. Epstein, A column generation algorithms for solving general forest planning problems with adjacency constraints, Forest Science 40, 142-161 (1994). de Werra, D., Extensions of coloring models for scheduling purposes, European Journal of Operational Research 92, 474-492 (1996). de Werra, D., On a multiconstrained model for chromatic scheduling, Discrete Applied Mathematics 94, 171-180 (1999). Welsh, D. J. A. and M. B. Powell, An upper bound to the chromatic number of a graph and its application to the timetabling problems, Computer Journal 10, 85-86 (1967). West, D. B., Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NY (1996). Wood, D. C., A technique for coloring a graph applicable to large scale time-tabling problems, Computer Journal 12, 317-319 (1969). 描述 碩士
國立政治大學
應用數學系
89751007資料來源 http://thesis.lib.nccu.edu.tw/record/#A2010000326 資料類型 thesis dc.contributor.advisor 劉明郎 zh_TW dc.contributor.author (Authors) 王竣玄 zh_TW dc.creator (作者) 王竣玄 zh_TW dc.date (日期) 2002 en_US dc.date.accessioned 9-May-2016 16:39:26 (UTC+8) - dc.date.available 9-May-2016 16:39:26 (UTC+8) - dc.date.issued (上傳時間) 9-May-2016 16:39:26 (UTC+8) - dc.identifier (Other Identifiers) A2010000326 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/95623 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學系 zh_TW dc.description (描述) 89751007 zh_TW dc.description.abstract (摘要) 著色問題(graph coloring problem)的研究已行之有年，並衍生出廣泛的實際應用，但還缺乏一般化的著色問題模型。本論文建構一般化的著色問題模型，其目標函數包含顏色成本的固定支出和點著色變動成本。此著色模型為0/1整數線性規畫模型，其限制式含有選點問題(node packing problem)的限制式。我們利用圖中的極大團(maximal clique)所構成的強力限制式，取代原有的選點限制式，縮短求解時間。我們更進一步舉出一個特殊指派問題並將此著色模型應用於此指派問題上。本論文亦針對此指派問題發展了一個演算法來尋找極大團。計算結果顯示極大團限制式對於此著色問題模型的求解有極大的效益。 zh_TW dc.description.abstract (摘要) The graph coloring problem (GCP) has been studied for a long time and it has a wide variety of applications. A straightforward formulation of graph coloring problem has not been formulated yet. In this paper, we formulate a general GCP model that concerns setup cost and variable cost of different colors. The resulting model is an integer program that involves the packing constraint. The packing constraint in the GCP model can be replaced by the maximal clique constraint in order to shorten the solution time. A special assignment problem is presented which essentially is a GCP model application. An algorithm of finding maximal cliques for this assignment problem is developed. The computational results show the efficiency of maximal clique constraints for the GCP problem. en_US dc.description.abstract (摘要) 摘要 ABSTRACT 摘要-----iii 目次-----v 表目次-----vi 圖目次-----vii 第一章 緒論-----1 1.1 前言-----1 1.2 文獻回顧-----2 第二章 建構著色問題的0/1整數規畫模型-----4 2.1 選點問題(NPP)-----4 2.2 著色問題(GCP)-----5 2.3 完全圖-----9 2.4 點著色有限制時的GCP-----12 第三章 特殊指派問題-----14 3.1 問題描述-----14 3.2 尋找極大團的演算法-----18 3.3 實例及計算結果-----20 第四章 結論與建議-----25 參考文獻-----26 附錄 GAMS程式-----28 表目次 表一 10件工作的時段-----21 表二 人員被雇用的底薪要求-----21 表三 每位人員執行每項工作所要求的薪資-----21 表四 實例計算結果之比較-----24 圖目次 圖一 範例2.2中的圖形G=(V,E)-----9 圖二 特殊指派問題範例的工作時間區段-----16 圖三 工作1至工作7所生成的圖形H-----17 圖四 G1是一個區間圖-----19 圖五 G1的區間表示重新排序-----20 圖六 工作的時段區間分佈圖-----22 圖七 將不連續的工作時段區間重新命名-----22 圖八 利用演算法3.1將工作時段的區間重新排序-----23 圖九 實例問題的最佳指派-----24 - dc.description.tableofcontents 摘要 ABSTRACT 摘要-----iii 目次-----v 表目次-----vi 圖目次-----vii 第一章 緒論-----1 1.1 前言-----1 1.2 文獻回顧-----2 第二章 建構著色問題的0/1整數規畫模型-----4 2.1 選點問題(NPP)-----4 2.2 著色問題(GCP)-----5 2.3 完全圖-----9 2.4 點著色有限制時的GCP-----12 第三章 特殊指派問題-----14 3.1 問題描述-----14 3.2 尋找極大團的演算法-----18 3.3 實例及計算結果-----20 第四章 結論與建議-----25 參考文獻-----26 附錄 GAMS程式-----28 表目次 表一 10件工作的時段-----21 表二 人員被雇用的底薪要求-----21 表三 每位人員執行每項工作所要求的薪資-----21 表四 實例計算結果之比較-----24 圖目次 圖一 範例2.2中的圖形G=(V,E)-----9 圖二 特殊指派問題範例的工作時間區段-----16 圖三 工作1至工作7所生成的圖形H-----17 圖四 G1是一個區間圖-----19 圖五 G1的區間表示重新排序-----20 圖六 工作的時段區間分佈圖-----22 圖七 將不連續的工作時段區間重新命名-----22 圖八 利用演算法3.1將工作時段的區間重新排序-----23 圖九 實例問題的最佳指派-----24 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#A2010000326 en_US dc.subject (關鍵詞) 選點問題 zh_TW dc.subject (關鍵詞) 著色問題 zh_TW dc.subject (關鍵詞) 最小著色數 zh_TW dc.subject (關鍵詞) 極大團 zh_TW dc.subject (關鍵詞) 團 zh_TW dc.subject (關鍵詞) 指派問題 zh_TW dc.subject (關鍵詞) node packing problem en_US dc.subject (關鍵詞) graph coloring problem en_US dc.subject (關鍵詞) chromatic number en_US dc.subject (關鍵詞) maximal clique en_US dc.subject (關鍵詞) clique en_US dc.subject (關鍵詞) assignment problem en_US dc.title (題名) 著色數的規畫模型及應用 zh_TW dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) Akkoyunlu, E. A., The enumeration of maximal cliques of large graphs, SIAM Journal on Computing 2, 1-6 (1973). Balakrishnan, R. and K. Ranganathan, A Textbook of Graph Theory, Springer, New York, NY (1991). Balas, E. and C. Yu, Finding a maximum clique in an arbitrary graph, SIAM Journal on Computing 15, 1054-1068 (1986). Balas, E. and J. Xue, Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM Journal on Computing 20, 209-221 (1991). Bron, C. and J. Kerbosch, Finding all cliques of an undirected graph, Communications of the ACM 16, 575-579 (1973). Brooke, A., D. Kendrick, and A. Meeraus, GAMS-A User’s Guide, The Scientific Press, Redwood City, CA (1988). Chaudhry, S., S. McCormick, and I. D. Moon, Locating independent facilities with maximum weight: Greedy heuristics, Omega 14, 383-389 (1986). Joseph, D., J. Meidanis, and P. Tiwari, Determining DNA sequence similarity using maximal independent set algorithms for interval graphs, Algorithms Theory — SWAT ’92, 326-337 (1992). Leighton, F. T., A graph coloring algorithm for large scheduling problems, Journal of Research of the National Bureau of Standards 84(6), 489-496 (1979). Mehta, N. K., The application of a graph coloring method to an examination scheduling problem, Interfaces 11(5), 57-61 (1981). Moon, I. D. and S. Chaudhry, An analysis of network location problems with distance constraints, Management Science 30, 290-307 (1984). Murray, A. and R. Church, Facets for node packing, European Journal of Operational Research 101, 598-608 (1997). Nemhauser, G. L. and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, NY (1988). Padberg, M., On the facial structure of set packing polyhedra, Mathematical Programming 5, 199-215 (1973). Pardalos, P. and J. Xue, The maximal clique problem, Journal of Global Optimization 4, 301-328 (1994). Toregas, C., R. Swain, C. ReVelle, and L. Bergman, The location of emergency service facilities, Operations Research 19, 1363-1373 (1971). Tucker, A., Applied Combinatorics, Wiley, New York, NY (1995). Weintraub, A., F. Barahona, and R. Epstein, A column generation algorithms for solving general forest planning problems with adjacency constraints, Forest Science 40, 142-161 (1994). de Werra, D., Extensions of coloring models for scheduling purposes, European Journal of Operational Research 92, 474-492 (1996). de Werra, D., On a multiconstrained model for chromatic scheduling, Discrete Applied Mathematics 94, 171-180 (1999). Welsh, D. J. A. and M. B. Powell, An upper bound to the chromatic number of a graph and its application to the timetabling problems, Computer Journal 10, 85-86 (1967). West, D. B., Introduction to Graph Theory, Prentice Hall, Upper Saddle River, NY (1996). Wood, D. C., A technique for coloring a graph applicable to large scale time-tabling problems, Computer Journal 12, 317-319 (1969). zh_TW
