由于图优化问题规模的不断扩大以及相应的实际应用需求的日益增多，亟需找到能够高效求解此类问题的相应算法。美国离散数学和理论计算机科学中心（简称，DIMACS）曾在1992年提出的3个挑战问题：最大团，图染色和可满足性问题。本次报告主要讲解两个算法用来求解最大加权团问题和最小加权图染色问题。首先，第一个工作是通过设计一种高效的局部搜索求解策略，将最大加权团问题的求解规模由原有的四千节点左右提高到百万节点级别。其次，第二个工作是针对大规模问题背景下的最小加权图染色问题，设计了一种全新的化简策略和基于多邻居的局部搜索算法，将最小加权图着色问题的求解规模提高了一个数量级。