50 năm lập trình tuyến tính nguyên: những tiến bộ thực tiễn gần đây — Hiển thị trang bảo vệ Anubis
(inria.hal.science)- Thay vì nội dung bài báo, trang xác minh bot Anubis được hiển thị, nên không thể xem ngay nội dung bài báo thực tế tại URL đó
- Trang bảo vệ cho biết việc quét web quá mức của các công ty AI có thể dẫn đến thời gian ngừng hoạt động của máy chủ và chặn truy cập tài nguyên
- Anubis yêu cầu bằng chứng công việc tương tự Hashcash, được thiết kế để người dùng cá nhân chỉ chịu gánh nặng nhỏ nhưng chi phí tích lũy sẽ lớn đối với việc quét dữ liệu quy mô lớn
- Cách này là giải pháp tạm thời, và về lâu dài tập trung vào việc nhận diện trình duyệt headless qua các dấu hiệu như render phông chữ
- Do cần các tính năng JavaScript hiện đại, nếu đang bật plugin như JShelter thì phải tắt trên tên miền đó mới có thể truy cập
Trang bảo vệ Anubis đang được hiển thị
- Tiêu đề trang là “Making sure you're not a bot!”, và trên màn hình hiển thị trạng thái đang tính toán
- Độ khó là
4 - Tốc độ là
0kH/s
- Độ khó là
- Quản trị viên máy chủ đã thiết lập Anubis để bảo vệ máy chủ khỏi hoạt động quét dữ liệu quá mức của các công ty AI, nên trang này được hiển thị
- Việc quét dữ liệu quy mô lớn có thể gây ra thời gian ngừng hoạt động của website, và kết quả là mọi người dùng đều có thể không truy cập được tài nguyên
Cơ chế bằng chứng công việc và hạn chế truy cập
- Anubis sử dụng cơ chế bằng chứng công việc thuộc họ Hashcash
- Gánh nặng bổ sung với từng người dùng riêng lẻ là không đáng kể
- Với các trình quét quy mô lớn, chi phí tích lũy tăng lên khiến chi phí quét dữ liệu cao hơn
- Cách làm hiện tại gần với một giải pháp tạm thời
- Mục tiêu là câu giờ để nhận diện trình duyệt headless qua các dấu hiệu như cách render phông chữ
- Hướng đi là không hiển thị trang bằng chứng công việc với những trường hợp nhiều khả năng là người dùng hợp pháp
- Anubis yêu cầu các tính năng JavaScript hiện đại
- Các plugin như JShelter có thể vô hiệu hóa những tính năng cần thiết
- Trên tên miền này cần tắt JShelter hoặc plugin tương tự
1 bình luận
Các ý kiến trên Hacker News
Muốn hiểu ở mức tổng quan vì sao các solver quy hoạch tuyến tính nguyên (ILP) thương mại như Gurobi lại tốt hơn rất nhiều so với các lựa chọn miễn phí/mã nguồn mở.
Tôi thắc mắc liệu có phải vì ILP vốn là một bài toán quá khó, nên các solver tốt nhất về cơ bản là một tập hợp quy mô lớn các heuristic cho những bài toán con cụ thể, còn trong phạm vi công khai thì nhìn chung vẫn chưa có chiến lược nào đủ tốt hay không.
Trong quy hoạch tuyến tính nguyên hỗn hợp (MILP), điều quan trọng là các heuristic để tìm điểm khởi đầu tốt cho phương pháp nhánh-cận và tỉa cây hiệu quả, cũng như các mặt phẳng cắt tùy chỉnh để loại bỏ nghiệm phân số, cải thiện giá trị mục tiêu và tính nguyên.
Khi các nhà nghiên cứu vận trù học tập trung vào một bài toán cụ thể, họ cũng có thể tự viết các mặt phẳng cắt và heuristic để đánh bại khá dễ dàng các solver đa dụng như Gurobi. Các công ty solver thuê các nhóm tiến sĩ và nhà nghiên cứu để liên tục làm việc này, đồng thời theo dõi cải thiện và hồi quy trên các tập bài toán của khách hàng.
Các solver mã nguồn mở dường như bị kìm chân bởi vài yếu tố chồng lên nhau. Rào cản gia nhập đối với phát triển tối ưu hóa hiện đại rất cao, nên ngay từ đầu đã có ít nhà nghiên cứu/nhà phát triển có thể đóng góp đáng kể ở cả hai mặt toán học và lập trình; nếu có năng lực như vậy thì các con đường sinh lợi lại kéo họ ra xa khỏi việc đóng góp mã nguồn mở; và do đặc thù của dự án mã nguồn mở, “khách hàng” ít có khả năng cung cấp ngược lại các ví dụ, dữ liệu hiệu năng và profiling cần thiết để cải thiện solver.
Có ngoại lệ, nhưng nằm ngoài phát triển solver thương mại truyền thống không có nghĩa là sẽ là mã nguồn mở. Ví dụ SNOPT được phát triển tại Stanford vẫn là giấy phép thương mại. Công việc về solver trong học thuật thường diễn ra trong các bối cảnh ứng dụng cụ thể như Clarabel, nên có xu hướng thu hẹp phạm vi họ bài toán.
Ở các lĩnh vực khác, các công ty công nghệ lớn đôi khi vượt qua điểm nghẽn bằng cách mua lại dự án thương mại hiện có, hoặc tài trợ dự án mã nguồn mở để kiềm chế đối thủ. Trong mảng solver cũng có những ví dụ hẹp như Ceres, nhưng có lẽ khoản đầu tư để phát triển từ đầu toàn bộ stack solver đa dụng bị xem là quá lớn.
Nếu bạn biết cấu trúc của bài toán, bạn cũng có thể tận dụng nó để vượt qua hiệu năng của solver thương mại. Nhưng với một bài toán tùy ý thì gần như không có khả năng.
Tôi lờ mờ nhớ mình từng xây một công cụ phân bổ tài nguyên bằng thư viện quy hoạch tuyến tính nguyên hỗn hợp “ILOG” của IBM. Khi đó tôi nhận ra rằng nếu cùng bài toán mà chúng tôi giải trong vòng 5 phút được tạo ra 20 năm trước, thì có lẽ nó vẫn còn đang chạy đến giờ.
Theo tôi nhớ, năng lực tính toán thuần đã tăng khoảng 1000 lần, và thuật toán cũng cải thiện ở mức tương tự, tổng cộng tốt hơn khoảng một triệu lần.
Đây là điều đáng suy ngẫm khi dự đoán tương lai. Nhân tiện, “tài nguyên” đó là kim cương.
Tôi tò mò những thứ này thực sự được dùng như thế nào. Khi triển khai tối ưu hóa số, tôi hình dung nó thường thất bại vì các vấn đề phổ biến trong cách tiếp cận dựa trên dữ liệu, chẳng hạn niềm tin và dữ liệu xấu, rồi cuối cùng một người quan trọng nào đó quyết định nên làm gì bằng trực giác.
Giá điện giao ngay của EU được xác định mỗi ngày bằng một lần chạy solver khổng lồ. Hãy tìm Euphemia, có các bài viết về cách nó hoạt động.
Hầu hết các lĩnh vực có mục tiêu tối ưu hóa rõ ràng và tiền thật liên quan đều đầy solver.
Phần tồn kho chưa được tự động hóa hoàn toàn vì dự báo nhu cầu khó.
Case study của Gurobi: https://www.gurobi.com/case_studies/
Một số case study của CPLEX: https://www.ibm.com/products/ilog-cplex-optimization-studio/...
Case study của Hexaly, trước đây là LocalSolver: https://www.hexaly.com/customers
Tôi nghe nói Gurobi khá đắt. Không biết có ai có thể chia sẻ thông tin giá không.
Có ít nhất hai MIP solver khá ổn là mã nguồn mở hoặc miễn phí cho mục đích phi thương mại.
https://highs.dev/
https://www.scipopt.org/
Tôi muốn nói thêm rằng với nhiều người trong ngành, nó hoàn toàn xứng đáng với số tiền đó.
Tôi nhớ hồi thập niên 1990 từng triển khai một phiên bản nào đó của siêu phẳng cắt Gomory trong Maple để học, không phải để dùng thực tế. Có vẻ lĩnh vực này đã tiến bộ rất nhiều
“Nếu vào đầu thập niên 1990 cần hai tháng thời gian chạy để giải LP, thì ngày nay chưa đến 1 giây. Gần đây, Bixby đã so sánh hiệu năng không phụ thuộc vào máy của hai bộ giải MILP là CPLEX và Gurobi từ năm 1990 đến 2020, và báo cáo mức tăng tốc gần 4×10^6 lần”
Tôi có cảm giác các cách tiếp cận dựa trên học máy/trí tuệ nhân tạo cho những bài toán kiểu này còn khá thiếu. Tôi đã thấy nhiều bài báo dùng học tăng cường/mạng nơ-ron đồ thị để giải các bài toán nhỏ, nhưng rốt cuộc nhiều khi mua giấy phép Gurobi rồi chạy vẫn có vẻ là lựa chọn tốt nhất
Gần đây tôi làm tối ưu hóa lịch trình khá gần với lập lịch phân xưởng; tuy có ví dụ dùng học tăng cường, nhưng trông vẫn chưa đủ. Với các bài toán lớn, tôi đã phải dựa vào thuật toán tiến hóa để có được nghiệm tương đối hợp lý
Không biết nếu có thể mô hình hóa bài toán tốt thì cách tiếp cận kiểu vận trù học có phải luôn hiệu quả hơn không
Bạn cũng có thể xây thuật toán di truyền, nhưng không có gì đảm bảo nó sẽ cho lời giải không bị kẹt ở cực tiểu cục bộ. Cũng cần giả định rằng có thể làm cho nó chạy nhanh. Mạng nơ-ron thì cũng sẽ kém tối ưu hơn
“Từ năm 1988 đến 2004, phần cứng đã nhanh hơn 1600 lần, còn bộ giải LP nhanh hơn 3300 lần, tạo ra hệ số tăng tốc tích lũy vượt quá 5 × 10^6. Mà đó đã là chuyện của 20 năm trước!”
“Các tác giả quan sát thấy mức tăng tốc 1000 lần trong các bộ giải MILP thương mại từ năm 2001 đến 2020. Trong đó 50 lần đến từ thuật toán, 20 lần nhờ máy tính nhanh hơn”
Tôi tự hỏi liệu có thể thu thập các hệ số tăng tốc như thế cho từng phân ngành của điện toán, rồi phân tách đóng góp giữa cải tiến thuật toán và máy tính nhanh hơn hay không
Trong lĩnh vực trình biên dịch có “định luật Proebsting”: tiến bộ của trình biên dịch làm hiệu năng tính toán tăng gấp đôi mỗi 18 năm
Nên thêm [pdf] [2024] vào tiêu đề