离散优化(discrete-optimization)-笔记

工具

• or-tool
  • 约束规划
  • 路径搜索
  • 网络流
• scip
  • python api
  • 线性规划(LP)
  • 整数规划(IP)/混合整数规划(MIP)

空间搜索

• 贪心算法:快速寻找到一个可行解
• 动态规划:枚举
• A*搜索
• 减少搜索空间 - 分支定界裁剪
• 通过线性松弛(relaxation)得到一个良好bound
• 快速成功/失败(first-fail)

constraint programming 约束规划

• 约束传播(如a!=b , b!=c 可得 a!=c)
• 全局约束all difference
• element 约束( values[index] = target)
• 冗余(redundant)去除
• 相似性(symmetry)破环

局部搜索(local search)

• 算法思路
  • 得到一个可行解
  • 找到可行解的邻域(neighbor)
  • 移动到莫一个邻域解
• 遗传算法
  • 生成基因(可行解)
  • 和别的基因杂交
  • 突变
  • 竞争(如按照得分进行概率选取)
• 模拟退火

start_temp //起始温度
end_temp //终止温度
curr_temp //当前温度
iter_n  //内循环次数
dec // 温度下降因子
curr_status //当前可行解
while curr_temp > end_temp:
  curr_temp *= dec
  for i in range(iter_n):
    neighbor = find_neighbor(curr_status)
    d = score(neighbor ) > score(curr_status)
    if d <0 or exp(-d/curr_temp) < random(0,1)
      curr_status = neightbor

• 禁忌搜索

线性规划(凸优化)

• 局部最优解 -> 全局最优解
• 最优解在定点

MIP

• 分支定界
• 平面切割