Trang này được dịch bởi Cloud Translation API.

Làm quen với công cụ OR cho C++

Các phần sau sẽ giúp bạn làm quen với công cụ OR-Tools bằng C++:

Vấn đề tối ưu hoá là gì?
Giải quyết vấn đề tối ưu hoá trong C++
Ví dụ khác về C++
Xác định loại vấn đề bạn muốn giải quyết

Sự cố tối ưu hoá là gì?

Mục tiêu của tính năng tối ưu hoá là tìm ra giải pháp tốt nhất cho một vấn đề trong số rất nhiều giải pháp khả thi. (Đôi khi, bạn sẽ hài lòng với việc tìm thấy mọi giải pháp khả thi; OR-Tools cũng có thể làm được điều đó.)

Dưới đây là một vấn đề tối ưu hoá điển hình. Giả sử một công ty vận chuyển giao gói hàng cho khách hàng của họ bằng một đội xe tải. Mỗi ngày, công ty phải giao gói hàng cho các xe tải, sau đó chọn tuyến đường cho từng xe tải để giao các gói hàng. Mỗi hoạt động chỉ định có thể áp dụng cho các gói hàng và tuyến đường đều có chi phí, dựa trên tổng quãng đường đi của xe tải và có thể là cả các yếu tố khác. Vấn đề là phải chọn cách chỉ định các gói và tuyến có chi phí thấp nhất.

Giống như mọi bài toán tối ưu hoá, vấn đề này có các yếu tố sau:

Mục tiêu: số lượng mà bạn muốn tối ưu hoá. Trong ví dụ trên, mục tiêu là giảm thiểu chi phí. Để thiết lập một bài toán tối ưu hoá, bạn cần xác định một hàm tính toán giá trị của mục tiêu cho mọi giải pháp khả thi. Hàm này được gọi là hàm mục tiêu. Trong ví dụ trước, hàm mục tiêu sẽ tính toán tổng chi phí của mọi lượt chỉ định gói và tuyến.

Giải pháp tối ưu là giải pháp có giá trị cao nhất của hàm mục tiêu. ("Tốt nhất" có thể là mức tối đa hoặc mức tối thiểu).
Các quy tắc ràng buộc – những hạn chế đối với nhóm giải pháp khả thi, dựa trên các yêu cầu cụ thể của vấn đề. Ví dụ: nếu công ty vận chuyển không thể chỉ định các gói hàng có trọng lượng lớn hơn một trọng lượng nhất định cho xe tải, thì việc này sẽ gây ra hạn chế đối với các giải pháp.

Giải pháp khả thi là giải pháp đáp ứng tất cả các hạn chế đặt ra cho bài toán mà không nhất thiết phải là giải pháp tối ưu.

Bước đầu tiên trong quá trình giải quyết một vấn đề tối ưu hoá là xác định mục tiêu và các hạn chế.

Giải bài tập tối ưu hoá trong C++

Tiếp theo, chúng tôi sẽ đưa ra ví dụ về một bài toán tối ưu hoá cũng như trình bày cách thiết lập và giải quyết bài toán đó trong C++.

Ví dụ về phương pháp tối ưu hoá tuyến tính

Một trong những phương pháp tối ưu hoá lâu đời nhất và được sử dụng rộng rãi nhất là tối ưu hoá tuyến tính (hay lập trình tuyến tính), trong đó hàm mục tiêu và các quy tắc ràng buộc có thể được viết dưới dạng biểu thức tuyến tính. Sau đây là ví dụ đơn giản về loại vấn đề này.

Tối đa hoá 3x + y phải tuân theo các ràng buộc sau:

0 ≤ x ≤ 1
0 ≤ y ≤ 2
x + y ≤ 2

Hàm mục tiêu trong ví dụ này là 3x + y. Cả hàm mục tiêu và các điều kiện ràng buộc đều được đưa ra bởi biểu thức tuyến tính, điều này khiến đây là một bài toán tuyến tính.

Các bước chính để giải bài tập

Đối với mỗi ngôn ngữ, các bước cơ bản để thiết lập và giải quyết vấn đề đều giống nhau:

Nhập các thư viện bắt buộc,
Khai báo trình giải,
Tạo các biến,
Xác định các điều kiện ràng buộc,
Xác định hàm mục tiêu,
Gọi trình giải toán và
Hiện kết quả.

Chương trình C++

Phần này trình bày một chương trình C++ có chức năng thiết lập và giải quyết vấn đề.

Sau đây là các bước:

Nhập các thư viện cần thiết.

#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

Khai báo trình giải.

// Create the linear solver with the GLOP backend.
std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
if (!solver) {
  LOG(WARNING) << "Could not create solver GLOP";
  return;
}

MPSolver là một trình bao bọc để giải quyết mọi vấn đề về lập trình tuyến tính hoặc lập trình số nguyên hỗn hợp.

Tạo các biến.

// Create the variables x and y.
MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

LOG(INFO) << "Number of variables = " << solver->NumVariables();

Xác định các điều kiện ràng buộc. Hai điều kiện ràng buộc đầu tiên, 0 &leq; x ≤ 1 và 0 &leq; y ≤ 2, đã được đặt theo định nghĩa của các biến. Mã sau đây xác định điều kiện ràng buộc x + y &leq; 2:
```
// Create a linear constraint, x + y <= 2.
const double infinity = solver->infinity();
MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
ct->SetCoefficient(x, 1);
ct->SetCoefficient(y, 1);

LOG(INFO) << "Number of constraints = " << solver->NumConstraints();
```
Phương thức SetCoefficient đặt hệ số của x và y trong biểu thức cho quy tắc ràng buộc.

Xác định hàm mục tiêu.

// Create the objective function, 3 * x + y.
MPObjective* const objective = solver->MutableObjective();
objective->SetCoefficient(x, 3);
objective->SetCoefficient(y, 1);
objective->SetMaximization();

Phương thức SetMaximization khai báo đây là sự cố tối đa hoá.

Gọi trình giải toán và hiện kết quả.

LOG(INFO) << "Solving with " << solver->SolverVersion();
const MPSolver::ResultStatus result_status = solver->Solve();
// Check that the problem has an optimal solution.
LOG(INFO) << "Status: " << result_status;
if (result_status != MPSolver::OPTIMAL) {
  LOG(INFO) << "The problem does not have an optimal solution!";
  if (result_status == MPSolver::FEASIBLE) {
    LOG(INFO) << "A potentially suboptimal solution was found";
  } else {
    LOG(WARNING) << "The solver could not solve the problem.";
    return;
  }
}

LOG(INFO) << "Solution:";
LOG(INFO) << "Objective value = " << objective->Value();
LOG(INFO) << "x = " << x->solution_value();
LOG(INFO) << "y = " << y->solution_value();

Hoàn tất chương trình

Dưới đây là chương trình đầy đủ.

// Minimal example to call the GLOP solver.
#include <cstdlib>
#include <memory>

#include "absl/flags/flag.h"
#include "absl/log/flags.h"
#include "ortools/base/init_google.h"
#include "ortools/base/logging.h"
#include "ortools/init/init.h"
#include "ortools/linear_solver/linear_solver.h"

namespace operations_research {
void BasicExample() {
  LOG(INFO) << "Google OR-Tools version : " << OrToolsVersion::VersionString();

  // Create the linear solver with the GLOP backend.
  std::unique_ptr<MPSolver> solver(MPSolver::CreateSolver("GLOP"));
  if (!solver) {
    LOG(WARNING) << "Could not create solver GLOP";
    return;
  }

  // Create the variables x and y.
  MPVariable* const x = solver->MakeNumVar(0.0, 1, "x");
  MPVariable* const y = solver->MakeNumVar(0.0, 2, "y");

  LOG(INFO) << "Number of variables = " << solver->NumVariables();

  // Create a linear constraint, x + y <= 2.
  const double infinity = solver->infinity();
  MPConstraint* const ct = solver->MakeRowConstraint(-infinity, 2.0, "ct");
  ct->SetCoefficient(x, 1);
  ct->SetCoefficient(y, 1);

  LOG(INFO) << "Number of constraints = " << solver->NumConstraints();

  // Create the objective function, 3 * x + y.
  MPObjective* const objective = solver->MutableObjective();
  objective->SetCoefficient(x, 3);
  objective->SetCoefficient(y, 1);
  objective->SetMaximization();

  LOG(INFO) << "Solving with " << solver->SolverVersion();
  const MPSolver::ResultStatus result_status = solver->Solve();

  // Check that the problem has an optimal solution.
  LOG(INFO) << "Status: " << result_status;
  if (result_status != MPSolver::OPTIMAL) {
    LOG(INFO) << "The problem does not have an optimal solution!";
    if (result_status == MPSolver::FEASIBLE) {
      LOG(INFO) << "A potentially suboptimal solution was found";
    } else {
      LOG(WARNING) << "The solver could not solve the problem.";
      return;
    }
  }

  LOG(INFO) << "Solution:";
  LOG(INFO) << "Objective value = " << objective->Value();
  LOG(INFO) << "x = " << x->solution_value();
  LOG(INFO) << "y = " << y->solution_value();

  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << solver->wall_time() << " milliseconds";
  LOG(INFO) << "Problem solved in " << solver->iterations() << " iterations";
}
}  // namespace operations_research

int main(int argc, char* argv[]) {
  InitGoogle(argv[0], &argc, &argv, true);
  absl::SetFlag(&FLAGS_stderrthreshold, 0);
  operations_research::BasicExample();
  return EXIT_SUCCESS;
}

Chạy chương trình C++

Bạn có thể chạy chương trình trên như sau:

Sao chép và dán mã ở trên vào tệp mới rồi lưu dưới dạng program.cc.
Mở cửa sổ lệnh ở cấp cao nhất của thư mục bạn đã cài đặt OR-Tools rồi nhập:
```
make run SOURCE=relative/path/to/program.cc
```
, trong đó relative/path/to/ là đường dẫn đến thư mục bạn đã lưu chương trình.

Chương trình sẽ trả về các giá trị x và y để tối đa hoá hàm mục tiêu:

Solution:
x =  1.0
y =  1.0

Để chỉ biên dịch mà không cần chạy chương trình, hãy nhập:

make build SOURCE=relative/path/to/program.cc

Biên dịch ở chế độ chọn

Cách biên dịch ở chế độ O3:

make DEBUG='-O3' all

Chạy tệp thực thi C++

Khi bạn biên dịch chương trình C++ trong công cụ OR bằng make, tệp thực thi sẽ được tạo trong thư mục bin. Bạn có thể chạy tệp thực thi cho chương trình ví dụ như sau:

cd bin && ./program

Nếu có thay đổi đối với chương trình, bạn cần phải biên dịch lại như đã trình bày ở trên.

Ví dụ khác về C++

Để xem thêm ví dụ về C++ minh hoạ cách giải các loại vấn đề tối ưu hoá, hãy xem phần Ví dụ.

Xác định loại vấn đề bạn muốn giải quyết

Có nhiều loại vấn đề tối ưu hoá trên thế giới. Đối với mỗi loại vấn đề, sẽ có các phương pháp và thuật toán khác nhau để tìm ra một giải pháp tối ưu.

Trước khi có thể bắt đầu viết một chương trình để giải quyết một vấn đề tối ưu hoá, bạn cần xác định loại vấn đề mình đang gặp phải, sau đó chọn một trình giải toán phù hợp — một thuật toán giúp tìm ra một giải pháp tối ưu.

Dưới đây là thông tin tổng quan ngắn gọn về các loại vấn đề mà công cụ OR-Tools giải quyết và đường liên kết đến các phần trong hướng dẫn này giải thích cách giải từng loại vấn đề.

Tối ưu hoá tuyến tính
Tối ưu hoá quy tắc ràng buộc
Tối ưu hoá kết hợp số nguyên
Bài tập
Lập lịch
Đóng gói
Định tuyến
Luồng mạng

Tối ưu hoá tuyến tính

Như đã tìm hiểu trong phần trước, bài toán tối ưu hoá tuyến tính là bài toán trong đó hàm mục tiêu và các quy tắc ràng buộc là các biểu thức tuyến tính trong biến.

Trình giải quyết chính trong công cụ OR-Tools cho loại bài toán này là trình giải tối ưu hoá tuyến tính. Trên thực tế, đây là trình bao bọc cho một số thư viện cho phương pháp tuyến tính và tối ưu hoá hỗn hợp số nguyên, bao gồm cả các thư viện của bên thứ ba.

Tìm hiểu thêm về tính năng tối ưu hoá tuyến tính

Tối ưu hoá nhiều số nguyên

Vấn đề tối ưu hoá số nguyên hỗn hợp là một vấn đề trong đó một số hoặc tất cả các biến bắt buộc phải là số nguyên. Ví dụ như vấn đề về việc chỉ định, trong đó, một nhóm worker cần được chỉ định cho một nhóm tác vụ. Đối với mỗi trình thực thi và tác vụ, bạn xác định một biến có giá trị là 1 nếu trình thực thi đó được gán cho tác vụ đã cho và là 0 nếu không được chỉ định. Trong trường hợp này, các biến chỉ có thể nhận giá trị 0 hoặc 1.

Tìm hiểu thêm về tính năng tối ưu hoá kết hợp số nguyên

Tối ưu hoá quy tắc ràng buộc

Tối ưu hoá quy tắc ràng buộc (hay lập trình quy tắc ràng buộc – CP) sẽ xác định các giải pháp khả thi trong số một tập hợp rất nhiều đề xuất, trong đó vấn đề có thể được mô hình hoá theo các điều kiện ràng buộc tuỳ ý. CP dựa trên tính khả thi (tìm một giải pháp khả thi) thay vì tối ưu hoá (tìm một giải pháp tối ưu) và tập trung vào các hạn chế và biến thay vì hàm mục tiêu. Tuy nhiên, bạn có thể sử dụng CP để giải các bài tập tối ưu hoá, chỉ bằng cách so sánh các giá trị của hàm mục tiêu đối với tất cả các giải pháp khả thi.

Tìm hiểu thêm về cách tối ưu hoá quy tắc ràng buộc

Assignment

Vấn đề chỉ định liên quan đến việc chỉ định một nhóm tác nhân (chẳng hạn như nhân viên hoặc máy) cho một tập hợp tác vụ, trong đó có chi phí cố định để chỉ định từng tác nhân cho một tác vụ cụ thể. Vấn đề là tìm bài tập có tổng chi phí thấp nhất. Vấn đề gán thực sự là một trường hợp đặc biệt của vấn đề về luồng mạng.

Tìm hiểu thêm về việc chỉ định

Đóng hàng

Đóng gói thùng là vấn đề đóng gói một tập hợp đối tượng có kích thước khác nhau vào các vùng chứa có dung lượng khác nhau. Mục tiêu là đóng gói nhiều đối tượng nhất có thể, tuỳ thuộc vào dung lượng của các vùng chứa. Một trường hợp đặc biệt của trường hợp này là vấn đề về Ba lô, trong đó chỉ có một vùng chứa.

Tìm hiểu thêm về tính năng đóng gói thùng rác

Lập lịch

Sự cố lên lịch liên quan đến việc phân công tài nguyên để thực hiện một nhóm tác vụ vào các thời điểm cụ thể. Một ví dụ quan trọng là vấn đề về cửa hàng việc làm, trong đó nhiều công việc được xử lý trên một số máy. Mỗi công việc bao gồm một chuỗi các tác vụ phải được thực hiện theo thứ tự nhất định và mỗi tác vụ phải được xử lý trên một máy cụ thể. Vấn đề là chỉ định lịch biểu để tất cả các công việc được hoàn thành trong khoảng thời gian ngắn nhất có thể.

Tìm hiểu thêm về cách lên lịch

Đang định tuyến

Vấn đề về việc định tuyến liên quan đến việc tìm tuyến đường tối ưu cho một nhóm xe để đi qua một mạng, được xác định bằng biểu đồ định hướng. Vấn đề chỉ định gói hàng cho xe giao hàng, được mô tả trong phần Vấn đề tối ưu hoá là gì? là một ví dụ về vấn đề định tuyến. Một vấn đề khác là vấn đề của nhân viên bán hàng khi di chuyển.

Tìm hiểu thêm về cách định tuyến

Luồng mạng

Nhiều bài toán tối ưu hoá có thể được biểu thị bằng biểu đồ có hướng bao gồm các nút và vòng cung có định hướng giữa các nút. Ví dụ: các vấn đề về vận tải, trong đó hàng hoá được vận chuyển qua mạng lưới đường sắt, có thể được biểu thị bằng một biểu đồ, trong đó các vòng cung là đường ray và các nút là các trung tâm phân phối.

Trong bài toán về luồng tối đa, mỗi cung có sức chứa tối đa có thể được truyền tải qua đó. Vấn đề là chỉ định số lượng hàng hoá cần vận chuyển qua mỗi vòng cung sao cho tổng số lượng hàng được vận chuyển càng lớn càng tốt.

Tìm hiểu thêm về luồng mạng