بخش قبل نشان داد که چگونه می توان تمام راه حل های یک مشکل CP را پیدا کرد. در مرحله بعد، نحوه یافتن راه حل بهینه را نشان خواهیم داد. به عنوان مثال، مشکل بهینه سازی زیر را حل می کنیم.
- 2 x + 2 y + 3 z را با توجه به محدودیت‌های زیر به حداکثر برسانید:
x + 7 ⁄ 2 y + 3 ⁄ 2 z ≤ 25 3 x - 5 y + 7 z ≤ 45 5 x + 2 y - 6 z ≤ 37 x ، y ، z ≥ 0 اعداد صحیح x ، y ، z
به منظور افزایش سرعت محاسبات، حل کننده CP-SAT روی اعداد صحیح کار می کند. این بدان معنی است که تمام محدودیت ها و هدف باید دارای ضرایب صحیح باشند. در مثال بالا، اولین محدودیت این شرط را ندارد. برای حل مشکل، ابتدا باید محدودیت را با ضرب آن در یک عدد صحیح به اندازه کافی بزرگ تبدیل کنید تا تمام ضرایب به اعداد صحیح تبدیل شوند. این در بخش محدودیت ها در زیر نشان داده شده است.
راه حل با استفاده از حل کننده CP-SAT
بخش های زیر یک برنامه پایتون را ارائه می دهد که با استفاده از حل کننده CP-SAT مشکل را حل می کند.
کتابخانه ها را وارد کنید
کد زیر کتابخانه مورد نیاز را وارد می کند.
from ortools.sat.python import cp_model
#include <stdint.h>
#include <stdlib.h>
#include <algorithm>
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/util/sorted_interval_list.h"
import static java.util.Arrays.stream;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;
using System;
using System.Linq;
using Google.OrTools.Sat;
مدل را اعلام کنید
کد زیر مدل مشکل را اعلام می کند.
model = cp_model.CpModel()
CpModelBuilder cp_model;
CpModel model = new CpModel();
CpModel model = new CpModel();
متغیرها را ایجاد کنید
کد زیر متغیرهای مشکل را ایجاد می کند.
var_upper_bound = max(50, 45, 37)
x = model.new_int_var(0, var_upper_bound, "x")
y = model.new_int_var(0, var_upper_bound, "y")
z = model.new_int_var(0, var_upper_bound, "z")
int64_t var_upper_bound = std::max({50, 45, 37});
const Domain domain(0, var_upper_bound);
const IntVar x = cp_model.NewIntVar(domain).WithName("x");
const IntVar y = cp_model.NewIntVar(domain).WithName("y");
const IntVar z = cp_model.NewIntVar(domain).WithName("z");
int varUpperBound = stream(new int[] {50, 45, 37}).max().getAsInt();
IntVar x = model.newIntVar(0, varUpperBound, "x");
IntVar y = model.newIntVar(0, varUpperBound, "y");
IntVar z = model.newIntVar(0, varUpperBound, "z");
int varUpperBound = new int[] { 50, 45, 37 }.Max();
IntVar x = model.NewIntVar(0, varUpperBound, "x");
IntVar y = model.NewIntVar(0, varUpperBound, "y");
IntVar z = model.NewIntVar(0, varUpperBound, "z");
محدودیت ها را تعریف کنید
از اولین محدودیت،
| x + 7 ⁄ 2 y + 3 ⁄ 2 z | ≤ | 25 |
دارای ضرایب غیر صحیح است، ابتدا باید کل محدودیت را در یک عدد صحیح به اندازه کافی بزرگ ضرب کنید تا ضرایب را به اعداد صحیح تبدیل کنید. در این حالت، می توانید در 2 ضرب کنید که منجر به محدودیت جدید می شود
| 2 x + 7 y + 3 z | ≤ | 50 |
این مسئله را تغییر نمی‌دهد، زیرا محدودیت اصلی دقیقاً همان راه‌حل‌های محدودیت تبدیل شده را دارد.
کد زیر سه قید خطی را برای مسئله تعریف می کند:
model.add(2 * x + 7 * y + 3 * z <= 50)
model.add(3 * x - 5 * y + 7 * z <= 45)
model.add(5 * x + 2 * y - 6 * z <= 37)
cp_model.AddLessOrEqual(2 * x + 7 * y + 3 * z, 50);
cp_model.AddLessOrEqual(3 * x - 5 * y + 7 * z, 45);
cp_model.AddLessOrEqual(5 * x + 2 * y - 6 * z, 37);
model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 7, 3}), 50);
model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {3, -5, 7}), 45);
model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {5, 2, -6}), 37);
model.Add(2 * x + 7 * y + 3 * z <= 50);
model.Add(3 * x - 5 * y + 7 * z <= 45);
model.Add(5 * x + 2 * y - 6 * z <= 37);
تابع هدف را تعریف کنید
کد زیر تابع هدف را برای مسئله تعریف می کند و آن را یک مشکل حداکثر سازی اعلام می کند:
model.maximize(2 * x + 2 * y + 3 * z)
cp_model.Maximize(2 * x + 2 * y + 3 * z);
model.maximize(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 2, 3}));
model.Maximize(2 * x + 2 * y + 3 * z);
با حل کننده تماس بگیرید
کد زیر حل کننده را فراخوانی می کند.
solver = cp_model.CpSolver()
status = solver.solve(model)
const CpSolverResponse response = Solve(cp_model.Build());
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
راه حل را نمایش دهید
کد زیر نتایج را نمایش می دهد.
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f"Maximum of objective function: {solver.objective_value}\n")
print(f"x = {solver.value(x)}")
print(f"y = {solver.value(y)}")
print(f"z = {solver.value(z)}")
else:
print("No solution found.")
if (response.status() == CpSolverStatus::OPTIMAL ||
response.status() == CpSolverStatus::FEASIBLE) {
// Get the value of x in the solution.
LOG(INFO) << "Maximum of objective function: "
<< response.objective_value();
LOG(INFO) << "x = " << SolutionIntegerValue(response, x);
LOG(INFO) << "y = " << SolutionIntegerValue(response, y);
LOG(INFO) << "z = " << SolutionIntegerValue(response, z);
} else {
LOG(INFO) << "No solution found.";
}
if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
System.out.printf("Maximum of objective function: %f%n", solver.objectiveValue());
System.out.println("x = " + solver.value(x));
System.out.println("y = " + solver.value(y));
System.out.println("z = " + solver.value(z));
} else {
System.out.println("No solution found.");
}
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
Console.WriteLine($"Maximum of objective function: {solver.ObjectiveValue}");
Console.WriteLine("x = " + solver.Value(x));
Console.WriteLine("y = " + solver.Value(y));
Console.WriteLine("z = " + solver.Value(z));
}
else
{
Console.WriteLine("No solution found.");
}
خروجی در زیر نشان داده شده است:
Maximum of objective function: 35 x value: 7 y value: 3 z value: 5
کل برنامه
کل برنامه در زیر نشان داده شده است.
"""Simple solve."""
from ortools.sat.python import cp_model
def main() -> None:
"""Minimal CP-SAT example to showcase calling the solver."""
# Creates the model.
model = cp_model.CpModel()
# Creates the variables.
var_upper_bound = max(50, 45, 37)
x = model.new_int_var(0, var_upper_bound, "x")
y = model.new_int_var(0, var_upper_bound, "y")
z = model.new_int_var(0, var_upper_bound, "z")
# Creates the constraints.
model.add(2 * x + 7 * y + 3 * z <= 50)
model.add(3 * x - 5 * y + 7 * z <= 45)
model.add(5 * x + 2 * y - 6 * z <= 37)
model.maximize(2 * x + 2 * y + 3 * z)
# Creates a solver and solves the model.
solver = cp_model.CpSolver()
status = solver.solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f"Maximum of objective function: {solver.objective_value}\n")
print(f"x = {solver.value(x)}")
print(f"y = {solver.value(y)}")
print(f"z = {solver.value(z)}")
else:
print("No solution found.")
# Statistics.
print("\nStatistics")
print(f" status : {solver.status_name(status)}")
print(f" conflicts: {solver.num_conflicts}")
print(f" branches : {solver.num_branches}")
print(f" wall time: {solver.wall_time} s")
if __name__ == "__main__":
main()
#include <stdint.h>
#include <stdlib.h>
#include <algorithm>
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/util/sorted_interval_list.h"
namespace operations_research {
namespace sat {
void CpSatExample() {
CpModelBuilder cp_model;
int64_t var_upper_bound = std::max({50, 45, 37});
const Domain domain(0, var_upper_bound);
const IntVar x = cp_model.NewIntVar(domain).WithName("x");
const IntVar y = cp_model.NewIntVar(domain).WithName("y");
const IntVar z = cp_model.NewIntVar(domain).WithName("z");
cp_model.AddLessOrEqual(2 * x + 7 * y + 3 * z, 50);
cp_model.AddLessOrEqual(3 * x - 5 * y + 7 * z, 45);
cp_model.AddLessOrEqual(5 * x + 2 * y - 6 * z, 37);
cp_model.Maximize(2 * x + 2 * y + 3 * z);
// Solving part.
const CpSolverResponse response = Solve(cp_model.Build());
if (response.status() == CpSolverStatus::OPTIMAL ||
response.status() == CpSolverStatus::FEASIBLE) {
// Get the value of x in the solution.
LOG(INFO) << "Maximum of objective function: "
<< response.objective_value();
LOG(INFO) << "x = " << SolutionIntegerValue(response, x);
LOG(INFO) << "y = " << SolutionIntegerValue(response, y);
LOG(INFO) << "z = " << SolutionIntegerValue(response, z);
} else {
LOG(INFO) << "No solution found.";
}
// Statistics.
LOG(INFO) << "Statistics";
LOG(INFO) << CpSolverResponseStats(response);
}
} // namespace sat
} // namespace operations_research
int main() {
operations_research::sat::CpSatExample();
return EXIT_SUCCESS;
}
package com.google.ortools.sat.samples;
import static java.util.Arrays.stream;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.LinearExpr;
/** Minimal CP-SAT example to showcase calling the solver. */
public final class CpSatExample {
public static void main(String[] args) {
Loader.loadNativeLibraries();
// Create the model.
CpModel model = new CpModel();
// Create the variables.
int varUpperBound = stream(new int[] {50, 45, 37}).max().getAsInt();
IntVar x = model.newIntVar(0, varUpperBound, "x");
IntVar y = model.newIntVar(0, varUpperBound, "y");
IntVar z = model.newIntVar(0, varUpperBound, "z");
// Create the constraints.
model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 7, 3}), 50);
model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {3, -5, 7}), 45);
model.addLessOrEqual(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {5, 2, -6}), 37);
model.maximize(LinearExpr.weightedSum(new IntVar[] {x, y, z}, new long[] {2, 2, 3}));
// Create a solver and solve the model.
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);
if (status == CpSolverStatus.OPTIMAL || status == CpSolverStatus.FEASIBLE) {
System.out.printf("Maximum of objective function: %f%n", solver.objectiveValue());
System.out.println("x = " + solver.value(x));
System.out.println("y = " + solver.value(y));
System.out.println("z = " + solver.value(z));
} else {
System.out.println("No solution found.");
}
// Statistics.
System.out.println("Statistics");
System.out.printf(" conflicts: %d%n", solver.numConflicts());
System.out.printf(" branches : %d%n", solver.numBranches());
System.out.printf(" wall time: %f s%n", solver.wallTime());
}
private CpSatExample() {}
}
using System;
using System.Linq;
using Google.OrTools.Sat;
public class CpSatExample
{
static void Main()
{
// Creates the model.
CpModel model = new CpModel();
// Creates the variables.
int varUpperBound = new int[] { 50, 45, 37 }.Max();
IntVar x = model.NewIntVar(0, varUpperBound, "x");
IntVar y = model.NewIntVar(0, varUpperBound, "y");
IntVar z = model.NewIntVar(0, varUpperBound, "z");
// Creates the constraints.
model.Add(2 * x + 7 * y + 3 * z <= 50);
model.Add(3 * x - 5 * y + 7 * z <= 45);
model.Add(5 * x + 2 * y - 6 * z <= 37);
model.Maximize(2 * x + 2 * y + 3 * z);
// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
{
Console.WriteLine($"Maximum of objective function: {solver.ObjectiveValue}");
Console.WriteLine("x = " + solver.Value(x));
Console.WriteLine("y = " + solver.Value(y));
Console.WriteLine("z = " + solver.Value(z));
}
else
{
Console.WriteLine("No solution found.");
}
Console.WriteLine("Statistics");
Console.WriteLine($" conflicts: {solver.NumConflicts()}");
Console.WriteLine($" branches : {solver.NumBranches()}");
Console.WriteLine($" wall time: {solver.WallTime()}s");
}
}