本部分介绍了原始约束编程求解器，它已被高级的 CP-SAT 求解器取代。
以下部分介绍了如何求解 CP-SAT 部分中所述的示例，这次使用原始 CP 求解器。如果您坚持要使用原始 CP 求解器，可以浏览 API 参考文档。请注意，原始 CP 求解器是路由库的基础，自定义路由模型可能需要其 API。
导入库
以下代码会导入所需的库。
from ortools.constraint_solver import pywrapcp
#include <ostream>
#include <string>
#include "ortools/constraint_solver/constraint_solver.h"
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
import java.util.logging.Logger;
using System;
using Google.OrTools.ConstraintSolver;
声明求解器
以下代码会声明求解器。
solver = pywrapcp.Solver("CPSimple")
Solver solver("CpSimple");
Solver solver = new Solver("CpSimple");
Solver solver = new Solver("CpSimple");
创建变量
以下代码用于创建该问题的变量。
该求解器会创建 x、y 和 z 三个变量，每个变量可以取值 0、1 或 2。
num_vals = 3
x = solver.IntVar(0, num_vals - 1, "x")
y = solver.IntVar(0, num_vals - 1, "y")
z = solver.IntVar(0, num_vals - 1, "z")
const int64_t num_vals = 3;
IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x");
IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y");
IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");
final long numVals = 3;
final IntVar x = solver.makeIntVar(0, numVals - 1, "x");
final IntVar y = solver.makeIntVar(0, numVals - 1, "y");
final IntVar z = solver.makeIntVar(0, numVals - 1, "z");
const long numVals = 3;
IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
IntVar z = solver.MakeIntVar(0, numVals - 1, "z");
创建限制条件
以下代码会创建约束条件 x ≠ y。
solver.Add(x != y)
print("Number of constraints: ", solver.Constraints())
solver.AddConstraint(solver.MakeAllDifferent({x, y}));
LOG(INFO) << "Number of constraints: "
<< std::to_string(solver.constraints());
solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
logger.info("Number of constraints: " + solver.constraints());
solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
Console.WriteLine($"Number of constraints: {solver.Constraints()}");
调用求解器
以下代码调用求解器。
决策构建器是原始 CP 求解器的主要输入。它包含以下内容：
vars- 包含问题变量的数组。- 一条规则，用于选择要向哪个变量赋值。
- 一条规则，用于选择要分配给该变量的下一个值。
如需了解详情，请参阅决策构建器。
decision_builder = solver.Phase(
[x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
)
DecisionBuilder* const db = solver.MakePhase(
{x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);
final DecisionBuilder db = solver.makePhase(
new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
DecisionBuilder db =
solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
输出解决方案
解决方案打印机的代码会在求解器找到后显示每个解决方案，详见下一部分。
由于我们的问题有多种解决方案，因此可以使用 while solver.NextSolution() 循环遍历这些解决方案。（请注意，这与 CP-SAT 求解器的解决方案打印机的运作方式不同）。
count = 0
solver.NewSearch(decision_builder)
while solver.NextSolution():
count += 1
solution = f"Solution {count}:\n"
for var in [x, y, z]:
solution += f" {var.Name()} = {var.Value()}"
print(solution)
solver.EndSearch()
print(f"Number of solutions found: {count}")
int count = 0;
solver.NewSearch(db);
while (solver.NextSolution()) {
++count;
LOG(INFO) << "Solution " << count << ":" << std::endl
<< " x=" << x->Value() << " y=" << y->Value()
<< " z=" << z->Value();
}
solver.EndSearch();
LOG(INFO) << "Number of solutions found: " << solver.solutions();
int count = 0;
solver.newSearch(db);
while (solver.nextSolution()) {
++count;
logger.info(
String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value()));
}
solver.endSearch();
logger.info("Number of solutions found: " + solver.solutions());
int count = 0;
solver.NewSearch(db);
while (solver.NextSolution())
{
++count;
Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
}
solver.EndSearch();
Console.WriteLine($"Number of solutions found: {solver.Solutions()}");
求解器返回的结果
以下是求解器找到的 18 个解：
Number of constraints: 1 Solution 1: x = 0 y = 1 z = 0 Solution 2: x = 0 y = 1 z = 1 Solution 3: x = 0 y = 1 z = 2 Solution 4: x = 0 y = 2 z = 0 Solution 5: x = 0 y = 2 z = 1 Solution 6: x = 0 y = 2 z = 2 Solution 7: x = 1 y = 0 z = 0 Solution 8: x = 1 y = 0 z = 1 Solution 9: x = 1 y = 0 z = 2 Solution 10: x = 1 y = 2 z = 0 Solution 11: x = 1 y = 2 z = 1 Solution 12: x = 1 y = 2 z = 2 Solution 13: x = 2 y = 0 z = 0 Solution 14: x = 2 y = 0 z = 1 Solution 15: x = 2 y = 0 z = 2 Solution 16: x = 2 y = 1 z = 0 Solution 17: x = 2 y = 1 z = 1 Solution 18: x = 2 y = 1 z = 2 Number of solutions found: 18 Advanced usage: Problem solved in 2 ms Memory usage: 13918208 bytes
完整程序
以下是使用原始 CP 求解器的示例的完整程序。
"""Simple Constraint optimization example."""
from ortools.constraint_solver import pywrapcp
def main():
"""Entry point of the program."""
# Instantiate the solver.
solver = pywrapcp.Solver("CPSimple")
# Create the variables.
num_vals = 3
x = solver.IntVar(0, num_vals - 1, "x")
y = solver.IntVar(0, num_vals - 1, "y")
z = solver.IntVar(0, num_vals - 1, "z")
# Constraint 0: x != y.
solver.Add(x != y)
print("Number of constraints: ", solver.Constraints())
# Solve the problem.
decision_builder = solver.Phase(
[x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
)
# Print solution on console.
count = 0
solver.NewSearch(decision_builder)
while solver.NextSolution():
count += 1
solution = f"Solution {count}:\n"
for var in [x, y, z]:
solution += f" {var.Name()} = {var.Value()}"
print(solution)
solver.EndSearch()
print(f"Number of solutions found: {count}")
print("Advanced usage:")
print(f"Problem solved in {solver.WallTime()}ms")
print(f"Memory usage: {pywrapcp.Solver.MemoryUsage()}bytes")
if __name__ == "__main__":
main()
#include <ostream>
#include <string>
#include "ortools/constraint_solver/constraint_solver.h"
namespace operations_research {
void SimpleCpProgram() {
// Instantiate the solver.
Solver solver("CpSimple");
// Create the variables.
const int64_t num_vals = 3;
IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x");
IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y");
IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");
// Constraint 0: x != y..
solver.AddConstraint(solver.MakeAllDifferent({x, y}));
LOG(INFO) << "Number of constraints: "
<< std::to_string(solver.constraints());
// Solve the problem.
DecisionBuilder* const db = solver.MakePhase(
{x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);
// Print solution on console.
int count = 0;
solver.NewSearch(db);
while (solver.NextSolution()) {
++count;
LOG(INFO) << "Solution " << count << ":" << std::endl
<< " x=" << x->Value() << " y=" << y->Value()
<< " z=" << z->Value();
}
solver.EndSearch();
LOG(INFO) << "Number of solutions found: " << solver.solutions();
LOG(INFO) << "Advanced usage:" << std::endl
<< "Problem solved in " << std::to_string(solver.wall_time())
<< "ms" << std::endl
<< "Memory usage: " << std::to_string(Solver::MemoryUsage())
<< "bytes";
}
} // namespace operations_research
int main(int /*argc*/, char* /*argv*/[]) {
operations_research::SimpleCpProgram();
return EXIT_SUCCESS;
}
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
import java.util.logging.Logger;
/** Simple CP Program.*/
public class SimpleCpProgram {
private SimpleCpProgram() {}
private static final Logger logger = Logger.getLogger(SimpleCpProgram.class.getName());
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
// Instantiate the solver.
Solver solver = new Solver("CpSimple");
// Create the variables.
final long numVals = 3;
final IntVar x = solver.makeIntVar(0, numVals - 1, "x");
final IntVar y = solver.makeIntVar(0, numVals - 1, "y");
final IntVar z = solver.makeIntVar(0, numVals - 1, "z");
// Constraint 0: x != y..
solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
logger.info("Number of constraints: " + solver.constraints());
// Solve the problem.
final DecisionBuilder db = solver.makePhase(
new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
// Print solution on console.
int count = 0;
solver.newSearch(db);
while (solver.nextSolution()) {
++count;
logger.info(
String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value()));
}
solver.endSearch();
logger.info("Number of solutions found: " + solver.solutions());
logger.info(String.format("Advanced usage:\nProblem solved in %d ms\nMemory usage: %d bytes",
solver.wallTime(), Solver.memoryUsage()));
}
}
using System;
using Google.OrTools.ConstraintSolver;
/// <summary>
/// This is a simple CP program.
/// </summary>
public class SimpleCpProgram
{
public static void Main(String[] args)
{
// Instantiate the solver.
Solver solver = new Solver("CpSimple");
// Create the variables.
const long numVals = 3;
IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
IntVar z = solver.MakeIntVar(0, numVals - 1, "z");
// Constraint 0: x != y..
solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
Console.WriteLine($"Number of constraints: {solver.Constraints()}");
// Solve the problem.
DecisionBuilder db =
solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);
// Print solution on console.
int count = 0;
solver.NewSearch(db);
while (solver.NextSolution())
{
++count;
Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
}
solver.EndSearch();
Console.WriteLine($"Number of solutions found: {solver.Solutions()}");
Console.WriteLine("Advanced usage:");
Console.WriteLine($"Problem solved in {solver.WallTime()}ms");
Console.WriteLine($"Memory usage: {Solver.MemoryUsage()}bytes");
}
}
决策者
原始 CP 求解器的主要输入是决策构建器，它包含问题的变量并设置求解器的选项。
上一部分中的代码示例使用 Phase 方法（对应于 C++ 方法 MakePhase）创建决策构建器。
“阶段”一词指的是搜索的一个阶段。在这个简单示例中，只有一个阶段，但对于更复杂的问题，决策制定工具可以有多个阶段，以便求解器从一个阶段到下一个阶段采用不同的搜索策略。
Phase 方法有三个输入参数：
vars- 包含问题变量的数组，在本例中为[x, y, z]。IntVarStrategy- 用于选择下一个未绑定变量来赋值的规则。此处的代码使用了默认的CHOOSE_FIRST_UNBOUND，这意味着在每一步，求解器都会按照第一个未绑定变量在传递给Phase方法的变量数组中出现的顺序选择第一个未绑定变量。IntValueStrategy- 用于选择要为变量分配的下一个值的规则。 此处的代码使用默认ASSIGN_MIN_VALUE，它会选择尚未为变量尝试过的最小值。这将按递增顺序分配值。另一个选项是ASSIGN_MAX_VALUE，在这种情况下，求解器将按降序分配值。