Giải quyết bài toán tối ưu hóa phức tạp ngay trên trình duyệt với Google OR-Tools và WebAssembly

Google OR-Tools là bộ công cụ mã nguồn mở hàng đầu của Google dùng để giải quyết các bài toán tối ưu hóa tổ hợp, lập trình tuyến tính và lập trình nguyên. Gần đây, một dự án mới mang tên or-tools-wasm đã được ra mắt, mang toàn bộ khả năng xử lý này vào trình duyệt thông qua công nghệ WebAssembly.

GitHub Repo stars npm version

Tại sao or-tools-wasm lại quan trọng?

Trước đây, để chạy các thuật toán tối ưu hóa nặng như CP-SAT hay Routing, các nhà phát triển thường phải xây dựng một backend server để xử lý và trả kết quả về cho frontend. Với or-tools-wasm, mọi thứ giờ đây có thể chạy trực tiếp trên máy của người dùng (client-side).

Điều này mang lại lợi ích lớn về tính riêng tư (dữ liệu không cần gửi lên server), giảm độ trễ (latency) và tiết kiệm chi phí hạ tầng. Dự án này cung cấp API TypeScript đầy đủ, hỗ trợ đa luồng (multithreaded) để tận dụng sức mạnh của CPU hiện đại.

Các tính năng chính

Thư viện này bao bọc (wrap) hầu hết các thành phần quan trọng của Google OR-Tools:

• CP-SAT: Giải quyết bài toán ràng buộc và tối ưu hóa nguyên cho các mô hình logic, lập lịch.
• Routing: Tối ưu hóa lộ trình phương tiện (VRP), bài toán người bán hàng du lịch (TSP), và các vấn đề về thời gian/công suất.
• MPSolver & MathOpt: Các API lập trình tuyến tính và hỗn hợp nguyên, bao gồm nhiều backend solver như GLOP, CLP, GLPK, SCIP.
• Các thuật toán đồ thị: Max-flow, min-cost-flow, bài toán cái balo (Knapsack), Set cover.

Cách sử dụng cơ bản

Việc tích hợp vào dự án rất đơn giản thông qua npm:

npm install or-tools-wasm

Bạn có thể import các solver cần thiết từ các đường dẫn con:

import { CpModel, CpSolver } from 'or-tools-wasm/cp-sat';

// Tạo và giải quyết mô hình
const model = {
  name: 'simple_model',
  variables: [
    { name: 'x', domain: [0, 10] },
    { name: 'y', domain: [0, 10] }
  ],
  // ... thêm ràng buộc và mục tiêu
};

const modelBytes = await CpSat.createModel(model);
const result = await CpSat.solve(modelBytes);
console.log(result.response);

Yêu cầu kỹ thuật với trình duyệt

Vì sử dụng WebAssembly đa luồng và SharedArrayBuffer, trang web của bạn cần được phục vụ với các tiêu đề bảo mật cụ thể để bật tính năng cô lập nguồn gốc chéo (cross-origin isolation):

• Cross-Origin-Opener-Policy: same-origin
• Cross-Origin-Embedder-Policy: require-corp

Nếu thiếu các header này, trình duyệt sẽ chặn SharedArrayBuffer, khiến quá trình giải quyết bài toán có thể thất bại.

Build Status

Worker Bridge và Hiệu suất

Một điểm cộng lớn của or-tools-wasm là cơ chế Worker Bridge. Các bài toán tối ưu hóa có thể tốn nhiều thời gian CPU. Nếu chạy trực tiếp trên luồng chính (main thread), giao diện người dùng (UI) sẽ bị treo.

Thư viện này cho phép chạy solver trong một Web Worker ẩn. Điều này giúp luồng chính luôn thoải mái để xử lý việc render, nhập liệu và cập nhật tiến độ cho người dùng.

Dự án hiện đang được duy trì bởi Axel Wickman và đã được sử dụng trong các ứng dụng thực tế như PragmaPlanner. Đây là một công cụ hữu ích cho cộng đồng lập trình viên web muốn áp dụng AI và tối ưu hóa hóa học trực tiếp trên nền tảng browser.