Optimization primer: how MIP and CP solvers think优化入门:MIP 和 CP 求解器是怎么想的
Rules decide what is allowed. Optimization decides what is best. A process (BPMS) carries the result out. This page explains the two algorithm families behind solvers such as IBM CPLEX Optimizer, CP Optimizer and OR-Tools, with small examples you can check by hand and three demos that run in your browser.规则决定什么可以做,优化决定什么最好,流程(BPMS)负责执行。本页讲 IBM CPLEX Optimizer、CP Optimizer、OR-Tools 这类求解器背后的两类算法,每个都有能手算核对的小例子,另有三个在浏览器里运行的演示。
Teaching material with self-written examples and public concepts only. Not an official IBM resource. Runnable C and Python code is in examples/optimization.教学材料,例子为自编,只用公开概念,不是 IBM 官方资源。可运行的 C 和 Python 代码在 examples/optimization。
Two families两大类
| MIP (mixed-integer programming) | CP (constraint programming) | |
|---|---|---|
| Good at | amounts and cost: how many, how much | order and time: who, when, in what sequence |
| Core idea | LP relaxation gives a bound; branch and prune | propagate constraints; search; backtrack |
| IBM engine | CPLEX Optimizer | CP Optimizer |
| OR-Tools | linear solver wrapper (GLOP, SCIP, CPLEX, Gurobi) | CP-SAT |
| MIP(混合整数规划) | CP(约束规划) | |
|---|---|---|
| 擅长 | 数量和成本:多少、花多少钱 | 顺序和时间:谁、什么时候、什么顺序 |
| 核心 | LP 松弛给出界;分支、剪枝 | 约束传播;搜索;回溯 |
| IBM 引擎 | CPLEX Optimizer | CP Optimizer |
| OR-Tools | 线性求解器封装(GLOP、SCIP、CPLEX、Gurobi) | CP-SAT |
Demo 1: branch and bound on a snack budget演示 1:用分支定界选零食
Cola costs 4 and gives 5 happiness; chocolate 5 and 6; chips 6 and 7. Each at most once. Move the budget and watch the solver compute a bound, try a branch, and prune.可乐 4 元 5 分,巧克力 5 元 6 分,薯片 6 元 7 分,每样最多一份。拖动预算,看求解器怎么算上限、试分支、剪枝。
Demo 2: constraint propagation on a duty roster演示 2:用约束传播排值班
Three people, A, B and C, take the duty on Mon, Tue and Wed, one each. B is the day after A. C is not on Wed. Tap Propagate first, then guess if it is not enough.甲、乙、丙三人周一到周三各值一天。乙在甲的第二天,丙不能周三。先点「传播」,不够再猜。
Demo 3: rules first, then optimization演示 3:先规则,后优化
Three electricians: Zhang San 50 an hour, Li Si 40, Wang Wu 45; at most 6 hours each. Orders: A 3 h, B 2 h, C 4 h. C is high-voltage work, and only Zhang San and Wang Wu hold the certificate. A rules engine decides who is allowed; the optimizer picks the cheapest plan among the allowed ones. Switch the rule off and on.三个电工:张三时薪 50,李四 40,王五 45,每人最多 6 小时。工单:A 3 小时,B 2 小时,C 4 小时。C 是高压活,只有张三和王五持证。规则引擎决定谁可以做,优化器在可以的人里选最省钱的方案。把规则关掉、打开对比一下。
The eight algorithms, step by step八个算法的步骤
Which tool for which job什么工具做什么
| Tool | Use it for |
|---|---|
| OR-Tools (free, open source) | learning to model; CP-SAT for scheduling; routing; graph algorithms |
| IBM CPLEX Optimizer | large-scale MIP with commercial support; free community edition has a size limit |
| IBM CP Optimizer | scheduling and sequencing with rich time rules |
| 工具 | 用途 |
|---|---|
| OR-Tools(免费开源) | 学建模;CP-SAT 排程;车辆路径;图算法 |
| IBM CPLEX Optimizer | 大规模 MIP,有商业支持;免费社区版有规模上限 |
| IBM CP Optimizer | 时间规则复杂的排程排序 |
Modelling matters more than writing the algorithm: you declare variables, constraints and an objective, and the solver does branch and bound or propagation for you.会建模比会写算法更重要:你只声明变量、约束和目标,分支定界和传播交给求解器。