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

Các phần sau đây sẽ giúp bạn bắt đầu sử dụng OR-Tools dành cho Java:

Vấn đề 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ố một nhóm lớn các giải pháp khả thi. (Đôi khi bạn sẽ hài lòng với việc tìm thấy bất kỳ giải pháp khả thi nào; OR-Tools cũng có thể làm điều đó).

Dưới đây là một vấn đề thường gặp về tối ưu hoá. Giả sử rằng 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 các gói hàng cho xe tải, sau đó chọn tuyến đường cho từng xe tải để giao các gói hàng đó. Mỗi lần chỉ định gói và tuyến đường có thể có chi phí, dựa trên tổng quãng đường đi của xe tải và cả các yếu tố khác. Vấn đề là phải chọn chỉ định các gói và tuyến có chi phí thấp nhất.

Giống như tất cả 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 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 vấ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 tổng chi phí của mọi hoạt động chỉ định gói và tuyến đường.

    Giải pháp tối ưu là giải pháp mà trong đó giá trị của hàm mục tiêu là tốt nhất. ("Tốt nhất" có thể là giá trị tối đa hoặc tối thiểu.)

  • Các quy tắc ràng buộc – các hạn chế đối với tập hợp giải pháp có thể có, dựa trên 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ì điều này sẽ gây hạn chế cho các giải pháp.

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

Bước đầu tiên để 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 Java

Tiếp theo, chúng tôi sẽ đưa ra ví dụ về một vấn đề tối ưu hoá, đồng thời cho thấy cách thiết lập và giải quyết vấn đề đó trong Java.

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 và được sử dụng rộng rãi nhất là tối ưu hoá tuyến tính (hoặc 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. Dưới đây là ví dụ đơn giản về loại vấn đề này.

Tối đa hoá 3x + y tuân theo các điều kiện ràng buộc sau:

  1. 0 ≤ x ≤ 1
  2. 0 ≤ y ≤ 2
  3. 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 quy tắc ràng buộc đều do biểu thức tuyến tính tính, khiến đây là bài toán tuyến tính.

Các bước chính trong việc 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 một vấn đề đều giống nhau:

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

Chương trình Java<

Phần này sẽ trình bày về một chương trình Java có thể thiết lập và giải quyết vấn đề này.

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

  • Nhập các thư viện cần thiết.
    import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;
  • Khai báo trình giải toán. 
    // Create the linear solver with the GLOP backend.
MPSolver solver = MPSolver.createSolver("GLOP");
    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 x = solver.makeNumVar(0.0, 1.0, "x");
MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

System.out.println("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 trong đị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, 0 <= x + y <= 2.
MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
ct.setCoefficient(x, 1);
ct.setCoefficient(y, 1);

System.out.println("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 objective = solver.objective();
objective.setCoefficient(x, 3);
objective.setCoefficient(y, 1);
objective.setMaximization();
    Phương thức setMaximization khai báo đây là bài toán tối đa hoá.
  • Gọi trình giải và hiện kết quả. 
    solver.solve();
System.out.println("Solution:");
System.out.println("Objective value = " + objective.value());
System.out.println("x = " + x.solutionValue());
System.out.println("y = " + y.solutionValue());

Hoàn thành chương trình

Chương trình hoàn chỉnh được hiển thị dưới đây.

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

    // Create the variables x and y.
    MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
    MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    solver.solve();

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());
  }

  private BasicExample() {}
}

Chạy chương trình Java

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

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

Chương trình này sẽ trả về các giá trị của x và y giúp 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/my_program.java

Ví dụ khác về Java

Để xem thêm ví dụ về Java minh hoạ cách giải nhiều loại bài tập 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 bài tập tối ưu hoá trên thế giới. Đối với mỗi loại bài toán, sẽ có nhiều 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 quyết phù hợp — một thuật toán để tìm ra 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 có thể giải quyết, cũng như các đườ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 quyết từng loại vấn đề.

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

Như bạn đã 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 khi hàm mục tiêu và các giới hạn là biểu thức tuyến tính trong các biến.

Trình giải quyết chính trong OR-Tools cho loại vấn đề này là trình giải quyết tối ưu hoá tuyến tính. Trình giải quyết này thực sự là một trình bao bọc cho một số thư viện khác nhau để tối ưu hoá tuyến tính và 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á hỗn hợp số nguyên

Vấn đề tối ưu hoá số nguyên hỗn hợp là 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ề 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 chỉ định cho tác vụ nhất định và là 0 nếu không. 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á hạn chế

Tối ưu hoá quy tắc ràng buộc, hay lập trình ràng buộc (CP), xác định các giải pháp khả thi trong số một nhóm đề xuất rất lớn, trong đó vấn đề có thể được mô hình hoá dưới dạng các quy tắc 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 quy tắc ràng buộc và biến thay vì hàm mục tiêu. Tuy nhiên, bạn có thể dùng CP để giải các vấn đề tối ưu hoá chỉ bằng cách so sánh giá trị của hàm mục tiêu với tất cả các giải pháp khả thi.

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

Assignment

Bài tập gán liên quan đến việc chỉ định một nhóm tác nhân (chẳng hạn như worker 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. Sự cố 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 số điện thoại

Đóng hàng

Đóng gói trong thùng là vấn đề khi phải đó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 đề Knapsack, trong đó chỉ có một vùng chứa.

Tìm hiểu thêm về cách đóng gói thùng rác

Lập lịch

Vấn đề về lịch trình liên quan đến việc chỉ định 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à phải xử lý mỗi tác vụ 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 đề đị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ạng, được xác định bằng biểu đồ có 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ề sự cố định tuyến. Một vấn đề khác là vấn đề nhân viên bán hàng đi lại.

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 một biểu đồ có hướng bao gồm các nút và vòng cung định hướng giữa chúng. 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à các tuyến đường sắt 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 nó. Vấn đề là chỉ định số lượng hàng hoá cần vận chuyển qua mỗi vòng cung để 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ề các luồng mạng