列生成算法在金融风险管理中的信用评分卡优化问题求解示例 题目描述 在金融风险管理中，银行需要开发信用评分卡来评估客户的违约风险。评分卡由多个特征（如年龄、收入、负债比等）及其对应的分数段组成。每个特征可以被划分为若干个分箱（如年龄分为" <30"、"30-45"、">45"），每个分箱对应一个分数值。目标是选择最优的分箱和分数分配，使得评分卡能够最大程度地区分好坏客户（即好客户得分高，坏客户得分低），同时满足业务约束（如单调性约束：年龄越大分数越高）。 这个问题可以建模为一个大规模整数规划问题。由于特征和分箱组合非常多，直接求解很困难。列生成算法通过将问题分解为主问题（选择最优分数分配）和子问题（生成新的有潜力的分箱模式），能够有效求解。 解题过程 第一步：问题建模 假设有N个客户样本，每个客户有M个特征。将每个特征划分为多个分箱，每个分箱对应一个决策变量（分数值）。目标函数是最大化好坏客户的分数差异（可用AUC或KS指标衡量），约束包括： 单调性约束：某些特征的分数需随分箱递增/递减 分数范围约束 模型复杂度约束 主问题建模为线性规划： $$\max \sum_ {i=1}^N w_ i s_ i$$ $$s.t. \sum_ {j=1}^J a_ {ij} \lambda_ j = s_ i \quad \forall i$$ $$\sum_ {j=1}^J \lambda_ j = 1$$ $$\lambda_ j \geq 0$$ 其中$s_ i$是客户i的分数，$a_ {ij}$是模式j对客户i的分数贡献，$\lambda_ j$是模式j的权重。 第二步：初始化限制主问题 从一组简单的初始分箱模式开始（如等宽分箱）。计算每个模式的特征分数，构建初始的评分卡。这会给出一个可行的但可能不是最优的初始解。 第三步：构建子问题生成新列 子问题的目标是找到一个能改善当前评分卡的新分箱模式（即新列）。通过求解以下优化问题： $$\max \sum_ {i=1}^N \pi_ i a_ {ij} - \mu$$ 其中$\pi_ i$是主问题的对偶变量，$\mu$是等式约束的对偶变量。 这个子问题可以分解为每个特征的独立优化问题。对于每个特征，需要找到一种分箱方式，使得新模式的检验数（reduced cost）最大。 第四步：子问题求解细节 对每个特征，考虑所有可能的分箱方式： 计算每个分箱的好坏客户分布 确保满足单调性约束 计算每种分箱方式的检验数 这是一个组合优化问题，但特征数不多时可以用动态规划求解。例如对年龄特征，要找到最优的切分点使得检验数最大。 第五步：收敛判断 如果找到的新列检验数为正（即能改善目标函数），则将其加入主问题重新求解。否则当前解已是最优，算法终止。 第六步：整数解处理 由于最终需要整数解（每个客户只属于一个分箱），需要在列生成后使用分支定界法找到整数解，或者对连续解进行取整处理。 实例演示 假设有1000个客户，3个特征（年龄、收入、负债比）。初始用等宽分箱将每个特征分为3箱。 第一次迭代： 求解限制主问题，得到对偶变量值 在子问题中发现"年龄"特征的新分箱方式（如 <25, 25-40, 40-60, >60）能提高目标函数 将新模式加入主问题 经过5次迭代后，算法收敛，得到最优的评分卡分箱方案，KS指标从初始的0.35提升到0.48。