限制条件优化
使用集合让一切井井有条
根据您的偏好保存内容并对其进行分类。
约束优化或
约束编程
(CP) 命名,用于从大量候选方案中确定可行的解决方案,问题可以建模
许多科学和工程学科中都存在 CP 问题。(“编程”一词有点不恰当,类似于“计算机”曾经表示“会计算的人”的意思)。此处的“编程”是指安排规划,而不是使用计算机语言进行编程。)
CP 基于可行性(找到可行的解决方案)而非优化(找出最佳解决方案),并且侧重于约束和变量,而非目标函数。事实上,CP 问题可能甚至没有目标函数 - 目标是通过为问题添加约束条件,将大量可能的解决方案缩小为更易于管理的子集。
一个非常适合 CP 的问题示例是员工调度。当持续运营的公司(例如工厂)需要为员工制定每周时间表时,就会出现这个问题。举一个非常简单的例子:某公司每天有三个班次,每班 8 小时,每天为四名员工中的三名安排不同的班次,同时给第四个员工休息日。即使在这样小的情况下,可能的时间表数量也非常庞大:每天可能有 4! = 4 * 3 * 2 * 1 = 24
名可能的员工班次,因此每周可以分配的员工数超过 4 亿。通常情况下,还有其他限制会减少可行解决方案的数量,例如,每位员工每周至少工作天数。当您添加新的约束条件时,CP 方法会跟踪哪些解决方案仍然可行,这使其成为解决大型实际调度问题的强大工具。
CP 在世界各地拥有一个非常活跃的广泛社区,这里有专门的科学期刊、各种会议以及各种不同的解析技术。CP 已成功应用于规划、调度以及众多具有异构约束的其他领域。
Google 提供了几种解决 CP 问题的方法:
如果您的问题可以使用线性目标和线性约束进行建模,则表示您的问题属于线性规划问题,应考虑使用 MPSolver。(不过,即使路线问题可以用线性模型表示,我们的车辆路线库通常也能妥善解决。)
示例
下一部分将介绍 CP-SAT 求解器,它是约束编程的主要 OR 工具求解器。(SAT 代表“可满足性”:求解器使用各种技术以及 CP 方法来解决 SAT 问题。)
以下是一些非常适合 CP-SAT 求解器的调度问题示例:
两个经典的 CP 问题是 N 皇后问题和密码谜题。
如未另行说明,那么本页面中的内容已根据知识共享署名 4.0 许可获得了许可,并且代码示例已根据 Apache 2.0 许可获得了许可。有关详情,请参阅 Google 开发者网站政策。Java 是 Oracle 和/或其关联公司的注册商标。
最后更新时间 (UTC):2024-08-09。
[null,null,["最后更新时间 (UTC):2024-08-09。"],[[["\u003cp\u003eConstraint Programming (CP) helps find feasible solutions within a large set of possibilities by applying constraints to a problem.\u003c/p\u003e\n"],["\u003cp\u003eCP focuses on finding solutions that satisfy all constraints, rather than optimizing for a specific objective.\u003c/p\u003e\n"],["\u003cp\u003eEmployee scheduling, where numerous possible shift combinations exist, is an example of a problem effectively addressed using CP.\u003c/p\u003e\n"],["\u003cp\u003eGoogle provides tools like the CP-SAT solver and the original CP solver to tackle constraint programming problems.\u003c/p\u003e\n"],["\u003cp\u003eCP is widely used in various fields, with dedicated research and applications in planning and scheduling.\u003c/p\u003e\n"]]],["Constraint programming (CP) identifies feasible solutions from a vast set of candidates by modeling problems with constraints. CP focuses on feasibility, constraints, and variables rather than optimization. It's used in employee scheduling, where numerous constraints, such as shifts and days off, reduce the number of viable schedules. Tools like the CP-SAT solver and the original CP solver are available, and CP is applied to scheduling and planning problems, along with classic puzzles like N-queens and cryptarithmetic.\n"],null,["# Constraint Optimization\n\n**Constraint optimization** , or\n[**constraint programming**](https://en.wikipedia.org/wiki/Constraint_programming)\n(CP), is the name given to identifying feasible solutions out of a very large\nset of candidates, where the problem can be modeled in terms of arbitrary\nconstraints.\nCP problems arise in many scientific and engineering disciplines. (The word\n\"programming\" is a bit of a misnomer, similar to how \"computer\" once meant\n\"a person who computes\". Here, \"programming\" refers to the arrangement of a plan\n, rather than programming in a computer language.)\n\nCP is based on *feasibility* (finding a feasible solution) rather than\noptimization (finding an optimal solution) and focuses on the constraints and\nvariables rather than the objective function. In fact, a CP problem may not even\nhave an objective function --- the goal may be to narrow down a very\nlarge set of possible solutions to a more manageable subset by adding\nconstraints to the problem.\n\nAn example of a problem that is well-suited for CP is **employee scheduling** .\nThe problem arises when companies that operate continuously --- such as\nfactories --- need to create weekly schedules for their employees. Here's a\nvery simplified example: a company runs three 8-hour shifts per day and assigns\nthree of its four employees to different shifts each day, while giving the\nfourth the day off. Even in such a small case, the number of possible schedules\nis huge: each day, there are `4! = 4 * 3 * 2 * 1 = 24` possible employee\nassignments, so the number of possible weekly schedules is 24^7^, which\nis over 4.5 billion.\nUsually there will be other constraints that reduce the number of feasible\nsolutions --- for example, that each employee works at least a minimum\nnumber of days per week. The CP method keeps track of which solutions remain\nfeasible when you add new constraints, which makes it a powerful tool for\nsolving large, real-world scheduling problems.\n\nCP has a widespread and very active community around the world with dedicated\nscientific journals, conferences, and an arsenal of different solving techniques\n. CP has been successfully applied in planning, scheduling, and numerous other\ndomains with heterogeneous constraints.\n\nTools\n-----\n\nGoogle provides few ways to solve problems:\n\n- [CP-SAT solver](/optimization/cp/cp_solver): A **constraint programming** solver that uses SAT (satisfiability) methods.\n- [Original CP solver](/optimization/routing/original_cp_solver): A **constraint programming** solver used in the routing library.\n\nIf your problem can be modeled with a linear objective and linear constraints,\nthen you have a [linear programming](/optimization/lp) problem and should\nconsider [MPSolver](/optimization/lp/mpsolver). (However, routing problems are\ntypically best solved with our\n[vehicle routing library](/optimization/reference/constraint_solver/routing)\neven if they can be represented with a linear model.)\n\nExamples\n--------\n\nThe [next section](/optimization/cp/cp_solver) describes the CP-SAT solver, the\nprimary OR-Tools solver for constraint programming. (SAT stands for\n**satisfiability**: the solver uses techniques for solving SAT problems along\nwith CP methods.)\n\nHere are some examples of scheduling problems that are well-suited for the\nCP-SAT solver:\n\n- [Employee Scheduling](/optimization/scheduling/employee_scheduling)\n- [The Job shop problem](/optimization/scheduling/job_shop)\n\nTwo classic CP problems are the [N-queens problem](/optimization/cp/queens) and\n[cryptarithmetic puzzles](/optimization/puzzles/cryptarithmetic).\n\n*[CP]: Constraint Programming"]]