name: integer-program-solver description: 用于组合优化问题的整数和混合整数规划技能，涉及离散决策变量。 allowed-tools: Bash(*) Read Write Edit Glob Grep WebFetch metadata: author: babysitter-sdk version: “1.0.0” category: operations-research backlog-id: SK-IE-002
integer-program-solver
你是 integer-program-solver - 一个专门用于为组合优化问题制定和求解整数及混合整数规划模型的技能。
概述
此技能支持AI驱动的整数规划，包括：
- 二进制和整数变量建模
- Big-M约束公式化
- 逻辑约束线性化
- 分支定界求解跟踪
- MIP间隙分析和收敛监控
- 热启动解注入
- 解池生成
先决条件
- Python 3.8+ 及优化库
- 已安装 Google OR-Tools、Gurobi 或 CPLEX
- 理解组合优化
能力
1. 二进制变量建模
from ortools.linear_solver import pywraplp
def facility_location():
solver = pywraplp.Solver.CreateSolver('SCIP')
# 二进制变量：是否开设设施 j？
facilities = range(5)
customers = range(10)
y = {j: solver.BoolVar(f'y_{j}') for j in facilities}
x = {(i,j): solver.BoolVar(f'x_{i}_{j}')
for i in customers for j in facilities}
# 每个客户恰好分配给一个设施
for i in customers:
solver.Add(sum(x[i,j] for j in facilities) == 1)
# 只能分配给已开设的设施
for i in customers:
for j in facilities:
solver.Add(x[i,j] <= y[j])
# 目标：最小化总成本
fixed_cost = [100, 120, 110, 130, 90]
transport_cost = [[...]] # 成本矩阵
solver.Minimize(
sum(fixed_cost[j] * y[j] for j in facilities) +
sum(transport_cost[i][j] * x[i,j]
for i in customers for j in facilities)
)
return solver
2. Big-M约束公式化
# 使用 Big-M 的 If-then 约束
def big_m_constraints(solver, x, y, M=1e6):
"""
模型：如果 x > 0 则 y = 1
线性化：x <= M * y
"""
solver.Add(x <= M * y)
# 二选一约束
# 要么约束1成立，要么约束2成立
# c1: a*x <= b + M*(1-z)
# c2: c*x <= d + M*z
z = solver.BoolVar('z')
solver.Add(a*x <= b + M*(1-z))
solver.Add(c*x <= d + M*z)
3. 逻辑约束线性化
def logical_constraints(solver, y1, y2, y3):
"""
常见逻辑约束
"""
# AND：z = y1 AND y2
z_and = solver.BoolVar('z_and')
solver.Add(z_and <= y1)
solver.Add(z_and <= y2)
solver.Add(z_and >= y1 + y2 - 1)
# OR：z = y1 OR y2
z_or = solver.BoolVar('z_or')
solver.Add(z_or >= y1)
solver.Add(z_or >= y2)
solver.Add(z_or <= y1 + y2)
# 蕴含：y1 => y2
solver.Add(y1 <= y2)
# 至多一个：sum(y) <= 1
solver.Add(y1 + y2 + y3 <= 1)
# 恰好一个：sum(y) == 1
solver.Add(y1 + y2 + y3 == 1)
4. MIP间隙监控
def solve_with_gap_tracking(solver, time_limit=300):
solver.SetTimeLimit(time_limit * 1000)
# 设置 MIP 间隙容忍度
solver.SetSolverSpecificParametersAsString(
"limits/gap = 0.01" # 1% 最优间隙
)
status = solver.Solve()
result = {
"status": status,
"objective": solver.Objective().Value(),
"best_bound": solver.Objective().BestBound(),
"gap": (solver.Objective().Value() -
solver.Objective().BestBound()) /
solver.Objective().Value() * 100,
"nodes_explored": solver.nodes(),
"time": solver.WallTime() / 1000
}
return result
5. 解池生成
def generate_solution_pool(model, max_solutions=10):
"""
生成多个接近最优的解
"""
solutions = []
for i in range(max_solutions):
status = model.solve()
if status == pywraplp.Solver.OPTIMAL:
solution = {
"objective": model.Objective().Value(),
"variables": {v.name(): v.solution_value()
for v in model.variables()}
}
solutions.append(solution)
# 添加约束以排除此解
exclude = sum(v if v.solution_value() > 0.5 else (1-v)
for v in binary_vars)
model.Add(exclude <= len(binary_vars) - 1)
else:
break
return solutions
常见应用
设施选址
- 仓库选址
- 枢纽辐射网络
- 覆盖问题
调度
- 车间作业调度
- 车辆路径规划
- 人员排班
分配
- 任务分配
- 资源匹配
- 集合覆盖
流程集成
此技能与以下流程集成：
linear-programming-model-development.jstransportation-route-optimization.jswarehouse-layout-slotting-optimization.js
输出格式
{
"model_name": "Facility_Location",
"status": "optimal",
"objective_value": 4520.0,
"mip_gap": 0.0,
"solve_time_seconds": 12.5,
"nodes_explored": 1547,
"solution": {
"open_facilities": [0, 2, 4],
"assignments": {
"customer_0": "facility_2",
"customer_1": "facility_0"
}
},
"solution_pool_size": 5
}
工具/库
| 库 | 描述 | 使用场景 |
|---|---|---|
| Google OR-Tools | 开源 | 通用 MIP |
| Gurobi | 商业 | 高性能 |
| CPLEX | 商业 | 企业级 |
| SCIP | 开源 | 研究 |
| CBC | 开源 | 通用目的 |
最佳实践
- 紧致公式化 - 优先选择紧致的约束而非松散的
- 有效不等式 - 尽可能添加切割平面
- 热启动 - 提供初始解
- 对称性破缺 - 减少对称解
- 变量分支 - 选择好的分支变量
- 时间限制 - 设置合理的求解时间
约束
- 通过 MIP 间隙监控解的质量
- 记录所有线性化技术
- 先用小规模实例测试
- 对于大规模问题考虑启发式方法